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号位），但该解也是符合原问题的。
本文为博主原创文章，如需转载请说明转至
