1到n的排列组合

niexining

如题，
我写了一个，但可执行性相当差，n大于6时，我的机子就
算不出来了。

niexining

#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)

March.Liu

不要用随机数，大量重复值会造成效率低下，直接轮转法生成，可以参考STL里的算法。
我早年写过一个，下班回去找找还有没有。

ghostwwl

你都没有说清楚，到底是全排列 还是什么有条件的排列

niexining

我说的是全部排列情况。

有效率高的方法吗？     期待中........

wangcn

这篇文章应该对你有帮助
http://www.chinesepython.org/cgi ... e_cf_b7_bf_aa_ca_bc

shhgs

http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/474124

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

flw

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

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

你现在的水平应该不能和 2006.03 比了吧？
以你眼下对 yield 的理解，就算是之前没有见过 Raymond 的作品，也应该能自己写出来了吧？

niexining

shhgs的comb程序，看了一天都没弄明白；一碰上递归的内容，我的头就大了。
perm 程序总算是读下来了。 很精彩！

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

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

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

难道yield在那里很重要，很巧妙吗？

laborcar

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)