代码
比这篇新的文章:
计算python函数性能的小程序
比这篇旧的文章: Python i18n HowTo
作者: 半瓶墨水, 点击858次, 评论(0), 收藏者(1)
打分:
所有评论，共0条：( 我也来说两句)
比这篇旧的文章: Python i18n HowTo
生成四位不重复数字(0-9)的所有组合，比如8765, 9876, 0123
语言: Python, 标签: 猜数字 2008/06/22发布 5个月前更新 更新记录作者: 半瓶墨水, 点击858次, 评论(0), 收藏者(1)
Python语言: 生成四位不重复数字(0-9)的所有组合，比如8765, 9876, 0123
001 #coding=utf-8
002 #
003 #关于这个问题的精彩讨论参见这里
004 # http://groups.google.com/group/python-cn/browse_thread/thread/4d9eda8e422a6cf8
005 #
006 #猜数字游戏8步以内的求解程序的一部分
007 #用来生成四位不重复数字(0-9)的所有组合，比如8765, 9876, 0123
008
009 #用的是最直接的方法，4重for循环：
010 #by realfun
011 def init_set():
012 ret = []
013 for i in range(0, 10):
014 for j in range(0, 10):
015 for k in range(0, 10):
016 for l in range(0, 10):
017 if i != j and i != k and i != l and j != k and j != l and k != l:
018 ret.append((i, j, k, l))
019 return ret
020
021 #改进的4重for，减少判断语句被调用的次数
022 #by Leo Jay
023 def init_set2():
024 ret = []
025 for i in range(0, 10):
026 for j in range(0, 10):
027 if i == j: continue
028 for k in range(0, 10):
029 if j == k: continue
030 for l in range(0, 10):
031 if k == l: continue
032 if i != k and i != l and j != l:
033 ret.append((i, j, k, l))
034 return ret
035
036 #引入set，消除所有的判断语句
037 #by realfun
038 def init_set3():
039 s1 = set(range(0, 10))
040 ret = []
041 for i in s1:
042 s2 = s1.copy()
043 s2.remove(i)
044 for j in s2:
045 s3 = s2.copy()
046 s3.remove(j)
047 for k in s3:
048 s4 = s3.copy()
049 s4.remove(k)
050 for l in s4:
051 ret.append((i, j, k, l))
052 return ret
053
054 #by Nick Cen
055 def perm(items, n=None):
056 if n is None:
057 n = len(items)
058 for i in range(len(items)):
059 v = items[i:i+1]
060 if n == 1:
061 yield v
062 else:
063 rest = items[:i] + items[i+1:]
064 for p in perm(rest, n-1):
065 yield v + p
066
067 #by Nick Cen
068 #递归的方法消除判断语句
069 def init_set4():
070 ret = []
071 for i in perm(range(0,10),4):
072 ret.append(i)
073 return ret
074
075 #展开版，采用init_set3生成，已知程序里面最快的
076 #灭掉了所有的判断语句，同时用展开的方法灭掉了set，目前已知最快的
077 #应该不能更快了，因为这个版本已经没有多余的操作了
078 #by Leo Jay
079 def init_set5():
080 ret = []
081 for i in xrange(0, 10):
082 for j in xrange(i+1, 10):
083 for k in xrange(j+1, 10):
084 for l in xrange(k+1, 10):
085 ret.append((i, j, k, l))
086 ret.append((i, j, l, k))
087 ret.append((i, k, j, l))
088 ret.append((i, k, l, j))
089 ret.append((i, l, j, k))
090 ret.append((i, l, k, j))
091 ret.append((j, i, k, l))
092 ret.append((j, i, l, k))
093 ret.append((j, k, i, l))
094 ret.append((j, k, l, i))
095 ret.append((j, l, i, k))
096 ret.append((j, l, k, i))
097 ret.append((k, i, j, l))
098 ret.append((k, i, l, j))
099 ret.append((k, j, i, l))
100 ret.append((k, j, l, i))
101 ret.append((k, l, i, j))
102 ret.append((k, l, j, i))
103 ret.append((l, i, j, k))
104 ret.append((l, i, k, j))
105 ret.append((l, j, i, k))
106 ret.append((l, j, k, i))
107 ret.append((l, k, i, j))
108 ret.append((l, k, j, i))
109 return ret
110
111 #limodou: 得到一个灵感，可以写一个程序生成的程序，用来生成上面的代码。
112 #Leo Jay: 嘿嘿，实际上这段代码就是自动生成的
113 def gen_fun5():
114 def init_set3():
115 s1 = set(range(0, 4))
116 ret = []
117 for i in s1:
118 s2 = s1.copy()
119 s2.remove(i)
120 for j in s2:
121 s3 = s2.copy()
122 s3.remove(j)
123 for k in s3:
124 s4 = s3.copy()
125 s4.remove(k)
126 for l in s4:
127
128 ret.append((i, j, k, l))
129 return ret
130
131 c = ['i', 'j', 'k', 'l']
132 for i, j, k, l in init_set3():
133 print 'ret.append((%s, %s, %s, %s))' % (c[i], c[j], c[k], c[l])
134
135 #下面的代码用来测试性能
136 import time
137
138 def timing(f, n):
139 print f.__name__, n, "times",
140 r = range(n)
141 t1 = time.clock()
142 for i in r:
143 f()
144 t2 = time.clock()
145 print round(t2-t1, 3)
146
147 #直接的四重for
148 timing(init_set, 1000)
149 #init_set 1000 times 5.624
150
151 #四重for里面每层都加入判断，减少不必要的for
152 timing(init_set2, 1000)
153 #init_set2 1000 times 4.815
154
155 #引入set灭掉所有的判断语句(if语句)
156 timing(init_set3, 1000)
157 #init_set3 1000 times 3.189
158
159 #用递归灭掉所有的判断语句（递归调用开销大啊）
160 timing(init_set4, 1000)
161 #init_set4 1000 times 17.03
162
163 #灭掉了所有的判断语句，同时用展开的方法灭掉了set，目前已知最快的
164 #应该不能更快了，因为这个版本已经没有多余的操作了
165 timing(init_set5, 1000)
166 #init_set5 1000 times 2.024
002 #
003 #关于这个问题的精彩讨论参见这里
004 # http://groups.google.com/group/python-cn/browse_thread/thread/4d9eda8e422a6cf8
005 #
006 #猜数字游戏8步以内的求解程序的一部分
007 #用来生成四位不重复数字(0-9)的所有组合，比如8765, 9876, 0123
008
009 #用的是最直接的方法，4重for循环：
010 #by realfun
011 def init_set():
012 ret = []
013 for i in range(0, 10):
014 for j in range(0, 10):
015 for k in range(0, 10):
016 for l in range(0, 10):
017 if i != j and i != k and i != l and j != k and j != l and k != l:
018 ret.append((i, j, k, l))
019 return ret
020
021 #改进的4重for，减少判断语句被调用的次数
022 #by Leo Jay
023 def init_set2():
024 ret = []
025 for i in range(0, 10):
026 for j in range(0, 10):
027 if i == j: continue
028 for k in range(0, 10):
029 if j == k: continue
030 for l in range(0, 10):
031 if k == l: continue
032 if i != k and i != l and j != l:
033 ret.append((i, j, k, l))
034 return ret
035
036 #引入set，消除所有的判断语句
037 #by realfun
038 def init_set3():
039 s1 = set(range(0, 10))
040 ret = []
041 for i in s1:
042 s2 = s1.copy()
043 s2.remove(i)
044 for j in s2:
045 s3 = s2.copy()
046 s3.remove(j)
047 for k in s3:
048 s4 = s3.copy()
049 s4.remove(k)
050 for l in s4:
051 ret.append((i, j, k, l))
052 return ret
053
054 #by Nick Cen
055 def perm(items, n=None):
056 if n is None:
057 n = len(items)
058 for i in range(len(items)):
059 v = items[i:i+1]
060 if n == 1:
061 yield v
062 else:
063 rest = items[:i] + items[i+1:]
064 for p in perm(rest, n-1):
065 yield v + p
066
067 #by Nick Cen
068 #递归的方法消除判断语句
069 def init_set4():
070 ret = []
071 for i in perm(range(0,10),4):
072 ret.append(i)
073 return ret
074
075 #展开版，采用init_set3生成，已知程序里面最快的
076 #灭掉了所有的判断语句，同时用展开的方法灭掉了set，目前已知最快的
077 #应该不能更快了，因为这个版本已经没有多余的操作了
078 #by Leo Jay
079 def init_set5():
080 ret = []
081 for i in xrange(0, 10):
082 for j in xrange(i+1, 10):
083 for k in xrange(j+1, 10):
084 for l in xrange(k+1, 10):
085 ret.append((i, j, k, l))
086 ret.append((i, j, l, k))
087 ret.append((i, k, j, l))
088 ret.append((i, k, l, j))
089 ret.append((i, l, j, k))
090 ret.append((i, l, k, j))
091 ret.append((j, i, k, l))
092 ret.append((j, i, l, k))
093 ret.append((j, k, i, l))
094 ret.append((j, k, l, i))
095 ret.append((j, l, i, k))
096 ret.append((j, l, k, i))
097 ret.append((k, i, j, l))
098 ret.append((k, i, l, j))
099 ret.append((k, j, i, l))
100 ret.append((k, j, l, i))
101 ret.append((k, l, i, j))
102 ret.append((k, l, j, i))
103 ret.append((l, i, j, k))
104 ret.append((l, i, k, j))
105 ret.append((l, j, i, k))
106 ret.append((l, j, k, i))
107 ret.append((l, k, i, j))
108 ret.append((l, k, j, i))
109 return ret
110
111 #limodou: 得到一个灵感，可以写一个程序生成的程序，用来生成上面的代码。
112 #Leo Jay: 嘿嘿，实际上这段代码就是自动生成的
113 def gen_fun5():
114 def init_set3():
115 s1 = set(range(0, 4))
116 ret = []
117 for i in s1:
118 s2 = s1.copy()
119 s2.remove(i)
120 for j in s2:
121 s3 = s2.copy()
122 s3.remove(j)
123 for k in s3:
124 s4 = s3.copy()
125 s4.remove(k)
126 for l in s4:
127
128 ret.append((i, j, k, l))
129 return ret
130
131 c = ['i', 'j', 'k', 'l']
132 for i, j, k, l in init_set3():
133 print 'ret.append((%s, %s, %s, %s))' % (c[i], c[j], c[k], c[l])
134
135 #下面的代码用来测试性能
136 import time
137
138 def timing(f, n):
139 print f.__name__, n, "times",
140 r = range(n)
141 t1 = time.clock()
142 for i in r:
143 f()
144 t2 = time.clock()
145 print round(t2-t1, 3)
146
147 #直接的四重for
148 timing(init_set, 1000)
149 #init_set 1000 times 5.624
150
151 #四重for里面每层都加入判断，减少不必要的for
152 timing(init_set2, 1000)
153 #init_set2 1000 times 4.815
154
155 #引入set灭掉所有的判断语句(if语句)
156 timing(init_set3, 1000)
157 #init_set3 1000 times 3.189
158
159 #用递归灭掉所有的判断语句（递归调用开销大啊）
160 timing(init_set4, 1000)
161 #init_set4 1000 times 17.03
162
163 #灭掉了所有的判断语句，同时用展开的方法灭掉了set，目前已知最快的
164 #应该不能更快了，因为这个版本已经没有多余的操作了
165 timing(init_set5, 1000)
166 #init_set5 1000 times 2.024
所有评论，共0条：( 我也来说两句)