这是我在论坛上回的一个帖子,感觉很有意思就在这里保存下来,以免丢失! 原贴地址: http://community.csdn.net/Expert/topic/3964/3964967.xml?temp=.7246057 提问(我稍加更改): 做一函数,比如 向函数传入一个6函数计算出5行, 每二个一对,一行3对,一行中必须出现{1,2,3,4,5,6}; 两行中不能有相同的一对! 向函数传入一个 12 则输出11行等等... //例:如6则输出这样内容,每组必须无重复 //则函数计算出5行,每行3对,2个一对,无重复的组合 1-2,3-4,5-6 2-4,3-5,1-6 3-2,4-6,1-5 4-5,3-1,2-6 5-2,1-4,3-6 我的解答: 给搂主一个提议:这是我精心为你设计的一个算法,如果有什么不对的地方,给我发消息! 具体算法步骤: 输入num(偶数)时, 用(x,y)模式表示x-y 弄一个邻居表TA,如下是(1,2,3,4,…,i,i+1,…num)的所有二位组合: p1----> (1,2),(1,3),(1,4)…,(1, num) p2----> (2,3),(2,4)…(2, num) p3----> (3,4),…,(3, num) … pi---->(i,i+1),…,(i,num) … p(num-1)----> (num-1,num) 寻找一组的步骤如下: 初始化:定义集合SA,用来存储已经被包含的x,y,初始化SA={}, 注意:未处理(x1,y1):表示(x1,y1)没有被尝试地包含在SA中,所谓尝试,是因为即使被包含进去,也可能被回滚掉! 第1步,取p1中第一个未处理(1,y1),SA ={1,y1}; 第2步,如果2在SA中,进入第3步, 否则如果p2存在未处理(2,y2),取p2中第一个未处理(2,y2),SA =SA+{2,y2}; 否则如果p2不存在未处理(2,y2),去掉最后加入SA的两个数,然后返回到最后加入元素到SA的那一步; 第3步,如果3在SA中,进入第4步, 否则如果p3存在未处理(3,y3),取p3中第一个未处理(3,y3),SA =SA+{3,y3}; 否则如果p3不存在未处理(3,y3),去掉最后加入SA的两个数,然后返回到最后加入元素到SA的那一步; … 第i步,如果i在SA中,进入第i+1步, 否则如果pi存在未处理(i,yi),取pi中第一个未处理(i,yi),SA =SA+{i,yi}; 否则如果pi不存在未处理(i,yi),去掉最后加入SA的两个数,然后返回到最后加入元素到SA的那一步; … 第num-1步,如果num-1在SA中,进入第num步, 否则如果p(num-1)存在未处理((num-1),y(num-1)),取p(num-1)中第一个未处理((num-1),y(num-1)),SA =SA+{(num-1),y(num-1)}; 否则如果p(num-1)不存在未处理((num-1),y(num-1)),去掉最后加入SA的两个数,然后返回到最后加入元素到SA的那一步; 第num步,如果SA还未全包括{1,2,3,4, …,i,i+1,…num},去掉最后加入SA的两个数,然后返回到最后加入元素到SA的那一步; 否则,假设SA={x1,y1,x2,y2,…},则从邻居表中删除(x1,y1),(x2,y2),…;然后到初始化重新开始寻找下一组,直到邻居表中没有元素! 再给你一个例子: 当为6时, 邻居表, p1----> (1,2),(1,3),(1,4),(1,5),(1,6) p2----> (2,3),(2,4),(2,5),(2,6) p3----> (3,4),(3,5),(3,6) p4----> (4,5),(4,6) p5----> (5,6) 找第1组过程: 第1步,p1取(1,2),SA={1,2}; 第2步, 2在SA中,转下一步; 第3步,p3取 (3,4),SA={1,2,3,4}; 第4步,4在SA中,转下一步; 第5步,p5取 (5,6),SA={1,2,3,4,5,6}; 第6步,得到第一组(1,2),(3,4),(5,6), 从邻居表中删除(1,2),(3,4),(5,6),邻居表变为 p1----> (1,3),(1,4),(1,5),(1,6) p2----> (2,3),(2,4),(2,5),(2,6) p3----> (3,5),(3,6) p4----> (4,5),(4,6) 找第2组过程: 第1步,p1取(1,3),SA={1,3}; 第2步, p2取 (2,4),SA={1,3,2,4}; 第3步,3在SA中,转下一步; 第4步,4在SA中,转下一步; 第5步,p5不存在未处理(5,y5),去掉最后加入SA的两个数,SA={1,3};然后返回到最后加入元素到SA的第2步, 第2步, p2取 (2,5),SA={1,3,2,5}; 第3步,3在SA中,转下一步; 第4步,p2取 (4,6), SA={1,3,2,5,4,6}; 第5步,5在SA中,转下一步 第6步,得到第二组(1,3),(2,5),(4,6), 从邻居表中删除(1,3),(2,5),(4,6),邻居表变为 p1----> (1,4),(1,5),(1,6) p2----> (2,3),(2,4)(2,6) p3----> (3,5),(3,6) p4----> (4,5) 找第3组过程: … 找第4组过程: … 找第5组过程: … p1----> (1,6) p2----> (2,3) p3----> p4----> (4,5) 可以找到5组为 (1,2),(3,4),(5,6) (1,3),(2,5),(4,6) (1,4),(2,6),(3,5) (1,5),(2,4),(3,6) (1,6),(2,3),(4,5) 结果正确吧?

|