1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
| import math # Ou définition de notre propore fonction factorial, ce n’est pas bien compliqué
import itertools
def permuts_a(items):
items = tuple(items)
ln = len(items)
if ln <= 1:
return [items]
liste=[]
for p in permuts_a(items[1:]):
for i in range(ln):
liste.append(tuple(p[:i] + items[0:1] + p[i:]))
return liste
def permuts_b(items):
items = tuple(items)
ln = len(items)
if ln > 10:
raise ValueError("We can't compute all the permutations of sequence lengther than 10 items!")
if ln <= 1:
return [items]
num = math.factorial(ln)
liste = [None] * num
liste[0] = items
fact = 1
offset = num
while (fact < ln):
items = itertools.islice(liste, 0, num, offset)
fact += 1
offset = num // math.factorial(fact)
idx = 0
for it in items:
idx += offset
rad, c, end = it[:-fact], it[-fact:-fact + 1], it[-fact + 1:]
for i in range(1, fact):
liste[idx] = tuple(rad + end[:i] + c + end[i:])
idx += offset
return liste
def permuts_c(seq):
results = []
seq = list(seq)
results.append(tuple(seq))
i = 0
while 1:
i += 1
n,d,r = i, 1, 0 # numerator, divisor, rest
while r == 0:
d += 1
n, r = divmod(n, d)
if d > len(seq): break
seq[-d], seq[-r] = seq[-r], seq[-d] # swap
seq[-d+1:] = seq[-1:-d:-1] # reverse the end
results.append(tuple(seq))
return results
def permuts_d(seq):
totlen = math.factorial(len(seq))
results = [None] * totlen
seq = list(seq)
results[0] = tuple(seq)
for i in range(1, totlen):
n, d, r = i, 1, 0 # numerator, divisor, rest
while r == 0:
d += 1
n, r = divmod(n, d)
seq[-d], seq[-r] = seq[-r], seq[-d] # swap
seq[-d + 1:] = seq[-1:-d:-1] # reverse the end
results[i] = tuple(seq)
return results
def check(items, num=1000):
import timeit
print("permuts_a({}) {} times:\n\t{}".format(repr(items), num,
timeit.timeit("permuts_a({})".format(repr(items)), setup="from __main__ import permuts_a", number=num)))
print("permuts_b({}) {} times:\n\t{}".format(repr(items), num,
timeit.timeit("permuts_b({})".format(repr(items)), setup="from __main__ import permuts_b", number=num)))
print("permuts_c({}) {} times:\n\t{}".format(repr(items), num,
timeit.timeit("permuts_c({})".format(repr(items)), setup="from __main__ import permuts_c", number=num)))
print("permuts_d({}) {} times:\n\t{}".format(repr(items), num,
timeit.timeit("permuts_d({})".format(repr(items)), setup="from __main__ import permuts_d", number=num))) |
