心得经验总结：排列组合问题之圆形分布

1、问题

1.1 团团坐

有一张圆桌，坐了A,B,C,D四个人，已知，D在A的右边，C在D的对面，请问A,B,C,D,的坐次？

解答：这个问题相对简单，我们纸上画一画，就能画出他们的可能的位置了

但是，可能还有一种解，比如我们把A,B,C,D依次右转一个位，也是满足条件的，而且只要保持他们的相对位置不变，依次右转n个位都是问题的解，而且还有个有趣的事情，当他们转了一圈（即右转4个位）后，他们右回到原位了

2、圆形分布

上面这个问题就是一种圆形分布，那么他和直线分布的区别在哪里呢？又有什么联系呢？

上面文章《排列组合问题之线型排列》中讲过，当有4个球时，可能的排列共有4! = 24种，那么我们把A,B,C,D四个人的坐位分别标为{0, 1, 2, 3}的号，那么A,B,C,D四个人可能坐的位置就是一个线型排列。

假设我们用计算机来解析这个问题，给出一种可能的分布方式。我们的思路是：

1> 列出所有可能的分布

2> 然后解析每种组合是否满足题目的要求

当然，我们也可以每找到一种组合，就判断一次是否满足题目的要求，这样找到一种后就可以退出了，可以减少时间复杂度。

如果我们按线型排列处理，我们一共需要找出24种排列出来，根据前面的解析可知，某一种排列还有3种排列都可以满足题目的解得，我们只需要求出一种解即可，找出24种比较费时间，而且当问题复杂化后，比如是一个16边形的桌子，给出上述类似的问题，那么最坏情况下共需要列出16!=20922789888000种可能，如果我们能够去掉其中重复的，就可以减少计算。如我们这里实际只需要列出24 / 4 = 6种分布即可

3、如何找出线型分布中不一样的分布

我们再来看看问题的解答：A,B,C,D四个人的坐次 = {0, 2, 3, 1}

假设A固定不动，那么B, C, D可能的坐次仍是一个线型分布，即共有3!=6种，因为A不动，所有B,C,D不可能发生转动了，所以不会有上面多个解的问题

这时我们每右转一次A，那么上面的6种分布又可以得到新的6种线型分布，但他们和转动前的分布都是问题的解（因为他们的相对位置不变，而问题给出的条件是相对位置），所以对于圆形分布，即是把线型分布的首位连接成一个圆，圆转动后他们的位置仍然会保持相对不变，那么我们只需要求出A=0,{B,C,D}的线型分布组合起来的解，就可以用来判定题目给出的条件

4、圆形分布算法

为了减少篇幅，创建线型分布的函数 SetBallNum() 见《排列组合问题之线型排列》

为了处理方便，重复利用代码，生成圆形分布时，我们是固定最后一位不动的，即D的位置不动

bool CPermutation::CreateCirclePermutaion(int nNum, std::vectorint vectorPermutation)

{

//先创建nNum - 1个位的的直线排布

std::vector[span style="color: rgba(0, 0, 255, 1)">int

std::vector[span style="color: rgba(0, 0, 255, 1)">int

SetBallNum(0, vectorBall, vectorBallSet, vectorPermutation);

//然后将nNum - 1的位添加到最后

for (int i = 0; i < vectorPermutation.size(); i++)

{

vectorPermutation【i】.push_back(nNum - 1);

}//代码效果参考：http://www.ezhiqi.com/bx/art_6227.html

return true;

}

说明:为了减少代码，处理方便，算法中用到了STL的vector容器，需要少许STL容器使用的相关知识，当然用数组也是可以实现的，代码会略麻烦

5、如何表达A,B,C,D的相对位置

5.1 什么是x在y的右边？

我们来换一张相对好看一点的图：

图中B在A的右边，他们的位置是(0, 1)，C在B的右边他们的位置是(1, 2)....

A, B

B, C

C, D

D, A

相对位置

(0, 1)

(1, 2)

(2, 3)

(3, 0)

通过C之前的位置我们可以总结出，所谓x在y的右边就是f(x)+1 = f(y)，这里f(x)是指x的位置号。

但当到D后，我们发现上面这个公式不适用了A也在D的右边，但他们的位置却是(3, 0)，该如何处理这种情况？

我们再仔细看，当到D后，他的右边的位置理应是4，但由于是圆形分布，最后一位和第一位首位相接了，这实际上就和时钟转满了一圈是一样的，这时4要变成0了，这实际就是一个模的运算，取其余数即可，即：

f(x)+1 = f(y)%4 = f(y)%桌子的边数

5.2 什么是x在y的对面？

再看一次上面那张图， C在A的对面，他们的位置是(0, 2)，D在B的对面，他们的位置是(1, 3)，因为如果2个人相对，那么他们之间就隔了一半的人

于是我们能总结出公式：f(y)-fx(x) = 4 / 2 = 2

但是又发现也可以说A在C的对面，f(a)-f(c) = -2,修改下公式：

|f(y)-f(x)| = 2 = 4 / 2 = 桌子的边数/2

6、自动判断算法

bool CPermutation::TestCircleDesk()

{

int nSideNum = 4;

std::vectorint vectorPermutation;

CreateCirclePermutaion(nSideNum, vectorPermutation);

PrintPermutation(vectorPermutation);

//{A, B, C, D}对应分布中的{0, 1, 2, 3}

//遍历所有的分布

for (int i = 0; i < vectorPermutation.size(); i++)

{

std::vector[span style="color: rgba(0, 0, 255, 1)">int

//根据输入条件做判断

//f(x)+1 = f(y)%4

//D在A的右边，即f(0)+1 = f(3)%4

//如果不满足该条件，则继续下一组

if ((vectorCirclePermutation【0】 + 1) != (vectorCirclePermutation【3】 % nSideNum))

{

continue;

}//代码效果参考：http://www.ezhiqi.com/zx/art_7644.html

//|f(y)-f(x)| = 2 = 4 / 2

//C在D的对面，即|f(2)-f(3)| = 2 = 4 / 2

if (abs(vectorCirclePermutation【2】 - vectorCirclePermutation【3】) == nSideNum / 2)

{

printf("Find matched permutation : ");

for (int j = 0; j < nSideNum; j++)

{

printf("%d ", vectorCirclePermutation【j】);

}

printf("\n");

return true;

}

}

return false;

}//代码效果参考：http://www.ezhiqi.com/bx/art_961.html

说明：算法实现中是固定最后一位不动的，即D的位置不动，所以最后一位都是3（即D始终在3号位），但该解也是符合原问题的。

本文为博主原创文章，如需转载请说明转至