樂透必中組合 python

發信人: weijr (Magic Happens), 信區: TnC
標 題: Re: 樂透必中組合產生器
發信站: 透藍的盒子 BBS (Fri Feb 1 15:34:33 2002), 轉信

【 在 weijr (Magic Happens) 的大作中提到: 】
: 練習python用的。貪心算法，共23行。用C可能會快一千倍以上。
果然快一千倍。雖然程式碼長十倍。
另一個版本的python source.

#!/usr/bin/python
import sys
[V,K,T,M]=map(int,sys.argv[1:])
A,mc,mn,num=[],[],1,0
ok=lambda l1,l2:len([i for i in l1 if i in l2])>=T
def try_all(m,n,f,l=[0]):
      if not n: return f(l[1:])
      map(lambda x:try_all(m,n-1,f,l+[x]),xrange(l[-1]+1,m+1))
def find_max(l):
      global mn,mc
      (mn,mc)=max((len([i for i in A if ok(l,i)]),l),(mn,mc))
try_all(V,M,A.append)
while mn:
      (mc,mn,num)=([],0,num+1)
      try_all(V,K,find_max)
      map(A.remove,filter(lambda x:ok(x,mc),A))
      print num,"mc=",mc,"mn=",mn

發信人: weijr (Magic Happens), 信區: TnC
標 題: Re: 樂透必中組合產生器
發信站: 透藍的盒子 BBS (Fri Feb 1 15:34:33 2002), 轉信

【 在 weijr (Magic Happens) 的大作中提到: 】
: 練習python用的。貪心算法，共23行。用C可能會快一千倍以上。
果然快一千倍。雖然程式碼長十倍。
另一個版本的python source.

#!/usr/bin/python
import sys
[V,K,T,M]=map(int,sys.argv[1:])
A,mc,mn,num=[],[],1,0
ok=lambda l1,l2:len([i for i in l1 if i in l2])>=T
def try_all(m,n,f,l=[0]):
      if not n: return f(l[1:])
      map(lambda x:try_all(m,n-1,f,l+[x]),xrange(l[-1]+1,m+1))
def find_max(l):
      global mn,mc
      (mn,mc)=max((len([i for i in A if ok(l,i)]),l),(mn,mc))
try_all(V,M,A.append)
while mn:
      (mc,mn,num)=([],0,num+1)
      try_all(V,K,find_max)
      map(A.remove,filter(lambda x:ok(x,mc),A))
      print num,"mc=",mc,"mn=",mn