Python en mathématiques - Défis

Générer les permutations: récursivité

Générer les permutations, méthode 1

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)

Générer les permutations, méthode 2

Générer les permutations

Considérons toutes les permutations des entiers 1, 2, 3, ..., n.

  • Il y a les permutations qui se terminent par n.
    Les n-1 premiers éléments peuvent être disposés de (n-1)! façons différentes : ce sont les permutations des entiers 1, 2, 3, ..., (n-1).
  • Il y a les permutations qui se terminent par n-1.
    Les n-1 premiers éléments peuvent être disposés de (n-1)! façons différentes : ce sont les permutations des n-1 entiers 1, 2, 3, ..., (n-2), n.
  • Il y a les permutations qui se terminent par n-2.
    Les n-1 premiers éléments peuvent être disposés de (n-1)! façons différentes : ce sont les permutations des n-1 entiers 1, 2, 3, ..., (n-3), (n-1), n.
  • ...
  • Il y a les permutations qui se terminent par 1.
    Les n-1 premiers éléments peuvent être disposés de (n-1)! façons différentes : ce sont les permutations des n-1 entiers 2, 3, ..., (n-1), n.

Pour générer les permutations des entiers 1, 2, 3, ..., n, on peut donc :

  1. Générer les permutations des entiers 1, 2, 3, ..., n-1.
  2. A la fin de chacune de ces permutations, on ajoute l'entier n : on obtient toutes les permutations des entiers 1, 2, 3, ..., n se terminant par n.
  3. A la fin de chacune des permutations des entiers 1, 2, 3, ..., n-1, ajouter l'entier n-1 puis incrémenter d'une unité l'entier n-1 se trouvant dans les n-1 premières places. On obtient ainsi toutes les permutations des entiers 1, 2, 3, ..., n se terminant par n-1.
  4. ...
  5. De façon générique :

    A la fin de chacune des permutations des entiers 1, 2, 3, ..., n-1, ajouter l'entier j (où $1\leqslant j\leqslant n$) puis incrémenter d'une unité chaque entier $\geqslant j$ se trouvant dans les n-1 premières places. On obtient ainsi toutes les permutations des entiers 1, 2, 3, ..., n se terminant par j.

    A vous de coder !

    Application

    Le produit $42 \times 138 = 5796$ fait intervenir une fois et une seule chacun des 9 chiffres entre 1 et 9. Quels sont les autres produits ayant cette propriété ?

    • Générer la liste des permutations
    • Produit neuf chiffres
    
     
    def fin_en_j(n, listePermPred, j):
    	"""
    	n est un entier naturel non nul.
    	listePermPred est la liste des permutations des entiers 1, 2, 3, ..., n-1.
    	j est un entier entre 1 et n.
    	La fonction renvoie la liste des permutations des entiers 1, 2, 3, ..., n
    	se terminant par j.
    	"""
    	liste = []
    	for perm in listePermPred:
    		nv_perm = perm[:]  
    		for indice, valeur in enumerate(nv_perm):
    			if valeur >= j: 
    				nv_perm[indice] = valeur+1
    		nv_perm.append(j)
    		liste.append(nv_perm)
    	return liste
    	
    	
    def genere_perm(n, listePermPred):
    	"""
    	n est un entier naturel non nul.
    	listePermPred est la liste des permutations des entiers 1, 2, 3, ..., n-1.
    	La fonction renvoie la liste des permutations des entiers 1, 2, 3, ..., n.
    	"""
    	liste = []
    	for j in range(1, n+1):
    		liste.extend(fin_en_j(n, listePermPred, j))
    	return liste
    	
    
     
     
    def generePermutations(n):
    	"""
    	n est un entier naturel non nul.
    	La fonction renvoie la liste des permutations des entiers 1, 2, 3, ..., n.
    	"""
    	liste = [[1]]
    	for k in range(2, n+1):
    		liste = genere_perm(k, liste) 
    	return liste
    	
    	
    PERM = generePermutations(4)
    for p in PERM:
    	print(p)
    	
    print("Nombre de permuations: ", len(PERM)) 
    

    On obtient:

    [4, 3, 2, 1]
    [3, 4, 2, 1]
    [4, 2, 3, 1]
    [2, 4, 3, 1]
    [3, 2, 4, 1]
    [2, 3, 4, 1]
    [4, 3, 1, 2]
    [3, 4, 1, 2]
    [4, 1, 3, 2]
    [1, 4, 3, 2]
    [3, 1, 4, 2]
    [1, 3, 4, 2]
    [4, 2, 1, 3]
    [2, 4, 1, 3]
    [4, 1, 2, 3]
    [1, 4, 2, 3]
    [2, 1, 4, 3]
    [1, 2, 4, 3]
    [3, 2, 1, 4]
    [2, 3, 1, 4]
    [3, 1, 2, 4]
    [1, 3, 2, 4]
    [2, 1, 3, 4]
    [1, 2, 3, 4]
    Nombre de permuations:  24
    

    Il est facile de voir que l'on doit limiter la recherche à :

    • × =
    • et × =
    
    def fin_en_j(n, listePermPred, j):
    	"""
    	n est un entier naturel non nul.
    	listePermPred est la liste des permutations des entiers 1, 2, 3, ..., n-1.
    	j est un entier entre 1 et n.
    	La fonction renvoie la liste des permutations des entiers 1, 2, 3, ..., n
    	se terminant par j.
    	"""
    	liste = []
    	for perm in listePermPred:
    		nv_perm = perm[:]  
    		for indice, valeur in enumerate(nv_perm):
    			if valeur >= j: 
    				nv_perm[indice] = valeur+1
    		nv_perm.append(j)
    		liste.append(nv_perm)
    	return liste
    	
    	
    def genere_perm(n, listePermPred):
    	"""
    	n est un entier naturel non nul.
    	listePermPred est la liste des permutations des entiers 1, 2, 3, ..., n-1.
    	La fonction renvoie la liste des permutations des entiers 1, 2, 3, ..., n.
    	"""
    	liste = []
    	for j in range(1, n+1):
    		liste.extend(fin_en_j(n, listePermPred, j))
    	return liste
    	
    
     
     
    def generePermutations(n):
    	"""
    	n est un entier naturel non nul.
    	La fonction renvoie la liste des permutations des entiers 1, 2, 3, ..., n.
    	"""
    	liste = [[1]]
    	for k in range(2, n+1):
    		liste = genere_perm(k, liste) 
    	return liste
    	
    
    def recherche():
    	liste= []
    	for p in generePermutations(9):
    		n1 = p[0]
    		n2 = p[1] * 1000 + p[2] * 100 + p[3] * 10 + p[4]
    		n3 = p[5] * 1000 + p[6] * 100 + p[7] * 10 + p[8]
    		if n1*n2 == n3: liste.append((n1,n2,n3))
    		n1 = p[0] * 10 + p[1]
    		n2 = p[2] * 100 + p[3] * 10 + p[4]
    		n3 = p[5] * 1000 + p[6] * 100 + p[7] * 10 + p[8]
    		if n1*n2 == n3: liste.append((n1,n2,n3))
    	return liste
    	
    for solution in recherche():
    	print(solution)
    

    On obtient:

    (48, 159, 7632)
    (4, 1963, 7852)
    (4, 1738, 6952)
    (39, 186, 7254)
    (18, 297, 5346)
    (27, 198, 5346)
    (28, 157, 4396)
    (12, 483, 5796)
    (42, 138, 5796)