1到n的排列组合

1到n的排列组合

如题,
我写了一个,但可执行性相当差,n大于6时,我的机子就
算不出来了。
#function: 1到n的排列组合
#author:whyenglish
#e-mail:0316140111@mail.nuc.edu.cn
#思路:
#因为python每次可产生一随机数,
#让其产生n个随机数到一个list1里
#range(1,n+1)产生1到n,放在list2里
#list2中元素为key, list1中元素为value, 对应到mydict里
#按照values排序,打乱keys, 产生一种排列disorder
#不断产生disorder, 放入ok, 直到ok里有n! 个各不雷同的disorder
import random
from operator import itemgetter
import sys

def sortdictbyvalue(dict):     #按字典values排序
        dict_list=sorted(dict.items(),key=itemgetter(1))
        output=[]
        for i in dict_list:
                output.append(i[0])
        return output
               
def disorder(num):          # 产生一个disorder
               
        #myrand will get a series of rand-number
        myrand=[]
        for i in range(1,num+1):
                r=random.randint(1,num)
                myrand.append(r)
       
        #mirror range(1,num) to myrand, that is, mydict
        mydict={}
        index=0
        mykeys=range(1,num+1)
        for key in mykeys:
                mydict[mykeys[index]]=myrand[index]
                index=index+1
       
        #sort mydict by value, so mykeys isn't in order
        output=sortdictbyvalue(mydict)
       
        return output

def fact(num): #计算n!
        if num==1 or num==0:
                return 1
        else:
                output=num*fact(num-1)
                return output

def ok(num): # 产生n!个disorder
        indu=0
        induok=[]
        while indu < fact(num):
                test=disorder(num)       
                if test not in induok:
                        induok.append(test)
                        indu=indu+1
        print induok
       
if __name__=="__main__":
        num=int(sys.argv[1])
        ok(num)
不要用随机数,大量重复值会造成效率低下,直接轮转法生成,可以参考STL里的算法。
我早年写过一个,下班回去找找还有没有。
你都没有说清楚,到底是全排列 还是什么有条件的排列
我说的是全部排列情况。

有效率高的方法吗?     期待中........
这篇文章应该对你有帮助
http://www.chinesepython.org/cgi ... e_cf_b7_bf_aa_ca_bc


QUOTE:
原帖由 shhgs 于 2007-4-7 22:13 发表
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/474124

下面的评论比我的代码更精彩。Raymond Hettinger,真正的牛人,让我自愧弗如。

你现在的水平应该不能和 2006.03 比了吧?
以你眼下对 yield 的理解,就算是之前没有见过 Raymond 的作品,也应该能自己写出来了吧?
shhgs的comb程序,看了一天都没弄明白;一碰上递归的内容,我的头就大了。
perm 程序总算是读下来了。 很精彩!

Raymond Hettinger 的程序似乎如他所说:“Much simpler and clearer version”; 但又是纯粹递归。

我的脑子可能不具备理解递归的功能......

yield 是第一次见,它似乎和 list 的 append() 方法类似啊,

难道yield在那里很重要,很巧妙吗?
def next(a):
    try:
        i = -2 - [a[k-1]<a[k] for k in range(len(a)-1, 0, -1)].index(True)
        j = -1 - [a[i]<a[k] for k in range(-1, i, -1)].index(True)
        return a[:i] + [a[j]] + a[-1:j:-1] + [a[i]] + a[j-1:i:-1]
    except:
        return None
   
a = [1, 2, 3, 4]
while a:
    print a
    a = next(a)