【正确答案】打印数字的排列组合方式的最简单的方法就是递归，但本题存在两个难点：第一，数字中存在重复数字，第二，明确规定了某些位的特性。显然，采用常规的求解方法似乎不能完全适用了。
其实，可以换一种思维，把求解这6个数字的排列组合问题转换为大家都熟悉的图的遍历的问题，解答起来就容易多了。可以把1、2、2、3、4、5这6个数看成是图的6个结点，对这6个结点两两相连可以组成一个无向连通图，这6个数对应的全排列等价于从这个图中各个结点出发深度优先遍历这个图中所有可能路径所组成的数字集合。例如，从结点“1”出发所有的遍历路径组成了以“1”开头的所有数字的组合。由于“3”与“5”不能相连，因此，在构造图的时候使图中“3”和“5”对应的结点不连通就可以满足这个条件。对于“4”不能在第三位，可以在遍历结束后判断是否满足这个条件。
具体而言，实现步骤如下所示：
(1)用1、2、2、3、4、5这6个数作为6个结点，构造一个无向连通图。除了“3”与“5”不连通外，其他的所有结点都两两相连。
(2)分别从这6个结点出发对图做深度优先遍历。每次遍历完所有结点的时候，把遍历的路径对应数字的组合记录下来，如果这个数字的第三位不是“4”，那么把这个数字存放到集合Set中(由于这6个数中有重复的数，因此，最终的组合肯定也会有重复的。由于集合Set的特点为集合中的元素是唯一的，不能有重复的元素，因此，通过把组合的结果放到Set中可以过滤掉重复的组合)。
(3)遍历Set集合，打印出集合中所有的结果，这些结果就是本问题的答案。
实现代码如下：
class Test:
def __init__(self,arr):
#self.numbers=[1,2,2,3,4,5]
self.numbers=arr
#用来标记图中结点是否被遍历过
self.visited=[None]*len(self.numbers)
#图的二维数组表示
self.graph=[([None]*len(self.numbers)) for i in range(len(self.numbers))]
self.n=6
#用来标记图中结点是否被遍历过
#self.visited=None
#图的二维数组表示
#self.graph=None
#数字的组合
self.combination="
#存放所有的组合
self.s=set()
"""
**方法功能: 对图从结点start位置开始进行深度遍历
**输入参数: start:遍历的起始位置
"""
def depthFirstSearch(self,start):
self.visited[start]=True
self.combination+=str(self.numbers[start])
if len(self.combination)==self.n:
#4不出现在第三个位置
if self.combination.index("4")!=2:
self.s.add((self.combination))
j=0
while j＜self.n:
if self.graph[start][j]==1 and self.visited[j]=False:
self.depthFirstSearch(j)
j+=1
self.combination=self.combination[:-1]
self.visited[start]=False
#方法功能:获取1、2、2、3、4、5的左右组合,使得"4"不能在第三位,"3"与"5"不能相连
def getAllCombinations(self):
#构造图
i=0
while i＜self,n:
j=0
while j＜self.n:
if i==j:
self.graph[i][j]=0
else:
self.graph[i][j]=1
j+=1
i+=1
#确保在遍历的时候3与5是不可达的
self.graph[3][5]=0
self.graph[5][3]=0
#分别从不同的结点出发深度遍历图
i=0
while i＜self.n:
self.depthFirstSearch(i)
i+=1
def printAllCombinations(self):
for strs in self.s:
print strs,
if __name__=="__main__":
arr=[1,2,2,3,4,5]
t=Test(arr)
t.getAllCombinations()
#打印所有组合
t.printAllCombinations()
由于结果过多，因此这里就不列出详细的运行结果了。