# where the amazing happens

## 全排列和其他

#coding=utf-8

# 数字全排列
#
Chris Zheng 2007-06-05

import sys, os

#待排列的数字
NUMS = [1,2,3,4,5,6]

#结果集合
results = []

EXCLUDES
= (
lambda a,b,nums:abs(nums.index(a) - nums.index(b)) == 1, #a,b是否相邻
lambda a,b,idx_a,idx_b,nums:nums.index(a) == idx_a and nums.index(b) \
== idx_b #a,b是否同时符合特定位置
)

# 3和4不能相邻 当2在第1时6不能在第7
EXT_PARAMS = (
(
3,4,NUMS),(2,6,1,7,NUMS)
)

#检查排除条件
def __check_conditions(nums):
matchs
= False
for f in EXCLUDES:
for params in EXT_PARAMS:
try:
params[
-1] = nums
matchs
= f(*params)
if matchs: return matchs
except Exception:continue
return matchs

#树节点
class node(object):
def __init__(self, n):
self.value
= n
self.parent
= None
self.children
= []
def __eq__(self,other):
return self.value == other.value
def __str__(self):return str(self.value)

#主方法
def get_all(nums):
trees
= []
for n in nums:
trees.append(create_tree(node(n)))
for t in trees:
walk_tree(t)
global results
#过滤条件
return (r for r in results if not __check_conditions(r))

#生成结果树
def create_tree(root):
parent_elements
= __parents(root)
if len(parent_elements) == len(NUMS)+1:return root
nums
= (nums for nums in NUMS if node(nums) not in parent_elements)
for k in nums:
c
= node(k)
c.parent
= root
root.children.append(create_tree(c))
return root

def __parents(node):
parent_elements
= [node]
while node.parent:
parent_elements.append(node.parent)
node
= node.parent
return parent_elements

#遍历结果树
def walk_tree(root):
if root.children:
for n in root.children:
walk_tree(n)
else:
k
= [root.value]
p
= root.parent
while p:
k.append(p.value)
p
= p.parent
k.reverse()
results.append(k)

#测试输出
if __name__=='__main__':
rs
= get_all(NUMS)
f
= open('results.txt','w')
for k in rs:
f.write(str(k)
+'\n')
f.close()

.

posted on 2007-06-05 14:47 where the amazing happens 阅读(403) 评论(0)  编辑  收藏 所属分类: 算法&数据结构

 只有注册用户登录后才能发表评论。 网站导航: 相关文章:

### 导航

 < 2007年6月 >
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

• 随笔 - 17
• 文章 - 17
• 评论 - 22
• 引用 - 0

•