Given a round table, with N male and N female guests（1 < N < 10）, how many ways we can arrange them such that the sexes alternate?

Sample Input:

N = 3

Sample Output:

12

Intuition 1:

• Since there are 6 person and 3 groups, for each group one male and one female, to pick the first male there are 3 options, same with the first female. Now we have 3 x 3.
• For the second group, we have 2 options for both the male and female, so we have 2 x 2 for this group. Add up to the first group, we end up with 3 x 3 x 2 x 2.
• For the third group, we only have one option for both the male and female. Now we have 3 x 3 x 2 x 2 x 1 x 1.
• Since we have a round table, when the three groups swift position it won’t impact the final result. So we need to divide the previous result by 3.
• Finally what we have is: ( 3 x 3 x 2 x 2 x 1 x 1 ) / 3 = 12

Intuition 2:

• To get rid of the impact of round table, we can pick one male as the anchor person who will not move seat, then the next must be the opposite sex, which has 3 options.
• The next person is the same sex, which has 2 options. So we have 3 x 2 by now.
• The next person is the opposite sex, which has 2 options. Now we have 3 x 2 x 2.
• For the remaining two person we only have 1 option for each. So the final result is 3 x 2 x 2 x 1 x 1 = 12.

数据结构和算法：初级练习题 #59 阶乘和排列 （三）

给定一张圆桌，安排N位男士和N位女士就座（1 < N < 10），如果男女需要间隔就座，总共有多少种安排方式？

输入样例：

N = 3

输出样例：

12

算法思路之一：

• 六位客人因为需要男女间隔就座，所以总共有三组，每组一位男士一位女士。选择第一组的男士和女士，我们都有三个选择，所以变化是 3 x 3。
• 选择第二组的男士和女士，我们都有两个选择，所以变化是 2 x 2。加上第一组的变化，现在总共的变化是 3 x 3 x 2 x 2。
• 选择第三组我们都只剩下一个选择，所以这时的变化是 3 x 3 x 2 x 2 x 1` x 1。
• 考虑到圆桌就座，三组客人如果转动位置是不影响最后的结果，也就是说前面的变化中需要除以3。
• 最后的结果就是：3 x 3 x 2 x 2 x 1 x 1 / 3 = 12。

算法思路之二：

• 为了避免圆桌移位的影响，我们可以先选择一位客人作为固定位置不变，然后逐一选择其他位置的客人。
• 任意选择一位男士作为第一个就座的客人，这时同组的女士有三种选择。这时的变化是 1 x 3。
• 接下来选择第二组的男士和女士，分别都有两种选择。这时加上前面第一组，我们的变化是 3 x 2 x 2 x 1。
• 最后一组的两位客人都只有一个选择，所以最后的结果就是 3 x 2 x 2 x 1 x 1 x 1 = 12。

Python Solution