Générer les permutations
On peut générer les permutations des entiers 1, 2, 3, ..., n suivant le principe ci-dessous:
- Les permutations pour l'entier 1 : [1].
- Les permutations des entiers 1, 2 : [2, 1], [1, 2].
On a simplement placé 2 aux positions possibles par rapport à 1. - Les permutations pour les entiers 1, 2, 3 : on place 3 à tous les emplacements
possibles sur toutes les permutations des entiers 1, 2.
Cela donne : [3,2,1], [2,3,1], [2,1,3], [3,1,2], [1,3,2], [1,2,3]. - etc...
Générer les permutations des entiers 1, 2, 3, ..., n à l'aide d'un script python en partant comme ci-dessus de la liste des permutations du seul objet 1.
Application
Remplir les 9 cases ci-après par les 9 entiers 1, 2, 3, 4, 5, 6, 7, 8, 9 (chacun présent exactement une fois). L'objectif est de trouver toutes les solutions.
× = = ×
- Générer la liste des permutations
- Remplir les cases
from copy import deepcopy
def genere(n, listeperm):
"""
n: entier naturel
listeperm : liste des permutations pour l'entier n-1
Exemples:
liste_1 = [[1]]
liste_2 = [[1,2],[2,1]]
liste_3 = [[3,1,2], [1,3,2], [1,2,3], [3,2,1], [2,3,1], [2,1,3]]
La fonction renvoie la liste des permutations pour l'entier n
"""
liste = []
for permutation in listeperm:
for indice in range(0,n):
perm = deepcopy(permutation)
perm.insert(indice, n)
liste.append(perm)
return liste
def generer(n):
"""
n est un entier naturel.
La fonction génère la liste des permutations des entiers 1, 2, ..., n
"""
liste = [[1]]
for k in range(2,n+1):
liste = genere(k, liste)
return liste
def affichage(Liste):
for liste in Liste:
print(liste)
n = 4
affichage(generer(n))
On obtient:
[4, 3, 2, 1] [3, 4, 2, 1] [3, 2, 4, 1] [3, 2, 1, 4] [4, 2, 3, 1] [2, 4, 3, 1] [2, 3, 4, 1] [2, 3, 1, 4] [4, 2, 1, 3] [2, 4, 1, 3] [2, 1, 4, 3] [2, 1, 3, 4] [4, 3, 1, 2] [3, 4, 1, 2] [3, 1, 4, 2] [3, 1, 2, 4] [4, 1, 3, 2] [1, 4, 3, 2] [1, 3, 4, 2] [1, 3, 2, 4] [4, 1, 2, 3] [1, 4, 2, 3] [1, 2, 4, 3] [1, 2, 3, 4]
from copy import deepcopy
def genere(n, listeperm):
"""
n: entier naturel
listeperm : liste des permutations pour l'entier n-1
Exemples:
liste_1 = [[1]]
liste_2 = [[1,2],[2,1]]
liste_3 = [[3,1,2], [1,3,2], [1,2,3], [3,2,1], [2,3,1], [2,1,3]]
La fonction renvoie la liste des permutations pour l'entier n
"""
liste = []
for permutation in listeperm:
for indice in range(0,n):
perm = deepcopy(permutation)
perm.insert(indice, n)
liste.append(perm)
return liste
def generer(n):
"""
n est un entier naturel.
La fonction génère la liste des permutations des entiers 1, 2, ..., n
"""
liste = [[1]]
for k in range(2,n+1):
liste = genere(k, liste)
return liste
def affichage(Liste):
for liste in Liste:
print(liste)
def remplirCases():
liste_permutations = generer(9) # liste des permutations des entiers de 1 à 9
liste_solutions = []
for perm in liste_permutations :
a = perm[0]
b = perm[1]*10+perm[2]
c = perm[3]*100 + perm[4]*10 + perm[5]
d = perm[6]*10 + perm[7]
e = perm[8]
if a*b == c and c == d*e:
liste_solutions.append((a,b,c,d,e))
return liste_solutions
print(remplirCases())
On obtient:
(6, 29, 174, 58, 3), (2, 78, 156, 39, 4), (4, 39, 156, 78, 2), (3, 58, 174, 29, 6)