人们可以以多少种不同的方式坐在圆桌会议上？

发布于 2024-12-02 18:58:51 字数 107 浏览 4 评论 0原文

我正在开发一种算法，并在得出结论之前研究最大迭代次数的可能性。

在现实世界中，它类似于经典圆桌座位问题。你能告诉我圆桌会议中n个人不重复就坐的最大方式有多少种吗？

谢谢

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

夜吻♂芭芘 2024-12-09 18:58:51

我们来追溯一下这个问题的解决方案。

首先，让我们看看有多少种方法可以将 n 个人排成一行。我们可以选择将 n 个不同的人放在队伍的前面。剩下的n-1人中，任意n-1人都可以排在第二位。剩下的 n - 2 个中，任意 n - 2 个都可以放到第三个位置，依此类推。更一般地，我们得到公式

排列数量 = nx (n - 1) x (n - 2) x ... x 1 = n！

所以有n个！将人们排成一队的不同方式。更一般地，有 n!对 n 个独特元素重新排序的不同方法。

现在，当我们将人们排列成环时会发生什么？对于每个线性排列，我们可以通过连接两端将该排列转换为环形排列。例如，对于三个人，有六种方法将他们排成一行：

这些映射到以下环：

           1
1 2 3  -> / \
         3---2

           1
1 3 2  -> / \
         2---3

           2
2 1 3  -> / \
         3---1

           2
2 3 1  -> / \
         1---3

           3
3 1 2  -> / \
         2---1

           3
3 2 1  -> / \
         1---2

但是，我们不能由此得出 n 中座位排列的数量！因为我们在这里多次创建了相同的座位安排。作为一个技巧，我们假设我们总是写出循环，使得 1 位于循环的顶部。然后我们生成了以下循环：

           1
1 2 3  -> / \
         3---2

           1
1 3 2  -> / \
         2---3

           1
2 1 3  -> / \
         2---3

           1
2 3 1  -> / \
         3---2

           1
3 1 2  -> / \
         3---2

           1
3 2 1  -> / \
         2---3

请注意，我们生成了以下循环：

   1              1
  / \   x3       / \   x3
 2---3          3---2

所以实际上，只有两种不同的安排；我们刚刚将它们每个生成了三次。

这样做的原因是，由于环没有明确的起点和终点，因此我们最终将生成每种不同排列的多次旋转。特别是，如果我们需要让 n 个人入座，我们最终将生成同一循环的 n 个不同副本，其中每个不同的客人都位于顶部。因此，为了获得每个不同环的客人总数，我们需要忽略除其中一个之外的所有环。由于每个环有 n 个不同的副本，这意味着总数由下式给出

n！ /n=(n-1)！

所以有 (n - 1) 个！将人们围成一圈的不同方式。

希望这有帮助！

Let's trace through the solution to this problem.

First, let's see how many ways we can arrange n people in a line. There are n different people we can choose to put at the front of the line. Of the n - 1 who remain, any n - 1 of them can be put in the second position. Of the n - 2 who remain, any n - 2 of them can be put into the third position, etc. More generally, we get the formula

Num arrangements = n x (n - 1) x (n - 2) x ... x 1 = n!

So there are n! different ways of permuting people in a line. More generally, there are n! different ways to reorder n unique elements.

Now, what happens when we arrange people in a ring? For each linear permutation, we can convert that arrangement into a ring arrangement by connecting the two ends. For example, with three people, there are six ways to order them in a line:

These map to the following rings:

           1
1 2 3  -> / \
         3---2

           1
1 3 2  -> / \
         2---3

           2
2 1 3  -> / \
         3---1

           2
2 3 1  -> / \
         1---3

           3
3 1 2  -> / \
         2---1

           3
3 2 1  -> / \
         1---2

However, we can't conclude from this that the number of seating arrangements in n! because we've created the same seating arrangement multiple times here. As a trick, let's suppose that we always write the cycle out so that 1 is at the top of the cycle. Then we've generated the following cycles:

           1
1 2 3  -> / \
         3---2

           1
1 3 2  -> / \
         2---3

           1
2 1 3  -> / \
         2---3

           1
2 3 1  -> / \
         3---2

           1
3 1 2  -> / \
         3---2

           1
3 2 1  -> / \
         2---3

Notice that we've generated the following:

   1              1
  / \   x3       / \   x3
 2---3          3---2

So really, there are only two different arrangements; we've just generated each of them three times.

The reason for this is that because the ring has no definitive start and end point, we will end up generating multiple rotations of each of the different arrangements. In particular, if there are n people that we need to seat, we'll end up generating n different copies of the same rotation, one with each of the different guests up at the top. Consequently, to get the total number of guests, for each of the different rings, we need to ignore all but one of them. Since there are n different copies of each ring, this means that the total number is given by