昨天上午去面試的一道題，當(dāng)場沒想出來，回來花了點(diǎn)時(shí)間補(bǔ)完了下發(fā)回去.
原題要求用java，用python只是為了方便。用回溯法快，但是還是堅(jiān)持用遍歷森林來寫，這也是面試時(shí)沒想完的思路，呵呵，我就是自找麻煩的硬石頭性格。
最先想到用無向連通圖進(jìn)行深度優(yōu)先搜索，但是沒有考慮到結(jié)束條件。對于N個待排列的數(shù)字，每個節(jié)點(diǎn)都有N-1個出口和入口，而用樹狀結(jié)構(gòu)每個節(jié)點(diǎn)只有一個父節(jié)點(diǎn)，存在遞歸返回的條件。但是這個方法的實(shí)用性只限制在當(dāng)排列數(shù)很少（N < 8）時(shí)。當(dāng)N>8時(shí)算法消耗的時(shí)間明顯增加(一共8*7*6*5*4*3*2*1=40320種組合)，當(dāng)N>1000時(shí)(當(dāng)然，這種情況是不敢想像的)就會達(dá)到python的遞歸極限。所以真正如果要干點(diǎn)什么的話(當(dāng)然，高中生都知道全排列拿52張撲克牌出來排一下結(jié)果集就是個天文數(shù)字)，這顯然不是個好算法。
#coding=utf-8
# 數(shù)字全排列
# Chris Zheng 2007-06-05
import sys, os
#待排列的數(shù)字
NUMS = [1,2,3,4,5,6]
#結(jié)果集合
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是否同時(shí)符合特定位置
)
# 3和4不能相鄰 當(dāng)2在第1時(shí)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
#樹節(jié)點(diǎn)
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))
#生成結(jié)果樹
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
#遍歷結(jié)果樹
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()
.