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."

In [1]:
from itertools import permutations
In [2]:
# On regarde ce que ça fait
permutations(range(3))
Out[2]:
<itertools.permutations at 0x7f308c3cc530>
In [3]:
list(_)
Out[3]:
[(0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)]
In [4]:
# On regarde comment construire les deux ensembles de diagonales
[{i+p[i] for i in range(3)} for p in permutations(range(3))]
Out[4]:
[{0, 2, 4}, {0, 3}, {1, 4}, {1, 2, 3}, {1, 2, 3}, {2}]

Et voilà ! On peut coder la solution en une ligne !

In [5]:
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]
In [6]:
len(ll)
Out[6]:
92

Comme indiqué pendant le TD, on peut vraiment résoudre le problème sur un téléphone ...

iphone

iphone

In [7]:
# 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
In [9]:
for i in range(3,9): print len(queens(i)),
 0 2 10 4 40 92

In [10]:
len(queens(9))
Out[10]:
352
In [11]:
len(queens(10))
Out[11]:
724

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 une console pour déterminer les étapes de la solution.

In [13]:
x = 'SEND + MORE == MONEY'

Il faut d'abord vérifier que \(x\) n'a pas plus de 10 lettres différentes

In [14]:
chars = ''.join({c for c in x if c.isalpha()})
print chars, len(chars)
EDMONSRY 8

Pour substituer des chiffres aux lettres dans \(x\), on utilisera une table de traduction :

In [15]:
from string import maketrans
t = maketrans(chars, '12345678')
x.translate(t)
Out[15]:
'6152 + 3471 == 34518'
In [16]:
eval(_)
Out[16]:
False

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 :

In [17]:
print list(permutations('1234',3))
[('1', '2', '3'), ('1', '2', '4'), ('1', '3', '2'), ('1', '3', '4'), ('1', '4', '2'), ('1', '4', '3'), ('2', '1', '3'), ('2', '1', '4'), ('2', '3', '1'), ('2', '3', '4'), ('2', '4', '1'), ('2', '4', '3'), ('3', '1', '2'), ('3', '1', '4'), ('3', '2', '1'), ('3', '2', '4'), ('3', '4', '1'), ('3', '4', '2'), ('4', '1', '2'), ('4', '1', '3'), ('4', '2', '1'), ('4', '2', '3'), ('4', '3', '1'), ('4', '3', '2')]

Pour construire les tables de traduction, il faut donc faire un ''.join de ces résultats :

In [18]:
print [''.join(p) for p in permutations('1234',3)]
['123', '124', '132', '134', '142', '143', '213', '214', '231', '234', '241', '243', '312', '314', '321', '324', '341', '342', '412', '413', '421', '423', '431', '432']

Résolvons maintenant notre exemple :

In [19]:
res = []
for p in permutations('0123456789',8):
    t = maketrans(chars,''.join(p))
    y = x.translate(t)
    if eval(y): res.append(y)
  File "<string>", line 1
    5142 + 0361 == 03418
                       ^
SyntaxError: invalid token

Il y a encore un problème : en python 2, 0361 est interprété comme de l'octal ...

In [20]:
0361
Out[20]:
241

Il faut donc enlever les 0 initiaux avant d'évaluer. On bricole pour cela une expression régulière :

In [21]:
import re
pat = re.compile(r'((\D|^))(0+)([1-9][0-9]*)')
y = '5142 + 0361 == 03418'
re.findall(pat,y)
Out[21]:
[(' ', ' ', '0', '361'), (' ', ' ', '0', '3418')]
In [22]:
pat.sub(lambda m: m.group(1)+m.group(4), y)
Out[22]:
'5142 + 361 == 3418'
In [23]:
# On reprend où on en était
res = []
for p in permutations('0123456789',8):
    t = 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)
In [24]:
# On attend un peu, et on contemple le résultat
res
Out[24]:
['8324 + 913 == 9237',
 '7316 + 823 == 8139',
 '8432 + 914 == 9346',
 '6415 + 734 == 7149',
 '6419 + 724 == 7143',
 '7429 + 814 == 8243',
 '7531 + 825 == 8356',
 '8542 + 915 == 9457',
 '6524 + 735 == 7259',
 '7534 + 825 == 8359',
 '9567 + 1085 == 10652',
 '7539 + 815 == 8354',
 '7643 + 826 == 8469',
 '7649 + 816 == 8465',
 '5731 + 647 == 6378',
 '3712 + 467 == 4179',
 '5732 + 647 == 6379',
 '3719 + 457 == 4176',
 '3821 + 468 == 4289',
 '6851 + 738 == 7589',
 '6853 + 728 == 7581',
 '2817 + 368 == 3185',
 '2819 + 368 == 3187',
 '3829 + 458 == 4287',
 '5849 + 638 == 6487']

Il y a donc bien comme annoncé une seule solution si on interdit les 0 initiaux.

In [26]:
# Solveur de cryptarithmes par force brute
# (on essaie toutes les possibilites)
# Ici on autorise la premiere lettre a etre 0
# Attention, 012 (octal) = 9 (decimal) !
# Il faut donc enlever les 0 au debut avant de tester
from itertools import permutations
import re
from string import maketrans




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 = 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)
MARS + SATURNE + NEPTUNE == PLANETES 
8724 + 4765290 + 9016590 == 13790604 

Exercice 3

Prenons un élément de la suite, par exemple \(u=111221\), et regardons l'effet de groupby

In [27]:
from itertools import *
u = '111221'
g = groupby(u)
In [28]:
[(k,list(v)) for k,v in g]
Out[28]:
[('1', ['1', '1', '1']), ('2', ['2', '2']), ('1', ['1'])]
In [29]:
[str(len(v))+k for k,v in _]
Out[29]:
['31', '22', '11']
In [30]:
''.join(_)
Out[30]:
'312211'

On a donc la solution :

In [31]:
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)                                              
1
11
21
1211
111221
312211
13112221
1113213211
31131211131221
13211311123113112211
11131221133112132113212221
3113112221232112111312211312113211
1321132132111213122112311311222113111221131221
11131221131211131231121113112221121321132132211331222113112211
311311222113111231131112132112311321322112111312211312111322212311322113212221

Exercice 4

On commence par traduire le pseudo(code de Wikipedia en Python :

In [32]:
## Algorithme de Heap

def generate(n):
    A = 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
            
In [33]:
generate(3)
Out[33]:
[(1, 2, 3), (2, 1, 3), (3, 1, 2), (1, 3, 2), (2, 3, 1), (3, 2, 1)]
In [34]:
from time import time
a = time(); print len(generate(10));print time()-a
3628800
6.54991102219

In [35]:
a = time(); print len(list(permutations(range(1,11))));print time()-a
3628800
1.8500430584

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

$ pip install cython --user

On copie le programme dans un fichier heap.pyx et on déclare quelques types :

```python ## heap.pyx ## Algorithme de Heap

def generate(int n): # n est un entier cdef int i # i aussi cdef list A,c # et A, c son des listes A = range(1,n+1) # 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

In [36]:
!ls heap*
heap.c	heap.py  heap.pyx  heap.so

In [37]:
from heap import *
In [40]:
a = time(); print len(list(generate(10)));print time()-a
3628800
2.54358696938

On s'est donc rapproché des performances d'itertools.