函数性能：列出四个不重复数字(0-9)的所有组合
realfun
本来是写猜数字游戏完全求解程序的，写到这里发现我用的四层for循环比较慢，在我的双核上面跑100次需要五秒多。
望有人写的更好：
呵呵抛砖希望引来玉啊，更大的砖头也行啊
我的程序段（4层for循环）：
来自：http://www.fayaa.com/code/view/114/
01 #coding=utf-8
02 #猜数字游戏8步以内的求解程序的一部分
03 #用来生成四位不重复数字(0-9)的所有组合，比如8765, 9876, 0123
04 #用的是最直接的方法，4重for循环：
05
06 def init_set():
07 ret = []
08 for i in range(0, 10):
09 for j in range(0, 10):
10 for k in range(0, 10):
11 for l in range(0, 10):
12 if i != j and i != k and i != l and j != k and j != l and k != l:
13 ret.append((i, j, k, l))
14 return ret
15
16 def timing(f, n):
17 print f.__name__, n, "times",
18 r = range(n)
19 t1 = time.clock()
20 for i in r:
21 f()
22 t2 = time.clock()
23 print round(t2-t1, 3)
24
25 timing(init_set, 1000)
--
代码发芽网： http://www.fayaa.com/code/ （无需插件在blog上贴语法高亮的代码，百种语言，多种配色）
我的Blog: http://www.2maomao.com/blog
Leo Jay
> 想要写个小函数用来生成四个数字(0-9)的所有组合，要求四个数字不重复：比如8573, 9876, 0123
> 本来是写猜数字游戏完全求解程序的，写到这里发现我用的四层for循环比较慢，在我的双核上面跑100次需要五秒多。
> 望有人写的更好：
>
> 呵呵抛砖希望引来玉啊，更大的砖头也行啊
>
> 我的程序段（4层for循环）：
> 来自：http://www.fayaa.com/code/view/114/
> 01 #coding=utf-8
> 02 #猜数字游戏8步以内的求解程序的一部分
> 03 #用来生成四位不重复数字(0-9)的所有组合，比如8765, 9876, 0123
> 04 #用的是最直接的方法，4重for循环：
> 05
> 06 def init_set():
> 07 ret = []
> 08 for i in range(0, 10):
> 09 for j in range(0, 10):
这里加一个if i == j: continue
> 10 for k in range(0, 10):
这里加一个if i == k or j == k: continue
> 11 for l in range(0, 10):
> 12 if i != j and i != k and i != l and j != k and j != l
> and k != l:
这里改为if i !=l and j !=l and k != l:
> 13 ret.append((i, j, k, l))
> 14 return ret
> 15
> 16 def timing(f, n):
> 17 print f.__name__, n, "times",
> 18 r = range(n)
> 19 t1 = time.clock()
> 20 for i in r:
> 21 f()
> 22 t2 = time.clock()
> 23 print round(t2-t1, 3)
> 24
> 25 timing(init_set, 1000)
>
> --
> 代码发芽网： http://www.fayaa.com/code/ （无需插件在blog上贴语法高亮的代码，百种语言，多种配色）
> 我的Blog: http://www.2maomao.com/blog
> >
>
--
Best Regards,
Leo Jay
Nick Cen
if n is None:
n = len(items)
for i in range(len(items)):
v = items[i:i+1]
if n == 1:
yield v
else:
rest = items[:i] + items[i+1:]
for p in perm(rest, n-1):
yield v + p
--
http://candynick.vicp.net
realfun
> 09 for j in range(0, 10):这里加一个if i == j: continue
这里加一个if i == k or j == k: continue
> 10 for k in range(0, 10):
这里改为if i !=l and j !=l and k != l:
> 11 for l in range(0, 10):
> 12 if i != j and i != k and i != l and j != k and j != l
> and k != l:
> 13 ret.append((i, j, k, l))
realfun
def perm(items, n=None):
if n is None:
n = len(items)
for i in range(len(items)):
v = items[i:i+1]
if n == 1:
yield v
else:
rest = items[:i] + items[i+1:]
for p in perm(rest, n-1):
yield v + p
Nick Cen
print i
--
http://candynick.vicp.net
xiaq
我忍不住指出楼主应该用 timeit 测试函数性能，python comes with batteries included :)
http://www.woodpecker.org.cn/diveintopython/performance_tuning/timeit.html
realfun
我没有看懂perm函数，只是做了以下测试(timing函数不贴了，参见这里），有误解的地方请指出：
def perm(items, n=None):
if n is None:
n = len(items)
for i in range(len(items)):
v = items[i:i+1]
if n == 1:
yield v
else:
rest = items[:i] + items[i+1:]
for p in perm(rest, n-1):
yield v + p
ret = []
for i in perm(range(0,10),4):
ret.append(i)
return ret
timing(init_set4, 1000)
for i in perm(range(0,10),4):
print i
realfun
可能我用错了。
realfun
#更加改进的四重for，又快了一点儿
def init_set3():
s1 = set(range(0, 10))
ret = []
for i in s1:
s2 = s1.copy()
s2.remove(i)
for j in s2:
s3 = s2.copy()
s3.remove(j)
for k in s3:
s4 = s3.copy()
s4.remove(k)
for l in s4:
ret.append((i, j, k, l))
return ret
xiaq
> 发现这个方法并不快，事实上比起我一开始贴的程序，它需要三倍以上的时间，估计是函数调用开销导致的
> 我没有看懂perm函数，只是做了以下测试(timing函数不贴了，参见这里），有误解的地方请指出：
>
> def perm(items, n=None):
> if n is None:
> n = len(items)
> for i in range(len(items)):
> v = items[i:i+1]
> if n == 1:
> yield v
> else:
> rest = items[:i] + items[i+1:]
> for p in perm(rest, n-1):
> yield v + p
>
> def init_set4():
> ret = []
> for i in perm(range(0,10),4):
> ret.append(i)
> return ret
>
> timing(init_set4, 1000)
n 个元素的 k 元排列可以递归地定义如下：
a) n 个元素的 1 元排列就是从 n 个元素中任取一个元素构成的单元素序列。
b) n 个元素的 k 元排列(k > 1)，是从 n 个元素中任取一个元素，和剩余(n-1)个元素的一个(k-1)元排列连接而成的序列。
是不是太数学形式化了 :)
realfun
归纳的方法一般都是用递归来实现
我贴的最后一个方法也是同样的思想，不过是非递归的
估计是因为：python里面函数调用开销大，所以非递归比递归快很多。
n 个元素的 k 元排列可以递归地定义如下：
a) n 个元素的 1 元排列就是从 n 个元素中任取一个元素构成的单元素序列。
b) n 个元素的 k 元排列(k > 1)，是从 n 个元素中任取一个元素，和剩余(n-1)个元素的一个(k-1)元排列连接而成的序列。
是不是太数学形式化了 :)
limodou
嗯，这么一解释就清楚了:)
归纳的方法一般都是用递归来实现
我贴的最后一个方法也是同样的思想，不过是非递归的
估计是因为：python里面函数调用开销大，所以非递归比递归快很多。
--
I like python!
UliPad <<The Python Editor>>: http://code.google.com/p/ulipad/
UliSpot <<UliPad Snippets>>: http://ulipad.appspot.com
UliWeb <<simple web framework>>: http://uliwebproject.appspot.com
My Blog: (new)http://http://hi.baidu.com/limodou (old)http://www.donews.net/limodou
Leo Jay
> 不断尝试以后，我发现了一个更快的4重for，目前为止最快的（在我的机器上比最初版本快40%左右）
>
试试这个：
ret = []
for i in xrange(0, 10):
for j in xrange(i+1, 10):
for k in xrange(j+1, 10):
for l in xrange(k+1, 10):
ret.append((i, j, k, l))
ret.append((i, j, l, k))
ret.append((i, k, j, l))
ret.append((i, k, l, j))
ret.append((i, l, j, k))
ret.append((i, l, k, j))
ret.append((j, i, k, l))
ret.append((j, i, l, k))
ret.append((j, k, i, l))
ret.append((j, k, l, i))
ret.append((j, l, i, k))
ret.append((j, l, k, i))
ret.append((k, i, j, l))
ret.append((k, i, l, j))
ret.append((k, j, i, l))
ret.append((k, j, l, i))
ret.append((k, l, i, j))
ret.append((k, l, j, i))
ret.append((l, i, j, k))
ret.append((l, i, k, j))
ret.append((l, j, i, k))
ret.append((l, j, k, i))
ret.append((l, k, i, j))
ret.append((l, k, j, i))
return ret
limodou
Leo Jay
嘿嘿，实际上这段代码就是自动生成的：
def init_set3():
s1 = set(range(0, 4))
ret = []
for i in s1:
s2 = s1.copy()
s2.remove(i)
for j in s2:
s3 = s2.copy()
s3.remove(j)
for k in s3:
s4 = s3.copy()
s4.remove(k)
for l in s4:
ret.append((i, j, k, l))
return ret
c = ['i', 'j', 'k', 'l']
for i, j, k, l in init_set3():
print 'ret.append((%s, %s, %s, %s))' % (c[i], c[j], c[k], c[l])
limodou
realfun
嘿嘿，实际上这段代码就是自动生成的：
def init_set3():
s1 = set(range(0, 4))
ret = []
for i in s1:
s2 = s1.copy()
s2.remove(i)
for j in s2:
s3 = s2.copy()
s3.remove(j)
for k in s3:
s4 = s3.copy()
s4.remove(k)
for l in s4:
ret.append((i, j, k, l))return ret
c = ['i', 'j', 'k', 'l']
for i, j, k, l in init_set3():
print 'ret.append((%s, %s, %s, %s))' % (c[i], c[j], c[k], c[l])
--
realfun
靠！这段代码果然是最快的，而且这么生成的话，应该没有错误，我在本地用最初的版本和这个版本对比了一下，这个版本所花的时间在第一个版本的40%左右。
realfun
realfun
直接的四重for
#init_set 1000 times 5.624
四重for里面每层都加入判断，减少不必要的for
#init_set2 1000 times 4.815
引入set灭掉所有的判断语句(if语句)
#init_set3 1000 times 3.189
用递归灭掉所有的判断语句（递归调用开销大啊）
#init_set4 1000 times 17.03
灭掉了所有的判断语句，同时用展开的方法灭掉了set，目前已知最快的应
该不能更快了，因为这个版本已经没有多余的操作了
#init_set5 1000 times 2.024
realfun
lotrpy
realfun
lotrpy
realfun
性能的测试结果数据我都列出来了，不相信的话自己试一下吧
realfun
不知道你是没看懂题目还是怎么回事，如果你看了所有的讨论的话，应该有这样的疑问
性能的测试结果数据我都列出来了，不相信的话自己试一下吧
realfun
lotrpy
realfun
但是，总得照顾点儿"可读性"吧
而且，每次启动程序都要花很多时间初始化...
我把代码放附件里面了。不知道在你机器上速度如何了。
#猜数字游戏8步以内的求解程序的一部分
#用来生成四位不重复数字(0-9)的所有组合，比如8765, 9876, 0123
def init_set6():
return [(0, 1, 2, 3), (0, 1, 2, 4), (0, 1, 2, 5), (0, 1, 2, 6), (0, 1, 2, 7), (0, 1, 2, 8), (0, 1, 2, 9), (0, 1, 3, 2), (0,
......
lotrpy
realfun
但是我不明白的是，你认为Perm好在什么地方？逻辑清晰？可读性好？速度快？
同样的方法，用其他方式一样实现，且不需要递归调用，逻辑也清晰，可读性也还不错，Perm方法的优势在哪里？
看了一下完整的程序，这个初始list是用来猜数字的。在得到第一次猜测结果后再生成init_set如何？(0,1,2,3)得到的结果为xAyB,说明0,1,2,3里面有x+y个数，range(4,9+1)里面有4-(x+y)。或者第一次之后，生成的第一个有效结果为第二次猜测值(这个应该和源程序是同逻辑的)，然后利用前两次的结果，生产可能的结果列表。这时候Perm如何？
Leo Jay
> 你提供的方法不错，虽然从逻辑上来讲，该做的逻辑判断一个也没有少，却可以少分配许多内存
>
> 但是我不明白的是，你认为Perm好在什么地方？逻辑清晰？可读性好？速度快？
> 同样的方法，用其他方式一样实现，且不需要递归调用，逻辑也清晰，可读性也还不错，Perm方法的优势在哪里？
>
我想主要是因为perm函数是一个泛化的函数，比较通用，是从items里选出n个元素。items和n都可以变。
其它的嘛，我不认为它逻辑清晰，可读性好。
@@
马踏飞燕
应该是穷举法吧？
在 08-6-23，realfun<rea...@gmail.com> 写道：
--
免费手机铃声电子书下载，在线观看！
尽在 http://www.honeyday.org
realfun
猜数字游戏的八步以内求解程序: http://www.fayaa.com/code/view/116/
lotrpy
例如 123457698=2x3x3x7x13x23x29x113，所以他的最大值因数是113
总共有362880种可能，从中找出最大值因数最小的数字(结果可能不唯一)？
lotrpy
看起来，台湾论坛上面讨论比较多，结果也很不错。
realfun
realfun写的是猜数字，也就是英文里的mastermind，(mastermind 除了指猜数字，也有指猜球的颜色的)Raymond Hettinger在cookbook写了一篇，http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/496907台湾一个论坛有些中文的讨论，是JAVA的实现。
看起来，台湾论坛上面讨论比较多，结果也很不错。
realfun
举的例子不是很有说服力，对于猜数字，生成所有集，第一次选择以后，后面直接砍就行了，比条件生成要快得多。
举一个简化的例子，先用(0,1,2,3)，得到0A1B，再用(4,5,6,7)得到0A2B，那么，可能的结果(简化情况不考虑位置，只考虑数字)，应该是0到3里面有1个，4到7里面有两个，8和9里面有(4-2-1=1)个。利用Perm可以方便的选数字，组成潜在的结果。 这样要比一开始就生成所有可能的结果(10个数字里面选4个)要少。Perm 我是两年多前在邮件列表看到的，自己也算用过几次。感觉重要的不在递归不递归，而在处理问题的思路。列表里面其它的解答思路从上往下，越来越"具体"，最终收敛到把结果直接存在源代码里面，好处就是快，缺点就是有些"僵化"，预先计算还好，不方便根据当前情况进行调整。记得以前见过一个类似的问题，对由123456789这九个数字组成的9位数进行分解质因数，谁的最大值因数最小呢？
例如 123457698=2x3x3x7x13x23x29x113，所以他的最大值因数是113
总共有362880种可能，从中找出最大值因数最小的数字(结果可能不唯一)？
subowen
002 #关于这个问题的精彩讨论参见这里
003 # http://groups.google.com/group/python-cn/browse_thread/thread/4d9eda8e422a6cf8
004
005 #在我的电脑上
006 #init_set 1000 times 5.529
007 #init_set2 1000 times 4.674
008 #init_set3 1000 times 3.287
009 #init_set4 1000 times 18.271
010 #init_set5 1000 times 2.069
011
012 def init_set8(r10=range(10)):
013 """
014 把循环内的range函数提到外面
015 times5.486 ==> 4.427
016 """
017 ret = []
018 for i in r10:
019 for j in r10:
020 for k in r10:
021 for l in r10:
022 if i != j and i != k and i != l and j != k and j != l and k != l:
023 ret.append((i, j, k, l))
024 return ret
025 timing(init_set8, 1000)
026 def init_set9(r10=range(10)):
027 """
028 for 循环改成列表推导
029 times5.486 ==>3.773
030 """
031 return [(i, j, k, l)
032 for i in r10
033 for j in r10
034 for k in r10
035 for l in r10
036 if ( i != j and i != k and i != l and j != k and j != l and k != l) ]
037 timing(init_set9, 1000)
038
039 def init_set10(r10=range(10)):
040 """
041 return 一个 generator
042 init_set10 1000 times 0.004
043 这个无疑是最快的 :P
044 我最喜欢这个解决方案,空间换时间的算法
045 对这个问题属于 过度优化
046 """
047 return ((i, j, k, l)
048 for i in r10
049 for j in r10
050 for k in r10
051 for l in r10
052 if( i != j and i != k and i != l and j != k and j != l and k != l) )
053 timing(init_set10, 1000)
054
055 def init_set11():
056 """
057 用代码的空间代价换取计算P4_4的时间
058 init_set11 1000 times 7.268 OMG
059 reduce(lambda x,y:x+y,l)太慢了
060 """
061 c10_4=[( i, j, k, l ) for i in xrange(0, 10)
062 for j in xrange(i+1, 10)
063 for k in xrange(j+1, 10)
064 for l in xrange(k+1, 10) ]
065
066 ret=reduce(lambda x,y:x+y,
067 [ [ (i, j, k, l),
068 (i, j, l, k),
069 (i, k, j, l),
070 (i, k, l, j),
071 (i, l, j, k),
072 (i, l, k, j),
073 (j, i, k, l),
074 (j, i, l, k),
075 (j, k, i, l),
076 (j, k, l, i),
077 (j, l, i, k),
078 (j, l, k, i),
079 (k, i, j, l),
080 (k, i, l, j),
081 (k, j, i, l),
082 (k, j, l, i),
083 (k, l, i, j),
084 (k, l, j, i),
085 (l, i, j, k),
086 (l, i, k, j),
087 (l, j, i, k),
088 (l, j, k, i),
089 (l, k, i, j),
090 (l, k, j, i),]
091 for i, j, k, l in c10_4 ],
092 )
093 return ret
094
095 def init_set12():
096 """
097 generator是伟大的发明,数据流编程万岁
098 init_set12 1000 times 1.758
099 """
100 c10_4=(( i, j, k, l ) for i in xrange(0, 10)
101 for j in xrange(i+1, 10)
102 for k in xrange(j+1, 10)
103 for l in xrange(k+1, 10) )
104
105 from itertools import chain
106 ret=chain(
107 *( ( (i, j, k, l),
108 (i, j, l, k),
109 (i, k, j, l),
110 (i, k, l, j),
111 (i, l, j, k),
112 (i, l, k, j),
113 (j, i, k, l),
114 (j, i, l, k),
115 (j, k, i, l),
116 (j, k, l, i),
117 (j, l, i, k),
118 (j, l, k, i),
119 (k, i, j, l),
120 (k, i, l, j),
121 (k, j, i, l),
122 (k, j, l, i),
123 (k, l, i, j),
124 (k, l, j, i),
125 (l, i, j, k),
126 (l, i, k, j),
127 (l, j, i, k),
128 (l, j, k, i),
129 (l, k, i, j),
130 (l, k, j, i),)
131 for i, j, k, l in c10_4 )
132 )
133 return list(ret)
134 timing(init_set12, 1000)
---- --
知止而后有定，定而后能静，静而后能安，安而后能虑，虑而后能得。
realfun
关于生成器那个，其实是把时间成本拖到后面去了，并不快
001 #coding=cp936
002 #关于这个问题的精彩讨论参见这里
003 # http://groups.google.com/group/python-cn/browse_thread/thread/4d9eda8e422a6cf8
004 ...
lotrpy
"处理问题的思路"有道理。
举的例子不是很有说服力，对于猜数字，生成所有集，第一次选择以后，后面直接砍就行了，比条件生成要快得多。
realfun
lotrpy
第一次选择以后，最差的情况都要砍掉60%，后面砍掉的更多，你可以验证试试看
subowen
靠！抛砖引玉引来了流星火雨...:D
关于生成器那个，其实是把时间成本拖到后面去了，并不快
我觉得一般很少有完整生成一个 Pm_n 个元素的列表的需要
xiaq
> 我觉得一般很少有完整生成一个 Pm_n 个元素的列表的需要
> 生成一个generator 再filter是最常见的
> 那个时间 是一种幽默感 :P
>
> 过早的优化是万恶之源
不成功的优化是万恶之源。
subowen
As Knuth famously remarks, "We should forget about small efficiencies, say about 97% of the time: Premature optimization is the root of all evil." ("Computer Programming as an Art" in Literate Programming, CSLI Lecture Notes Number 27, Stanford University Center for the Study of Languages and Information, 1992).
init_set12 优雅的模式
---- --
知止而后有定，定而后能静，静而后能安，安而后能虑，虑而后能得。
subowen
#猜数字游戏8步以内的求解程序
#每次给出结果，要求输入xAyB，比如2A0B这样的结果，不分大小写
#
#解题思路很简单：
#1. 生成所有的四位不重复的0-9的数字组合的集合
#2. 随便找四个数字，比如0123
#3. 根据用户返回结果(xAyB)，砍掉集合里面不符合结果的
#4. 根据现有数字组合，猜下一个，主要技术含量在这里：
# a. 贪心算法，每次都找当前步骤里最优的
# b. "最优"的定义：
# b1. 选择一个组合
# b2. 把这个组合和剩下的组合进行匹配，统计xAyB出现的次数，
# 比如0A0B出现了10次，1A3B出现了0次等等
# b3. 如果xAyB的所有可能出现的机会最为均等，那么这个选择的"区分度"就很大
# 这个可以通过信息量理论进行衡量，也可以简化为通过"最小标准差"来衡量
# b4. 遍历所有组合，找出"区分度"最大的
#5. 重复步骤3, 4，直到用户给出4A0B或者集合里面只剩下一个元素
#
#生成所有的四位不重复的0-9的数字组合
# by Leo Jay
# 灭掉了所有的判断语句，同时用展开的方法灭掉了set，目前已知最快的
# 应该不能更快了，因为这个版本已经没有多余的操作了
#其他方法参见：http://www.fayaa.com/code/view/114/
def init_set():
ret = []
for i in xrange(0, 10):
for j in xrange(i+1, 10):
for k in xrange(j+1, 10):
for l in xrange(k+1, 10):
ret.append((i, j, k, l))
ret.append((i, j, l, k))
ret.append((i, k, j, l))
ret.append((i, k, l, j))
ret.append((i, l, j, k))
ret.append((i, l, k, j))
ret.append((j, i, k, l))
ret.append((j, i, l, k))
ret.append((j, k, i, l))
ret.append((j, k, l, i))
ret.append((j, l, i, k))
ret.append((j, l, k, i))
ret.append((k, i, j, l))
ret.append((k, i, l, j))
ret.append((k, j, i, l))
ret.append((k, j, l, i))
ret.append((k, l, i, j))
ret.append((k, l, j, i))
ret.append((l, i, j, k))
ret.append((l, i, k, j))
ret.append((l, j, i, k))
ret.append((l, j, k, i))
ret.append((l, k, i, j))
ret.append((l, k, j, i))
return ret
#对给定的两组数，计算xAyB
#不知道能不能更快些
def get_match_ab(target, source):
la, lb = 0, 0
for (i, t) in enumerate(target):
for (j, s) in enumerate(source):
if s == t:
if i == j:
la += 1
else:
lb += 1
#break this loop since we already found match
break
return (la, lb)
#检查target与source是否符合aAbB
def match_guess(target, source, a, b):
(la, lb) = get_match_ab(target, source)
return la == a and lb == b
#nums: the number_set list to be checked
#guess: last guess
#a, b: the number of aAbB
#@return: the rest number_sets which matche last guess
def check_and_remove(nums, guess, a, b):
rest_nums = []
for num_set in nums:
if match_guess(num_set, guess, a, b):
rest_nums.append(num_set)
return rest_nums
#计算一个选择相对于选择集的"标准差"
def calc_standard_deviation(target, nums):
#a * 10 + b is used to indicate an "a & b" combination
ab_map = {}
#init ab_map
abs = (0, 1, 2, 3, 4, 10, 11, 12, 13, 20, 21, 22, 30, 31, 40)
for ab in abs:
ab_map[ab] = 0
#let's do the calculation
for num_set in nums:
(a, b) = get_match_ab(num_set, target)
ab_map[a * 10 + b] += 1
ab_counts = [ab_map[ab] for ab in abs]
total = sum(ab_counts)
avg = float(total) / len(abs)
sd = sum([(abc - avg)**2 for abc in ab_counts])
return sd
#根据现有集合寻找下一个集合
#采用"最小标准差"作为衡量标准
def next_guess(nums):
min_sd = 0
min_set = ()
touched = False
for num_set in nums:
sd = calc_standard_deviation(num_set, nums)
if not touched or min_sd > sd:
touched = True
min_set = num_set
min_sd = sd
return min_set
#猜数字的过程
def play():
AN=raw_input('answer? eg. 1840')
def nanb(guess,AN):
"""
每次手动输入1a1b之类一点不好玩
还是pc代劳的好
"""
AN=(map(int,AN))
all=len(set(AN) & set(guess))
a=0
for x,y in zip(AN,guess):
if x==y:a+=1
return "%sa%sb"%(a,all-a)
nums = init_set()
guess = (0, 1, 2, 3)
done = False
retry = 1
while not done:
print retry, u'我猜是：', guess
retry += 1
a, b = 4, 4
while a + b > 4:
#in_str = raw_input(u'请输入这次猜测的结果(xAyB)：'.encode('GBK'))
in_str = nanb(guess,AN)
print (u'这次猜测的结果' +in_str).encode('GBK')
try:
a = int(in_str[0])
b = int(in_str[2])
except:
print u'输入有误，请重新输入'
continue
if a + b > 4:
print u'输入有误，AB数目和大于4了，请重新输入'
nums = check_and_remove(nums, guess, a, b)
if len(nums) <= 0:
break
elif len(nums) == 1:
done = True
else:
print u' 范围缩小到%d个数字了...' % len(nums)
#为了效率所做的妥协:第一次返回结果以后直接取剩下的里面的第一个
#TODO:有时间就来做个全排列证明一下8次以内这种方法可行
#TODO:说不定八次都直接选取第一个就可以，那还要什么算法...:(
if retry < 3:
guess = nums[0]
else:
guess = next_guess(nums)
#拆数字结束了
if done: #出错则为False
print u'搞定! 目标数字是：', nums[0]
else:
print u'您输入的结果中某一步有错误，请检查一下'
print
#来玩玩
while True:
print
print '----------------------------'
print u'猜数字游戏八步以内求解程序'
print u'按 Ctrl + C 退出'
print '----------------------------'
print
play()
---- --
知止而后有定，定而后能静，静而后能安，安而后能虑，虑而后能得。
xiaq
> As Knuth famously remarks, "We should forget about small efficiencies, say
> about 97% of the time: Premature optimization is the root of all evil."
> ("Computer Programming as an Art" in Literate Programming, CSLI Lecture
> Notes Number 27, Stanford University Center for the Study of Languages and
> Information, 1992).
嗯，我觉得 Knuth 的意思应该是"不成熟的优化"
subowen
---- --
知止而后有定，定而后能静，静而后能安，安而后能虑，虑而后能得。
xiaq
realfun
给猜数字的程序提点建议对懒人来说 每次都要 打 1b2b啥的简直是折磨我只试了一次就受不了了(中途还反馈错了)为了方便亲自尝试这个程序的人我修改了一下玩法,你只要把 想的答案 比如1840输入一次就可以看 程序的表演了
realfun
我的想法是：
1. 穷举所有的组合，证明八步以内都可行
2. 把穷举出来的结果做成一颗"推导树"，树的节点是每次的guess，树的分支是根据xAyB决定下一个选择
3. 把"推导树"格式化成嵌套的dict，然后做成网页版:D
@@
另外这还不是最终的目标
我的想法是：
1. 穷举所有的组合，证明八步以内都可行
2. 把穷举出来的结果做成一颗"推导树"，树的节点是每次的guess，树的分支是根据xAyB决定下一个选择
3. 把"推导树"格式化成嵌套的dict，然后做成网页版:D
那个javaworld里不是有个人说做了js版的吗。
realfun
lotrpy
@@
@@
他做的是他的，我做的是我的，每个人都写过hello world，但是还不是一样乐滋滋
恩 那个人说已现在的计算机穷举是不可能的 希望你能证明他是错的。
wangmao
为啥不可能，不就才5040种可能性吗？
@@
> 恩 那个人说已现在的计算机穷举是不可能的 希望你能证明他是错的。
为啥不可能，不就才5040种可能性吗？
是5040种数字组合
不是决策树。。
realfun
我只需要找出一个高度不超过8的决策树就可以了
5040种组合就是5040次，现在跑一次速度也就5s左右
改进一下，应该可以在一个小时内搞定
fluke.l
> 我所说的穷举肯定是可行的，他说不可能估计是指另外的事情
> 我只需要找出一个高度不超过8的决策树就可以了
> 5040种组合就是5040次，现在跑一次速度也就5s左右
> 改进一下，应该可以在一个小时内搞定
>
> 2008/6/23 @@ <ask...@gmail.com <mailto:ask...@gmail.com>>:
>
>
> 2008/6/23 wangmao <lwm...@gmail.com <mailto:lwm...@gmail.com>>:
@@
wangmao
> 我所说的穷举肯定是可行的，他说不可能估计是指另外的事情
> 我只需要找出一个高度不超过8的决策树就可以了
> 5040种组合就是5040次，现在跑一次速度也就5s左右
realfun
realfun
programus
我觉得4位数字的所有组合数目不是很多，应该是五千多个吧......具体的排列公式忘记了。所以，你没有必要每次猜的时候都执行上面的代码。
计算机中不外乎两种情况，1-费CPU，省存储空间，2-费空间，省CPU。既然所有组合的数量不大，何不提前把所有的组合存储在程序中呢？
我当年的实现方法是用类似你上面的程序把所有的数字求出来，放在一个数组里面。
实际猜数字的时候，只需要对这个数组遍历排除即可。速度相当快。呵呵......
实际游戏在下面这两个网址(自己选一个快的)中可以找到，不过貌似没包含源代码......（年代太久远了）
http://download.csdn.net/source/164760
http://www.box.net/shared/o049wg7k8w
On 6月22日, 下午8时56分, realfun <real...@gmail.com> wrote:
> 想要写个小函数用来生成四个数字(0-9)的所有组合，要求四个数字不重复：比如8573, 9876, 0123
> 本来是写猜数字游戏完全求解程序的，写到这里发现我用的四层for循环比较慢，在我的双核上面跑100次需要五秒多。
> 望有人写的更好：
>
> 呵呵抛砖希望引来玉啊，更大的砖头也行啊
>
> 我的程序段（4层for循环）：
> 来自：http://www.fayaa.com/code/view/114/
> 01 #coding=utf-8
> 02 #猜数字游戏8步以内的求解程序的一部分
> 03 #用来生成四位不重复数字(0-9)的所有组合，比如8765, 9876, 0123
> 04 #用的是最直接的方法，4重for循环：
> 05
> 06 def init_set():
> 07 ret = []
> 08 for i in range(0, 10):
> 09 for j in range(0, 10):
> 10 for k in range(0, 10):
> 11 for l in range(0, 10):
> 12 if i != j and i != k and i != l and j != k and j != l
> and k != l:
> 13 ret.append((i, j, k, l))
> 14 return ret
> 15
> 16 def timing(f, n):
> 17 print f.__name__, n, "times",
> 18 r = range(n)
> 19 t1 = time.clock()
> 20 for i in r:
> 21 f()
> 22 t2 = time.clock()
> 23 print round(t2-t1, 3)
> 24
> 25 timing(init_set, 1000)
programus
关于你说的把所有组合都放在程序里影响可读性的问题，我觉得可以考虑以某种格式存在文件里面，程序启动时预读即可（5040个数字，读取必然很快）。
仍然可以保证代码简洁。
你说的这个结果树，让我想起了我当初写的计算任意两个容器倒出任意容积的水的最简方法的程序。跟你现在这个思路一致。呵呵……
有关穷举，猜数字的答案数量确实很小，穷举没问题。不知道你想过打飞机游戏怎么写没。就是那个10x10矩阵里面摆三架“士”字形飞机的游戏。
我曾试图用与解猜数字相同的方法来做，预生成所有解决最终答案，然后穷举排除。但是失败了。
只是列出所有可能局，就花去了若干小时的计算时间……
> 2008/6/23 wangmao <lwm3...@gmail.com>:
realfun
程序读文件并不一定比生成来的快，上面讨论的各种方法在100毫秒内都可以搞定，也不是很慢。
其实就像有些朋友说的那样，优化这里并没有多少意义，不过整个讨论过程让我很是开心，受益良多
原来我上面提到的方法已经讨论过了，不好意思刚刚只看第一页了。
关于你说的把所有组合都放在程序里影响可读性的问题，我觉得可以考虑以某种格式存在文件里面，程序启动时预读即可（5040个数字，读取必然很快）。
仍然可以保证代码简洁。
你说的这个结果树，让我想起了我当初写的计算任意两个容器倒出任意容积的水的最简方法的程序。跟你现在这个思路一致。呵呵……
有关穷举，猜数字的答案数量确实很小，穷举没问题。不知道你想过打飞机游戏怎么写没。就是那个10x10矩阵里面摆三架"士"字形飞机的游戏。
我曾试图用与解猜数字相同的方法来做，预生成所有解决最终答案，然后穷举排除。但是失败了。
只是列出所有可能局，就花去了若干小时的计算时间……
BearXu
2008/6/23 realfun <rea...@gmail.com>:
BearXu
realfun
程序执行在十秒之内，让偶十分诧异...最终发现有5个元组需要9次才能完成
明天再用最小标准差选择法试试看
realfun
明天跑跑全部使用最小标准差算法，或者更变态的，信息量算法，zｚZＺ
目前的代码参见：
猜数字游戏8步以内的完全求解决策树生成程序
http://www.fayaa.com/code/view/128/
使用方法：保存程guessall.py，执行python guessall.py > result.txt，然后打开result.txt看结果
已经用最简单的选择法得到了一个决策树
程序执行在十秒之内，让偶十分诧异...最终发现有5个元组需要9次才能完成
明天再用最小标准差选择法试试看
realfun
max level is: 8
level7 plus tuples:
level: 8 tup: (9, 8, 3, 5)
level: 8 tup: (9, 2, 0, 3)
level: 8 tup: (0, 3, 9, 2)
realfun
生成的结果参见附件
嗯，周末考虑用生成的结果做个web小程序。
这回真的zｚZＺ
nnd，等不及了，试了完全使用最小标准差算法，二十几秒，还是有3个元组需要8次才能完成：
max level is: 8
level7 plus tuples:
level: 8 tup: (9, 8, 3, 5)
level: 8 tup: (9, 2, 0, 3)
level: 8 tup: (0, 3, 9, 2)
limodou
--
I like python!
UliPad <<The Python Editor>>: http://code.google.com/p/ulipad/
UliWeb <<simple web framework>>: http://uliwebproject.appspot.com
My Blog: (new)http://http://hi.baidu.com/limodou (old)http://www.donews.net/limodou
BearXu
2008/6/24 limodou <lim...@gmail.com>:
boa
2008/6/22 realfun <rea...@gmail.com>:
> 不断尝试以后，我发现了一个更快的4重for，目前为止最快的（在我的机器上比最初版本快40%左右）
>
试试这个：
ret = []
for i in xrange(0, 10):
for j in xrange(i+1, 10):
for k in xrange(j+1, 10):
for l in xrange(k+1, 10):
ret.append((i, j, k, l))
ret.append((i, j, l, k))
ret.append((i, k, j, l))
ret.append((i, k, l, j))
ret.append((i, l, j, k))
ret.append((i, l, k, j))
ret.append((j, i, k, l))
ret.append((j, i, l, k))
ret.append((j, k, i, l))
ret.append((j, k, l, i))
ret.append((j, l, i, k))
ret.append((j, l, k, i))
ret.append((k, i, j, l))
ret.append((k, i, l, j))
ret.append((k, j, i, l))
ret.append((k, j, l, i))
ret.append((k, l, i, j))
ret.append((k, l, j, i))
ret.append((l, i, j, k))
ret.append((l, i, k, j))
ret.append((l, j, i, k))
ret.append((l, j, k, i))
ret.append((l, k, i, j))
ret.append((l, k, j, i))
return ret
--
Best Regards,
Leo Jay
@@
boa
這是我把寫彩票中的一段拿出來改的，其中List1，List2，List3，List4可以在使用前更改包含的數字。不過這段速度是慢了好多。
def init_set():
List2 = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '0']
List3 = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '0']
List4 = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '0']
tmpList = [[List1[x], List2[y], List3[z], List4[m]]
for x in range(len(List1))
for y in range(len(List2))
for z in range(len(List3))
for m in range(len(List4))]
tmpList.sort()
sencList = []
for evrNum in tmpList:
if evrNum[0] < evrNum[1] and evrNum[1] < evrNum[2] and \
evrNum[2] < evrNum[3]:
if evrNum not in sencList:
sencList.append(evrNum)
return sencList
BearXu
2008/6/24 boa <zuggi...@gmail.com>:
k
Sudo
ret = []
digits = range(10)
for i in digits[:]:
for j in digits[i+1:]:
for k in digits[j+1:]:
for l in digits[k+1:]:
ret += [(i, j, k, l), (i, j, l, k),
(i, k, j, l), (i, k, l, j),
(i, l, j, k), (i, l, k, j),
(j, i, k, l), (j, i, l, k),
(j, k, i, l), (j, k, l, i),
(j, l, i, k), (j, l, k, i),
(k, i, j, l), (k, i, l, j),
(k, j, i, l), (k, j, l, i),
(k, l, i, j), (k, l, j, i),
(l, i, j, k), (l, i, k, j),
(l, j, i, k), (l, j, k, i),
(l, k, i, j), (l, k, j, i)]
return ret
realfun
囧匡
Davies Liu
闲来无事我也来凑一下热闹，用未经过特殊优化的递归代码实现，穷举所有猜数字过程也只需要二十几秒，生成器的优势还是很明显的。
算法的优劣起决定作用，实现次之。
if len(l) <= 1:
yield l
else:
for i in l:
for r in perm([j for j in l if j != i]):
yield [i]+r
def comb(l, n):
if n==0:
yield []
else:
for i in range(len(l)-n+1):
for r in comb(l[i+1:], n-1):
yield [l[i]]+r
def compare(n,m):
a = sum(n[i]==m[i] for i in range(len(n)))
b = sum(1 for i in n if i in m)
return a,b
def guess(n):
answer = []
for c in comb(range(10),4):
for g,a,b in answer:
if compare(c,g)[1] != b:
break
else:
for p in perm(c):
if p[0] == 0:continue
for g,a,b in answer:
if compare(p,g) != (a,b):
break
else:
yield p
a,b = compare(p,n)
answer.append((p,a,b))
if answer[-1][1] == 4:
return
print list(guess([6,8,9,7]))
for p in sum([list(perm(p)) for p in comb(range(10),4)], []):
if p[0] == 0: continue
answer = list(guess(p))
assert answer[-1] == p
if len(answer)>7:
print len(answer),p
Best regards,
Davies Liu
cx
On 6月23日, 上午12时00分, realfun <real...@gmail.com> wrote:
> 注意标题，这里注重的是性能
>
> 2008/6/22 lotrpy <lot...@gmail.com>:
>
> > 显然是perm的那个好啊，一看就是大家作品。
wangmao
"列出五个不重复数字(0-9)的所有组合"
"列出六个不重复数字(0-9)的所有组合"