def words(alphabet):
yield ''
for prefix in words(alphabet):
for characterletter in alphabet:
yield prefix + characterletter
from itertools import product, count, islice, chain
from timeit import repeat
from collections import deque
lib = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz°!"§$%&/()=ß ́`+#-.,><@€|^~–{[]}ÄÖÜäöü'
def Stefan_Pochmann(alphabet):
yield ''
for prefix in Stefan_Pochmann(alphabet):
for characterletter in alphabet:
yield prefix + characterletter
def Stefan_Pochmann_2(alphabet):
yield ''
for prefix in Stefan_Pochmann_2(alphabet):
yield from map(prefix.__add__, alphabet)
def Ivo_Merchiers(lib):
for length in count(0):
for combination in product(lib, repeat=length):
yield ''.join(combination)
def Ivo_Merchiers_2(lib):
join = ''.join
for length in count(0):
for combination in product(lib, repeat=length):
yield join(combination)
def Ivo_Merchiers_3(lib):
for length in count(0):
yield from map(''.join, product(lib, repeat=length))
def Ivo_Merchiers_chain(lib): # from Peilonrayz
join = ''.join
return chain.from_iterable(
map(join, product(lib, repeat=length))
for length in count(0)
)
solutions = Stefan_Pochmann, Stefan_Pochmann_2, Ivo_Merchiers, Ivo_Merchiers_2, Ivo_Merchiers_3, Ivo_Merchiers_chain
for alphabet in lib, 'abc':
print(alphabet)
n = 10**7
# Correctness
sets = map(set, zip(*(words(alphabet) for words in solutions)))
print(f'same first {n-1:,}:', all(len(s) == 1 for s in islice(sets, n - 1)))
s = next(sets)
print(f'same {n:,}th:', len(s) == 1, s)
print()
# Speed
tss = [[] for _ in solutions]
for _ in range(3):
for words, ts in zip(solutions, tss):
t = min(repeat(lambda: deque(islice(words(alphabet), n), 0), number=1))
ts.append(t)
for words, ts in zip(solutions, tss):
print(*('%.2f' % t for t in ts), 'seconds ', words.__name__, sep=' ')
print()
def words(alphabet):
yield ''
for prefix in words(alphabet):
for character in alphabet:
yield prefix + character
from itertools import product, count, islice, chain
from timeit import repeat
from collections import deque
lib = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz°!"§$%&/()=ß ́`+#-.,><@€|^~–{[]}ÄÖÜäöü'
def Stefan_Pochmann(alphabet):
yield ''
for prefix in Stefan_Pochmann(alphabet):
for character in alphabet:
yield prefix + character
def Stefan_Pochmann_2(alphabet):
yield ''
for prefix in Stefan_Pochmann_2(alphabet):
yield from map(prefix.__add__, alphabet)
def Ivo_Merchiers(lib):
for length in count(0):
for combination in product(lib, repeat=length):
yield ''.join(combination)
def Ivo_Merchiers_2(lib):
join = ''.join
for length in count(0):
for combination in product(lib, repeat=length):
yield join(combination)
def Ivo_Merchiers_3(lib):
for length in count(0):
yield from map(''.join, product(lib, repeat=length))
def Ivo_Merchiers_chain(lib): # from Peilonrayz
join = ''.join
return chain.from_iterable(
map(join, product(lib, repeat=length))
for length in count(0)
)
solutions = Stefan_Pochmann, Stefan_Pochmann_2, Ivo_Merchiers, Ivo_Merchiers_2, Ivo_Merchiers_3, Ivo_Merchiers_chain
for alphabet in lib, 'abc':
print(alphabet)
n = 10**7
# Correctness
sets = map(set, zip(*(words(alphabet) for words in solutions)))
print(f'same first {n-1:,}:', all(len(s) == 1 for s in islice(sets, n - 1)))
s = next(sets)
print(f'same {n:,}th:', len(s) == 1, s)
print()
# Speed
tss = [[] for _ in solutions]
for _ in range(3):
for words, ts in zip(solutions, tss):
t = min(repeat(lambda: deque(islice(words(alphabet), n), 0), number=1))
ts.append(t)
for words, ts in zip(solutions, tss):
print(*('%.2f' % t for t in ts), 'seconds ', words.__name__, sep=' ')
print()
def words(alphabet):
yield ''
for prefix in words(alphabet):
for letter in alphabet:
yield prefix + letter
from itertools import product, count, islice, chain
from timeit import repeat
from collections import deque
lib = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz°!"§$%&/()=ß ́`+#-.,><@€|^~–{[]}ÄÖÜäöü'
def Stefan_Pochmann(alphabet):
yield ''
for prefix in Stefan_Pochmann(alphabet):
for letter in alphabet:
yield prefix + letter
def Stefan_Pochmann_2(alphabet):
yield ''
for prefix in Stefan_Pochmann_2(alphabet):
yield from map(prefix.__add__, alphabet)
def Ivo_Merchiers(lib):
for length in count(0):
for combination in product(lib, repeat=length):
yield ''.join(combination)
def Ivo_Merchiers_2(lib):
join = ''.join
for length in count(0):
for combination in product(lib, repeat=length):
yield join(combination)
def Ivo_Merchiers_3(lib):
for length in count(0):
yield from map(''.join, product(lib, repeat=length))
def Ivo_Merchiers_chain(lib): # from Peilonrayz
join = ''.join
return chain.from_iterable(
map(join, product(lib, repeat=length))
for length in count(0)
)
solutions = Stefan_Pochmann, Stefan_Pochmann_2, Ivo_Merchiers, Ivo_Merchiers_2, Ivo_Merchiers_3, Ivo_Merchiers_chain
for alphabet in lib, 'abc':
print(alphabet)
n = 10**7
# Correctness
sets = map(set, zip(*(words(alphabet) for words in solutions)))
print(f'same first {n-1:,}:', all(len(s) == 1 for s in islice(sets, n - 1)))
s = next(sets)
print(f'same {n:,}th:', len(s) == 1, s)
print()
# Speed
tss = [[] for _ in solutions]
for _ in range(3):
for words, ts in zip(solutions, tss):
t = min(repeat(lambda: deque(islice(words(alphabet), n), 0), number=1))
ts.append(t)
for words, ts in zip(solutions, tss):
print(*('%.2f' % t for t in ts), 'seconds ', words.__name__, sep=' ')
print()
It's probably also a lot faster than yours, although because of your bug, that's not easy to benchmark properly. Peilonrayz' version also has a bug at the moment, but we can compare with Ivo_Merchiers' solution: and a few variations.
First ten million words using your long alphabet of 99 letters (that's up to '021ü'):
0same first 9,999,999: True
same 10,000,000th: True {'9TT8'}
1.14941 1.38 1.38 seconds Stefan_Pochmann
01.24766 1.64 1.63 seconds Stefan_Pochmann_2
2.45 2.45 2.45 seconds Ivo_Merchiers
2.19 2.20 2.21 seconds Ivo_Merchiers_2
1.50 1.49 1.50 seconds Ivo_Merchiers_3
1.20 1.20 1.20 seconds Ivo_Merchiers_chain
First ten million words using alphabet abc (that's up to 'ababaccacabbc'):
0same first 9,999,999: True
same 10,000,000th: True {'abcaccbbcccacbc'}
2.28849 2.43 2.48 seconds Stefan_Pochmann
04.37616 4.17 4.19 seconds Stefan_Pochmann_2
3.91 3.91 3.93 seconds Ivo_Merchiers
3.64 3.66 3.64 seconds Ivo_Merchiers_2
2.74 2.74 2.75 seconds Ivo_Merchiers_3
2.45 2.46 2.45 seconds Ivo_Merchiers_chain
from itertools import product, count
from itertools import, islice, chain
from timeit import repeat
from collections import deque
lib = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz°!"§$%&/()=ß ́`+#-.,><@€|^~–{[]}ÄÖÜäöü'
def Stefan_Pochmann(alphabet):
yield ''
for prefix in Stefan_Pochmann(alphabet):
for character in alphabet:
yield prefix + character
def Stefan_Pochmann_2(alphabet):
yield ''
for prefix in Stefan_Pochmann_2(alphabet):
yield from map(prefix.__add__, alphabet)
def Ivo_Merchiers(lib):
for length in count(0):
for combination in product(lib, repeat=length):
yield ''.join(combination)
def Ivo_Merchiers_2(lib):
join = ''.join
for alphabetlength in count(0):
for combination in product(lib, 'abc'repeat=length):
print yield join(alphabetcombination)
def Ivo_Merchiers_3(lib):
for length in count(0):
yield from map(''.join, product(lib, repeat=length))
def Ivo_Merchiers_chain(lib): # Correctnessfrom Peilonrayz
stefanjoin = ''.join
return chain.from_iterable(
map(join, product(lib, repeat=length))
for length in count(0)
)
solutions = Stefan_Pochmann, Stefan_Pochmann_2, Ivo_Merchiers, Ivo_Merchiers_2, Ivo_Merchiers_3, Ivo_Merchiers_chain
for alphabet in lib, 'abc':
print(alphabet)
ivon = Ivo_Merchiers10**7
# Correctness
sets = map(set, zip(*(words(alphabet) for words in solutions)))
print(f'same first {n-1:,}:', all(len(s) == i1 for s, i in islice(zip(stefan, ivo)sets, 10**6n - 1)))
s, i = next(stefan), next(ivosets)
print(f'same {n:,}th:', len(s) == i1, s)
print()
# Speed
tss = [[] for _ in solutions]
for _ in range(3):
for words, ts in Stefan_Pochmannzip(solutions, Ivo_Merchierstss):
timet = min(repeat(lambda: deque(islice(words(alphabet), 10**6n), 0), number=1))
printts.append(f'{timet)
for words, ts in zip(solutions, tss):
print(*('%.3}2f' seconds% t for t in ts), 'seconds ', words.__name__)
, sep=' ')
print()
It's probably also a lot faster than yours, although because of your bug, that's not easy to benchmark properly. Peilonrayz' version also has a bug at the moment, but we can compare with Ivo_Merchiers' solution:
First million words using your long alphabet of 99 letters (that's up to '021ü'):
0.149 seconds Stefan_Pochmann
0.247 seconds Ivo_Merchiers
First million words using alphabet abc (that's up to 'ababaccacabbc'):
0.288 seconds Stefan_Pochmann
0.376 seconds Ivo_Merchiers
from itertools import product, count
from itertools import islice
from timeit import repeat
from collections import deque
lib = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz°!"§$%&/()=ß ́`+#-.,><@€|^~–{[]}ÄÖÜäöü'
def Stefan_Pochmann(alphabet):
yield ''
for prefix in Stefan_Pochmann(alphabet):
for character in alphabet:
yield prefix + character
def Ivo_Merchiers(lib):
for length in count(0):
for combination in product(lib, repeat=length):
yield ''.join(combination)
for alphabet in lib, 'abc':
print(alphabet)
# Correctness
stefan = Stefan_Pochmann(alphabet)
ivo = Ivo_Merchiers(alphabet)
print(all(s == i for s, i in islice(zip(stefan, ivo), 10**6 - 1)))
s, i = next(stefan), next(ivo)
print(s == i, s)
print()
# Speed
for _ in range(3):
for words in Stefan_Pochmann, Ivo_Merchiers:
time = min(repeat(lambda: deque(islice(words(alphabet), 10**6), 0), number=1))
print(f'{time:.3} seconds ', words.__name__)
print()
It's probably also a lot faster than yours, although because of your bug, that's not easy to benchmark properly. Peilonrayz' version also has a bug at the moment, but we can compare with Ivo_Merchiers' solution and a few variations.
First ten million words using your long alphabet of 99 letters:
same first 9,999,999: True
same 10,000,000th: True {'9TT8'}
1.41 1.38 1.38 seconds Stefan_Pochmann
1.66 1.64 1.63 seconds Stefan_Pochmann_2
2.45 2.45 2.45 seconds Ivo_Merchiers
2.19 2.20 2.21 seconds Ivo_Merchiers_2
1.50 1.49 1.50 seconds Ivo_Merchiers_3
1.20 1.20 1.20 seconds Ivo_Merchiers_chain
First ten million words using alphabet abc:
same first 9,999,999: True
same 10,000,000th: True {'abcaccbbcccacbc'}
2.49 2.43 2.48 seconds Stefan_Pochmann
4.16 4.17 4.19 seconds Stefan_Pochmann_2
3.91 3.91 3.93 seconds Ivo_Merchiers
3.64 3.66 3.64 seconds Ivo_Merchiers_2
2.74 2.74 2.75 seconds Ivo_Merchiers_3
2.45 2.46 2.45 seconds Ivo_Merchiers_chain
from itertools import product, count, islice, chain
from timeit import repeat
from collections import deque
lib = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz°!"§$%&/()=ß ́`+#-.,><@€|^~–{[]}ÄÖÜäöü'
def Stefan_Pochmann(alphabet):
yield ''
for prefix in Stefan_Pochmann(alphabet):
for character in alphabet:
yield prefix + character
def Stefan_Pochmann_2(alphabet):
yield ''
for prefix in Stefan_Pochmann_2(alphabet):
yield from map(prefix.__add__, alphabet)
def Ivo_Merchiers(lib):
for length in count(0):
for combination in product(lib, repeat=length):
yield ''.join(combination)
def Ivo_Merchiers_2(lib):
join = ''.join
for length in count(0):
for combination in product(lib, repeat=length):
yield join(combination)
def Ivo_Merchiers_3(lib):
for length in count(0):
yield from map(''.join, product(lib, repeat=length))
def Ivo_Merchiers_chain(lib): # from Peilonrayz
join = ''.join
return chain.from_iterable(
map(join, product(lib, repeat=length))
for length in count(0)
)
solutions = Stefan_Pochmann, Stefan_Pochmann_2, Ivo_Merchiers, Ivo_Merchiers_2, Ivo_Merchiers_3, Ivo_Merchiers_chain
for alphabet in lib, 'abc':
print(alphabet)
n = 10**7
# Correctness
sets = map(set, zip(*(words(alphabet) for words in solutions)))
print(f'same first {n-1:,}:', all(len(s) == 1 for s in islice(sets, n - 1)))
s = next(sets)
print(f'same {n:,}th:', len(s) == 1, s)
print()
# Speed
tss = [[] for _ in solutions]
for _ in range(3):
for words, ts in zip(solutions, tss):
t = min(repeat(lambda: deque(islice(words(alphabet), n), 0), number=1))
ts.append(t)
for words, ts in zip(solutions, tss):
print(*('%.2f' % t for t in ts), 'seconds ', words.__name__, sep=' ')
print()
'' '' + ''
'a' '' + 'a'
'b' '' + 'b'
'c' '' + 'c'
'aa' 'a' + 'a'
'ab' 'a' + 'b'
'ac' 'a' + 'c'
'ba' 'b' + 'a'
'bb' 'b' + 'b'
'bc' 'b' + 'c'
'ca' 'c' + 'a'
'cb' 'c' + 'b'
'cc' 'c' + 'c'
'aaa' 'aa' + 'a'
'aab' 'aa' + 'b'
'aac' 'aa' + 'c'
'aba' 'ab' + 'a'
'abb' 'ab' + 'b'
... ...
def words(alphabet):
yield ''
for prefix in prefixes(alphabet):
for characterletter in alphabet:
yield prefix + characterletter
'' '' + ''
'a' '' + 'a'
'b' '' + 'b'
'c' '' + 'c'
'aa' 'a' + 'a'
'ab' 'a' + 'b'
'ac' 'a' + 'c'
'ba' 'b' + 'a'
'bb' 'b' + 'b'
'bc' 'b' + 'c'
'ca' 'c' + 'a'
'cb' 'c' + 'b'
'cc' 'c' + 'c'
'aaa' 'aa' + 'a'
'aab' 'aa' + 'b'
'aac' 'aa' + 'c'
'aba' 'ab' + 'a'
'abb' 'ab' + 'b'
def words(alphabet):
yield ''
for prefix in prefixes(alphabet):
for character in alphabet:
yield prefix + character
'' '' + ''
'a' '' + 'a'
'b' '' + 'b'
'c' '' + 'c'
'aa' 'a' + 'a'
'ab' 'a' + 'b'
'ac' 'a' + 'c'
'ba' 'b' + 'a'
'bb' 'b' + 'b'
'bc' 'b' + 'c'
'ca' 'c' + 'a'
'cb' 'c' + 'b'
'cc' 'c' + 'c'
'aaa' 'aa' + 'a'
'aab' 'aa' + 'b'
'aac' 'aa' + 'c'
'aba' 'ab' + 'a'
'abb' 'ab' + 'b'
... ...
def words(alphabet):
yield ''
for prefix in prefixes(alphabet):
for letter in alphabet:
yield prefix + letter
Loading
Loading
Loading
lang-py