这是一个纯暴力、天真的方法,有4个嵌套循环:
LETTERS = 'bcdfghjklmnpqrstvwxz'
DIGITS = '2456789'
from itertools import permutations
def aab12_1(letters=LETTERS, digits=DIGITS):
st=[]
for fc in letters:
for sc in letters:
if sc==fc: continue
for n1 in digits:
for n2 in digits:
if n1==n2: continue
st.append(''.join((fc,fc,sc,n1,n2)))
di={e:[''.join(t) for t in permutations(e)] for e in st}
return {s for sl in di.values() for s in sl}
>>> r=aab12_1()
>>> len(r)
478800
这已经
O(n**4)
复杂性;即,
真的很糟糕
您可以通过对生成的基本字符串进行排序来减少对的重复调用,从而降低复杂性
permutations
:
def aab12_2(letters=LETTERS, digits=DIGITS):
st=set()
for fc in letters:
for sc in letters:
if sc==fc: continue
for n1 in digits:
for n2 in digits:
if n1==n2: continue
st.add(''.join(sorted((fc,fc,sc,n1,n2))))
di={e:[''.join(t) for t in permutations(e)] for e in st}
return {s for sl in di.values() for s in sl}
from itertools import permutations, product, combinations
def aab12_3(letters=LETTERS, digits=DIGITS):
let_combo=[x+y for x,y in product([e+e for e in letters],letters) if x[0]!=y]
n_combos={a+b for a,b in combinations(digits,2)}
di={e:[''.join(t) for t in permutations(e)] for e in (x+y for x,y in product(let_combo, n_combos))}
return {s for sl in di.values() for s in sl}
这仍然隐含着
O(n**3)
与3
products()
这相当于每个循环的嵌套循环。每个
O
所以,让我们做个基准测试。下面是上面的3个函数:Ajax1234的递归函数和Rory Daulton的itertools函数:
from itertools import combinations, permutations, product
def aab12_1(letters=LETTERS, digits=DIGITS):
st=[]
for fc in letters:
for sc in letters:
if sc==fc: continue
for n1 in digits:
for n2 in digits:
if n1==n2: continue
st.append(''.join((fc,fc,sc,n1,n2)))
di={e:[''.join(t) for t in permutations(e)] for e in st}
return {s for sl in di.values() for s in sl}
def aab12_2(letters=LETTERS, digits=DIGITS):
st=set()
for fc in letters:
for sc in letters:
if sc==fc: continue
for n1 in digits:
for n2 in digits:
if n1==n2: continue
st.add(''.join(sorted((fc,fc,sc,n1,n2))))
di={e:[''.join(t) for t in permutations(e)] for e in st}
return {s for sl in di.values() for s in sl}
def aab12_3(letters=LETTERS, digits=DIGITS):
let_combo=[x+y for x,y in product([e+e for e in letters],letters) if x[0]!=y]
n_combos={a+b for a,b in combinations(digits,2)}
di={e:[''.join(t) for t in permutations(e)] for e in (x+y for x,y in product(let_combo, n_combos))}
return {s for sl in di.values() for s in sl}
def aab12_4():
def validate(val, queue, counter):
if not queue:
return True
if val.isdigit():
return sum(i.isdigit() for i in queue) < 2 and val not in queue
_sum = sum(i.isalpha() for i in counter)
return _sum < 3 and counter.get(val, 0) < 2
def is_valid(_input):
d = Counter(_input)
return sum(i.isdigit() for i in d) == 2 and sum(i.isalpha() for i in d) == 2
def combinations(d, current = []):
if len(current) == 5:
yield ''.join(current)
else:
for i in d:
if validate(i, current, Counter(current)):
yield from combinations(d, current+[i])
return [i for i in combinations(DIGITS+LETTERS) if is_valid(i)]
def aab12_5(letters=LETTERS, digits=DIGITS):
""" Rory Daulton
Generate the distinct 5-character strings consisting of three
letters (two are equal and a repeated letter) and two digits (each
one is different from the other).
"""
indices = range(5)
combs = []
for (letterdbl, lettersngl), (digit1, digit2), (indx1, indx2, indx3) in (
product(permutations(letters, 2),
combinations(digits, 2),
permutations(indices, 3))):
charlist = [letterdbl] * 5
charlist[indx1] = lettersngl
charlist[indx2] = digit1
charlist[indx3] = digit2
combs.append(''.join(charlist))
return combs
if __name__=='__main__':
import timeit
funcs=(aab12_1,aab12_2,aab12_3,aab12_4,aab12_5)
di={f.__name__:len(set(f())) for f in funcs}
print(di)
for f in funcs:
print(" {:^10s}{:.4f} secs".format(f.__name__, timeit.timeit("f()", setup="from __main__ import f", number=1)))
印刷品:
{'aab12_1': 478800, 'aab12_2': 478800, 'aab12_3': 478800, 'aab12_4': 478800, 'aab12_5': 478800}
aab12_1 0.6230 secs
aab12_2 0.3433 secs
aab12_3 0.3292 secs
aab12_4 50.4786 secs
aab12_5 0.2094 secs
