Python TD 5¶
itertools¶
Exercice 1¶
On se contente de traduire en Python la phrase de l'énoncé
"La condition sur les lignes et les colonnes signifie que pour un placement correct, les numéros de colonne forment une permutation $p$ de ceux des lignes. Les diagonales sont définies par $i+j=$ constante et $i-j=$ constante. On sélectionnera donc les permutations p telles que les ensembles $\{i+p(i)\}$ et $\{i-p(i)\}$ soient tous deux de cardinal 8."
from itertools import permutations
# On regarde ce que ça fait
permutations(range(3))
list(_)
# On regarde comment construire les deux ensembles de diagonales
[{i+p[i] for i in range(3)} for p in permutations(range(3))]
Et voilà ! On peut coder la solution en une ligne !
ll = [p for p in permutations(range(8)) if len({i+p[i] for i in range(8)})==8 and len({i-p[i] for i in range(8)})==8]
len(ll)
Comme indiqué pendant le TD, on peut vraiment résoudre le problème sur un téléphone ...
# On peut maintenant faire une fonction pour traiter un échiquier n*n
def queens(n):
sols = []
for p in permutations(range(n)):
if len(set([i+p[i] for i in range(n)]))==len(set([i-p[i] for i in range(n)]))==n:
sols.append(p)
return sols
for i in range(3,9): print (len(queens(i)), end= ' ')
len(queens(9))
len(queens(10))
Avec la force brute, on ira difficilement au delà de $n=11$. Avec des algorithmes optimisés, on peut aller plus loin, voir ici.
Exercice 2¶
Commençons par analyer un exemple dans l'interpréteur pour déterminer les étapes de la solution.
x = 'SEND + MORE == MONEY'
Il faut d'abord vérifier que $x$ n'a pas plus de 10 lettres différentes
chars = ''.join({c for c in x if c.isalpha()})
print (chars, len(chars))
Pour substituer des chiffres aux lettres dans $x$, on utilisera une table de traduction :
t = str.maketrans(chars, '12345678')
x.translate(t)
Le résultat est une expression python valide, qui peut être évaluée par la fonction eval :
eval(_)
Il faut donc engendrer toutes les chaînes de 8 chiffres différents, et pour chacune d'entre elles, effectuer la substitution dans $x$ et l'évaluer ...
On vérifie que le paramètre optionnel de la fonction permutations fait cela :
print (list(permutations('1234',3)))
Pour construire les tables de traduction, il faut donc faire un ''.join de ces résultats :
print ([''.join(p) for p in permutations('1234',3)])
Résolvons maintenant notre exemple :
res = []
for p in permutations('0123456789',8):
t = str.maketrans(chars,''.join(p))
y = x.translate(t)
if eval(y): res.append(y)
Il y a encore un problème : un nombre commençant par un 0 est invalide en python 3. En python 2, 0361 est interprété comme de l'octal, ce qui n'est pas mieux ...
0361
Si on n'autorise pas les 0 initiaux, on peut dans un premier temps se contenter d'ignorer les erreurs avec un try--except :
res = []
for p in permutations('0123456789',8):
t = str.maketrans(chars,''.join(p))
y = x.translate(t)
try:
if eval(y): res.append(y)
except: pass
res
Si on veut considérer toutes les solutions, il faut enlever les 0 initiaux avant d'évaluer. On bricole pour cela une expression régulière :
import re
pat = re.compile(r'((\D|^))(0+)([1-9][0-9]*)')
y = '5142 + 0361 == 03418'
re.findall(pat,y)
pat.sub(lambda m: m.group(1)+m.group(4), y)
# On reprend où on en était
res = []
for p in permutations('0123456789',8):
t = str.maketrans(chars,''.join(p))
y = x.translate(t)
y = pat.sub(lambda m: m.group(1)+m.group(4), y)
if eval(y): res.append(y)
# On attend un peu, et on contemple le résultat
res
Il y a donc bien comme annoncé une seule solution si on interdit les 0 initiaux.
# Solveur de cryptarithmes par force brute
# (on essaie toutes les possibilites)
# Ici on autorise la premiere lettre à être 0
# Attention, 012 est invalide
# Il faut donc enlever les 0 au debut avant de tester
from itertools import permutations
import re
def solve(s):
pat = re.compile(r'((\D|^))(0+)([1-9][0-9]*)') # pour enlever les 0 initiaux avant d'evaluer
words = re.findall('[A-Z]+',s)
chars = ''.join(set(''.join(words)))
for perm in permutations('0123456789', len(chars)):
tt = str.maketrans(chars, ''.join(perm))
eq = s.translate(tt)
eq = pat.sub(lambda m: m.group(1)+m.group(4), eq) # ici
if eval(eq): print (eq)
s = 'MARS + SATURNE + NEPTUNE == PLANETES '
print (s)
solve(s)
Exercice 3¶
Prenons un élément de la suite, par exemple $u=111221$, et regardons l'effet de groupby
from itertools import *
u = '111221'
g = groupby(u)
[(k,list(v)) for k,v in g]
[str(len(v))+k for k,v in _]
''.join(_)
On a donc la solution :
def suivant(x):
return ''.join([str(len(x))+x[0] for x in [list(g) for k,g in groupby(x)]])
cache = {1:'1'}
def conway(n):
if n in cache: return cache[n]
else:
y = suivant(conway(n-1))
cache[n]=y
return y
for n in range(1,16): print (conway(n))
Exercice 4¶
On commence par traduire le pseudo-code de Wikipedia en Python :
## Algorithme de Heap
def generate(n):
A = list(range(1,n+1))
res = []
c = [0]*n
res.append(tuple(A))
i = 0
while i<n:
if c[i]<i:
if i%2: A[c[i]],A[i] = A[i],A[c[i]]
else: A[0],A[i] = A[i],A[0]
res.append(tuple(A))
c[i] += 1
i = 0
else:
c[i] = 0
i +=1
return res
generate(3)
from time import time
a = time(); print (len(generate(10)));print (time()-a)
# Pour le moment, itertools gagne la course
a = time(); print (len(list(permutations(range(1,11)))));print (time()-a)
Il faut ensuite installer Cython si ce n'est pas déjà fait. Si on n'est pas super-utilisateur, on peut l'installer pour soi seul avec la commande
$ pip3 install cython --user
On copie le programme dans un fichier heap.pyx et on déclare quelques types :
## heap.pyx
## Algorithme de Heap
def generate(int n): # n est un entier
cdef int i # i aussi
cdef list A,c # A, c sont des listes
A = range(1,n+1) # et c'est tout ...
c = [0]*n
yield(tuple(A))
i = 0
while i<n:
if c[i]<i:
if i%2: A[c[i]],A[i] = A[i],A[c[i]]
else: A[0],A[i] = A[i],A[0]
yield(tuple(A)) # On codera plutôt un générateur
c[i] += 1
i = 0
else:
c[i] = 0
i +=1
On créee ensuite un fichier setup.py :
## setup.py
from distutils.core import setup
from Cython.Build import cythonize
setup( ext_modules = cythonize("heap.pyx"))
Et on compile avec la commande
$ python setup.py build_ext --inplace
!ls heap*
from heap import *
a = time(); print (len(list(generate(10))));print (time()-a)
On s'est donc rapproché des performances d'itertools.