| 排列组合问题之圆形分布 | 您所在的位置：网站首页 › 排列组合中的环形排列 › 排列组合问题之圆形分布 |
排列组合问题之圆形分布
|
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::vector& vectorPermutation) { //先创建nNum - 1个位的的直线排布 std::vector vectorBallSet(nNum - 1, 0); std::vector vectorBall(nNum - 1, 0); SetBallNum(0, vectorBall, vectorBallSet, vectorPermutation); //然后将nNum - 1的位添加到最后 for (int i = 0; i < vectorPermutation.size(); i++) { vectorPermutation[i].push_back(nNum - 1); } 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::vector vectorPermutation; CreateCirclePermutaion(nSideNum, vectorPermutation); PrintPermutation(vectorPermutation); //{A, B, C, D}对应分布中的{0, 1, 2, 3} //遍历所有的分布 for (int i = 0; i < vectorPermutation.size(); i++) { std::vector& vectorCirclePermutation = vectorPermutation[i]; //根据输入条件做判断 //f(x)+1 = f(y)%4 //D在A的右边，即f(0)+1 = f(3)%4 //如果不满足该条件，则继续下一组 if ((vectorCirclePermutation[0] + 1) != (vectorCirclePermutation[3] % nSideNum)) { continue; } //|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; }
说明：算法实现中是固定最后一位不动的，即D的位置不动，所以最后一位都是3（即D始终在3号位），但该解也是符合原问题的。 |
【本文地址】