Python en mathématiques - Défis

Générer les permutations

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

Un premier script

On considère le programme python suivant:


def toutChiffre(m):
    """
    m est un entier naturel dont l'écriture
    décimale est de longueur 9, 
    c'est à dire   10^8 <= m < 10^9
    """
    m = str(m)
    for i in '123456789':
        if i not in m: return False
    return True

Que renverra toutChiffre(234567891)? toutChiffre(232567891)?

Quel est le "rôle" de cette fonction?

Un second script

On considère le programme suivant:


def perm():
    liste = []
    for i in range(123456789, 987654321 + 1):
        if toutChiffre(i):
            liste.append(i)
    return liste

Que contiendra la liste renvoyée par la fonction?

Un petit problème

Avec les neuf chiffres 1, 2, 3, 4, 5, 6, 7, 8, 9 on forme trois entiers à deux chiffres et un entier à trois chiffres (chacun des 9 chiffres étant présent une et une seule fois). Est-il possible que le produit des deux entiers à deux chiffres ainsi formé soit égal au produit des deux autres?

Il s'agit donc de remplir correctement les cases suivantes, chacun des entiers entre 1 et 9 devant être présent exactement une fois:

× = ×

Par exemple $a=67$, $b=58$, $c=29$, $d=134$ et $a\times b = 3886 = c\times d$. Quelles sont les autres possibilités?

  • Question 1
  • Question 2
  • Question 3

toutChiffre(234567891) = True, toutChiffre(232567891) = False .

La fonction renvoie True si l'écriture décimale de m contient les neuf chiffres 1, 2, 3, 4, 5, 6, 7, 8, 9. Et renvoie False sinon.

La liste calculée par la fonction contiendra tous les entiers s'écrivant avec les neuf chiffres 1, 2, 3, 4, 5, 6, 7, 8, 9.

Cette liste est donc de longueur $9! = 362\ 880$.

Le début de liste:

 123456789,
 123456798,
 123456879,
 123456897,
 123456978,
 123456987,
 123457689,
 123457698,
 123457869,
 123457896,
 123457968,
 123457986,
 123458679,
 123458697,
 123458769,
 123458796,
 123458967,
 123458976,
 123459678,
 123459687,
 123459768,
 123459786,
 

def toutChiffre(m):
    """
    m est un entier naturel dont l'écriture
    décimale est de longueur 9
    """
    m=str(m)
    for i in '123456789':
        if i not in m: return False
    return True
    
def perm():
    n = 123456789
    for i in range(n,10**9):
        if toutChiffre(i):
            yield i
            
def produits(m):
    e1 = m%100
    m = m//100
    e2 = m%100 
    m = m//100 
    e3 = m%100
    m = m//100
    e4 = m
    p1 = e1*e2
    p2 = e3*e4
    if p1 == p2:
        return (e1,e2,e3,e4, p1)
    else:
        return False

for p in perm():
    q = produits(p)
    if q: print(q)     

On obtient:

(67, 58, 29, 134, 3886)
(58, 67, 29, 134, 3886)
(69, 54, 27, 138, 3726)
(54, 69, 27, 138, 3726)
(73, 58, 29, 146, 4234)
(58, 73, 29, 146, 4234)
(79, 46, 23, 158, 3634)
(46, 79, 23, 158, 3634)
(79, 64, 32, 158, 5056)
(64, 79, 32, 158, 5056)
(69, 58, 23, 174, 4002)
(58, 69, 23, 174, 4002)
(96, 58, 32, 174, 5568)
(58, 96, 32, 174, 5568)
(93, 54, 27, 186, 5022)
(54, 93, 27, 186, 5022)
(74, 63, 18, 259, 4662)
(63, 74, 18, 259, 4662)
(98, 76, 14, 532, 7448)
(76, 98, 14, 532, 7448)
(96, 73, 12, 584, 7008)
(73, 96, 12, 584, 7008)

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

Un algorithme

En étudiant la liste constituée des entiers à 9 chiffres tous distincts trouvée dans l'exercice précédent:

  • Le début
     123456789,  123456798,  123456879,
     123456897,  123456978,  123456987,
     123457689,  123457698,  123457869,
     123457896,  123457968,  123457986,
     123458679,  123458697,  123458769,
     123458796,
    
  • Un autre extrait:
     361485972,
     361487259,
     361487295,
     361487529,
     361487592,
     361487925,
     361487952,
     361489257,
     361489275,
     361489527,
     361489572,
     361489725
    

tentez de définir un algorithme permettant de passer d'un entier au suivant.

La première descente à droite

On dispose d'une liste L contenant les neuf chiffres de 1 à 9. Par exemple L = [3,6,2,5,8,4,9,7,1].

Codez en python une fonction rangDesc(liste) spécifiée comme suit:

  • La fonction "lit" les valeurs de la liste L de la droite vers la gauche.
  • La fonction renvoie le premier indice correspondant à une valeur lue inférieure à celle qui a été lue juste avant.

Exemples:

  • rangDesc([3, 6, 2, 5, 8, 4, 9, 7, 1]) = 5 (car en lisant de droite à gauche, 4 est la première valeur inférieure à celle qui est à sa droite et 4 a pour indice 5 dans la liste).
  • rangDesc([3, 6, 4, 5, 2, 9, 8, 7, 5, 1]) = 4 (car en lisant de droite à gauche, 2 est la première valeur inférieure à celle qui est à sa droite et 2 a pour indice 4 dans la liste).

Échange et renversement

Écrire une fonction python echange(liste, indicepivot) pour laquelle l'entrée liste est une liste dont le contenu est de la forme [..., valeur pivot, sous-liste de fin] où les éléments de sous-liste de fin sont en ordre décroissant. Cette fonction:

  • détermine l'indice indiceMinPG de l'élément le plus petit parmi ceux qui sont supérieurs à liste[indicepivot] et dont l'indice est supérieur à indicepivot.
  • échange les valeurs se trouvant à l'indice indicepivot et à l'indice indiceMinPG.
  • renverse l'ordre des éléments se trouvant alors aux indices indicepivot+1, indicepivot+2, ..., len(liste)-1.

Exemples:

  • Si A = [3,6,2,5,8,4,9,7,1], avec echange(A,5), on aura d'abord (échange des valeurs à indicepivot et indiceMinPG) A = [3, 6, 2, 5, 8, 7, 9, 4, 1] puis (renverserment des éléments après le pivot) A = [3, 6, 2, 5, 8, 7, 1, 4, 9].
  • Si A = [3, 6, 4, 2, 9, 8, 7, 5, 1], avec echange(A,3), on aura d'abord (échange des valeurs à indicepivot et indiceMinPG) A = [3, 6, 4, 5, 9, 8, 7, 2, 1] puis (renverserment des éléments après le pivot) A = [3, 6, 4, 5, 1, 2, 7, 8, 9].

Permutations

Utiliser les deux fonctions précédentes pour répondre à la question 1 ("tentez de définir un algorithme permettant de passer d'un entier au suivant").

Application

Avec les neuf chiffres 1, 2, 3, 4, 5, 6, 7, 8, 9 on forme trois entiers à trois chiffres. Est-il possible que la somme de deux des entiers soit égale au troisème entier? Donner toutes les solutions.

Il s'agit donc de remplir correctement les cases suivantes, chacun des entiers entre 1 et 9 devant être présent exactement une fois:

+ =

Par exemple 357 + 462 = 819.

Lorsque a + b = c, on éliminera le cas b > a pour ne garder que le cas a < b.

  • Algorithme
  • Descente depuis la droite
  • Échange et renversement
  • Générer les permutations
  • Générer les permutations, bis
  • Problème de la somme

Un processus

Décrivons le passage d'un entier au suivant sur un exemple. On part par exemple de 361485972 (premier nombre du second extrait donné ci-dessus).

Intuitivement, on cherche à garder le "préfixe" identique le plus long possible puisqu'ajouter 1 à un entier commence par perturber les chiffres de droite.

On procède aux étapes suivantes:

  1. On repère et souligne le plus long "suffixe" en fin de nombre et qui soit en ordre croissant lorsqu'on le parcourt de la droite vers la gauche. Ici: 361485972.
  2. Le chiffre suivant (lorsqu'on va de la droite vers la gauche) est ici 5: 361485972. On passe en rouge les chiffres soulignés plus grands que le chiffre vert: 361485972.
  3. On échange le chiffre vert et le plus petit rouge: 361487952.
  4. Enfin, on inverse l'ordre d'écriture des soulignés: 361487259.

La permutation qui suit A = 361485972 est B = 361487259.

Explication

Tentons maintenant de justifier un peu l'affirmation ci-dessus en cherchant à glisser une autre permutation entre A et B.

  • Si nous modifions le 3 en 1 ou 2 (par échange avec un chiffre occupant un autre rang), nous obtenons un entier plus petit que A donc qui ne peut pas se glisser entre A et B. Si nous modifions le 3 en 4, 5, 6, 7, 8, ou 9, nous obtenons un entier plus grand que B, donc qui ne se glisse pas entre A et B. On ne peut donc pas modifier le chiffre 3 pour trouver un entier entre A et B.
  • Sachant maintenant que le chiffre 3 doit rester identique si l'on veut définir un entier permutation entre A et B, le même raisonnement vaut pour le second chiffre (le chiffre 6).
  • Sachant maintenant que les deux premiers chiffres (3 et 6) doivent rester identiques, le même raisonnement vaut pour le troisième chiffre (le chiffre 1).
  • Et ainsi de suite: si l'on veut glisser un entier permutation entre A et B, tous les chiffres avant 5 doivent rester identiques.
  • La question suivante à se poser est: "Pouvait-on laisser le 5 identique?"
    Cela signifierait que la modification ne porterait que sur les chiffres soulignés. Mais tous les chiffres étant distincts et tous les chiffres avant les soulignés devant rester les mêmes, toute modification dans la partie soulignée ne peut se faire qu'en permutant les soulignés entre eux. Or les chiffres soulignés étant en ordre décroissant (dans la lecture de gauche à droite), toute perturbation ne peut que diminuer sa valeur et on obtiendrait donc un nombre qui se trouve avant A et qui ne se glisse donc pas entre A et B. Conclusion: il faut modifier le chiffre 5, et ce ne peut être qu'avec un échange avec un chiffre souligné (puisque les chiffres avant 5 sont fixes).
  • Nous cherchons donc maintenant à voir avec quel chiffre échanger 5. Pas avec un chiffre plus petit, sinon on obtient un entier inférieur à A. Il faut l'échanger avec un chiffre plus grand, et il est clair qu'il faut choisir le plus petit des plus grands (tout autre choix donnerait une valeur supérieure à ce choix).
  • On fait à ce moment l'échange et on obtient l'étape 361487952. Il est clair, vu la construction faite, que la partie soulignée est encore en ordre décroissant (dans la lecture de gauche à droite) et qu'avec les mêmes chiffres sur cette partie soulignée, on obtiendra la plus petite valeur possible en les disposant en ordre croissant, d'où la dernière étape.

On décide de renvoyer -1 si le contenu de la liste est rangé en ordre décroissant (de la gauche vers la droite).


def rangDesc(liste):
    fin = len(liste)-1
    for i in range(fin, 0, -1):
        if liste[i]>liste[i-1]:
            return i-1
    return -1     

def renverse(liste, a, b):
	"""
	La liste [..., L[a], L[a+1], L[a+2], ..., L[b-1], L[b], ...]
	devient [..., L[b], L[b-1], ..., L[a+2], L[a+1], L[a], ...]
	"""
	gauche = a
	droite = b
	while gauche < droite:
		liste[gauche], liste[droite] = liste[droite], liste[gauche]
		gauche += 1
		droite -= 1
		
		    

def echange(liste, indicepivot):
	"""
	la liste est supposée être de la forme
	[ ... ,  pivot, sous-liste de fin]
	où sous-liste de fin est en ordre décroissant.
	"""
	pivot = liste[indicepivot]
	indiceMinPG = indicepivot 

	while indiceMinPG+1 <len(liste) and liste[indiceMinPG+1] > pivot:
		indiceMinPG += 1
	
	liste[indicepivot], liste[indiceMinPG] = liste[indiceMinPG], pivot
	renverse(liste, indicepivot+1, len(liste)-1)
       

A partir d'une liste (par exemple celle de départ L=[1,2,3,4,5,6,7,8,9]), on obtient la permutation suivante par l'exécution de echange(L, rangDesc(L)).


 
def rangDesc(liste):
    fin = len(liste)-1
    for i in range(fin, 0, -1):
        if liste[i]>liste[i-1]:
            return i-1
    return -1
    


def renverse(liste, a, b):
	"""
	La liste [..., L[a], L[a+1], L[a+2], ..., L[b-1], L[b], ...]
	devient [..., L[b], L[b-1], ..., L[a+2], L[a+1], L[a], ...]
	"""
	gauche = a
	droite = b
	while gauche < droite:
		liste[gauche], liste[droite] = liste[droite], liste[gauche]
		gauche += 1
		droite -= 1
		
		    

def echange(liste, indicepivot):
	"""
	la liste est supposée être de la forme
	[ ... ,  pivot, sous-liste de fin]
	où sous-liste de fin est en ordre décroissant.
	"""
	pivot = liste[indicepivot]
	indiceMinPG = indicepivot 

	while indiceMinPG+1 < len(liste) and liste[indiceMinPG+1] > pivot:
		indiceMinPG += 1
	
	liste[indicepivot], liste[indiceMinPG] = liste[indiceMinPG], pivot
	renverse(liste, indicepivot+1, len(liste)-1)
    
     
    
    

		
     
 
    
def generePermutations(n):
    listeEntiers = [k for k in range(1,n+1)]
    
    indice = len(listeEntiers)
    while indice != -1:
        yield listeEntiers
        indice = rangDesc(listeEntiers)
        echange(listeEntiers, indice)
        
PERM =  generePermutations(3)  

compteur = 0   
for p in PERM:
    print(p)
    compteur += 1
    
print("Nombre de permutations: ", compteur)

On obtient:

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
Nombre de permutations:  6

Si l'on sait d'avance que l'on veut générer les permutations des entiers 1, 2, 3, ..., 9, il revient au même d'écrire l'algorithme suivant (moins modulable):


def genere():
    lettres = (1,2,3,4,5,6,7,8,9)
    liste = []
    for a in lettres:
        for b in [k for k in lettres if k!= a]:
            for c in [k for k in lettres if k not in (a,b)]:
                for d in [k for k in lettres if k not in (a,b,c)]:
                    for e in [k for k in lettres if k not in (a,b,c,d)]:
                        for f in [k for k in lettres if k not in (a,b,c,d,e)]:
                            for g in [k for k in lettres if k not in (a,b,c,d,e,f)]:
                                for h in [k for k in lettres if k not in (a,b,c,d,e,f,g)]:
                                    for i in [k for k in lettres if k not in (a,b,c,d,e,f,g,h)]:
                                        liste.append((a,b,c,d,e,f,g,h,i))
    return liste

def rangDesc(liste):
    fin = len(liste)-1
    for i in range(fin, 0, -1):
        if liste[i]>liste[i-1]:
            return i-1
    return -1
    


def renverse(liste, a, b):
	"""
	La liste [..., L[a], L[a+1], L[a+2], ..., L[b-1], L[b], ...]
	devient [..., L[b], L[b-1], ..., L[a+2], L[a+1], L[a], ...]
	"""
	gauche = a
	droite = b
	while gauche < droite:
		liste[gauche], liste[droite] = liste[droite], liste[gauche]
		gauche += 1
		droite -= 1
		
		    

def echange(liste, indicepivot):
	"""
	la liste est supposée être de la forme
	[ ... ,  pivot, sous-liste de fin]
	où sous-liste de fin est en ordre décroissant.
	"""
	pivot = liste[indicepivot]
	indiceMinPG = indicepivot 

	while indiceMinPG+1 <len(liste) and liste[indiceMinPG+1] > pivot:
		indiceMinPG += 1
	
	liste[indicepivot], liste[indiceMinPG] = liste[indiceMinPG], pivot
	renverse(liste, indicepivot+1, len(liste)-1)
    
   
    
def generePermutations(n):
    listeEntiers = [k for k in range(1,n+1)]
    
    indice = len(listeEntiers)
    while indice != -1:
        yield listeEntiers
        indice = rangDesc(listeEntiers)
        echange(listeEntiers, indice)
        
def recherche():
	liste = []
	for m in generePermutations(9):
		e1 = 100*m[0] + 10*m[1] + m[2] 
		e2 = 100*m[3] + 10*m[4] + m[5] 
		if e1 < e2: # si a + b = c on garde le triplet (a,b,c) avec a < b et on rejette le "symétrique" (b,a,c)
			e3 = 100*m[6] + 10*m[7] + m[8] 
			if e1 + e2 == e3:
				liste.append((e1,e2,e3))
	return liste
        
 
for solution in recherche():
	print(solution)

On obtient:

(124, 659, 783)
(125, 739, 864)
(127, 359, 486)
(127, 368, 495)
(128, 367, 495)
(128, 439, 567)
(129, 357, 486)
(129, 438, 567)
(129, 654, 783)
(129, 735, 864)
(134, 658, 792)
(135, 729, 864)
(138, 429, 567)
(138, 654, 792)
(139, 428, 567)
(139, 725, 864)
(142, 596, 738)
(142, 695, 837)
(143, 586, 729)
(145, 692, 837)
(146, 583, 729)
(146, 592, 738)
(152, 487, 639)
(152, 784, 936)
(154, 629, 783)
(154, 638, 792)
(154, 782, 936)
(157, 329, 486)
(157, 482, 639)
(158, 634, 792)
(159, 327, 486)
(159, 624, 783)
(162, 387, 549)
(162, 783, 945)
(163, 782, 945)
(167, 328, 495)
(167, 382, 549)
(168, 327, 495)
(173, 286, 459)
(173, 295, 468)
(175, 293, 468)
(176, 283, 459)
(182, 367, 549)
(182, 394, 576)
(182, 457, 639)
(182, 493, 675)
(182, 754, 936)
(182, 763, 945)
(183, 276, 459)
(183, 492, 675)
(183, 546, 729)
(183, 762, 945)
(184, 392, 576)
(184, 752, 936)
(186, 273, 459)
(186, 543, 729)
(187, 362, 549)
(187, 452, 639)
(192, 384, 576)
(192, 483, 675)
(192, 546, 738)
(192, 645, 837)
(193, 275, 468)
(193, 482, 675)
(194, 382, 576)
(195, 273, 468)
(195, 642, 837)
(196, 542, 738)
(214, 569, 783)
(214, 659, 873)
(215, 478, 693)
(215, 748, 963)
(216, 378, 594)
(216, 738, 954)
(218, 349, 567)
(218, 376, 594)
(218, 439, 657)
(218, 475, 693)
(218, 736, 954)
(218, 745, 963)
(219, 348, 567)
(219, 438, 657)
(219, 564, 783)
(219, 654, 873)
(234, 657, 891)
(235, 746, 981)
(236, 718, 954)
(236, 745, 981)
(237, 654, 891)
(238, 419, 657)
(238, 716, 954)
(239, 418, 657)
(241, 596, 837)
(243, 576, 819)
(243, 675, 918)
(245, 673, 918)
(245, 718, 963)
(245, 736, 981)
(246, 573, 819)
(246, 591, 837)
(246, 735, 981)
(248, 319, 567)
(248, 715, 963)
(249, 318, 567)
(251, 397, 648)
(254, 619, 873)
(254, 637, 891)
(257, 391, 648)
(257, 634, 891)
(259, 614, 873)
(264, 519, 783)
(269, 514, 783)
(271, 593, 864)
(271, 683, 954)
(273, 546, 819)
(273, 591, 864)
(273, 645, 918)
(273, 681, 954)
(275, 418, 693)
(275, 643, 918)
(276, 318, 594)
(276, 543, 819)
(278, 316, 594)
(278, 415, 693)
(281, 394, 675)
(281, 673, 954)
(283, 671, 954)
(284, 391, 675)
(291, 357, 648)
(291, 384, 675)
(291, 546, 837)
(291, 573, 864)
(293, 571, 864)
(294, 381, 675)
(296, 541, 837)
(297, 351, 648)
(314, 658, 972)
(317, 529, 846)
(317, 628, 945)
(318, 627, 945)
(318, 654, 972)
(319, 527, 846)
(324, 567, 891)
(324, 657, 981)
(327, 519, 846)
(327, 564, 891)
(327, 618, 945)
(327, 654, 981)
(328, 617, 945)
(329, 517, 846)
(341, 586, 927)
(342, 576, 918)
(346, 572, 918)
(346, 581, 927)
(352, 467, 819)
(354, 618, 972)
(354, 627, 981)
(357, 462, 819)
(357, 624, 981)
(358, 614, 972)
(362, 457, 819)
(364, 527, 891)
(367, 452, 819)
(367, 524, 891)
(372, 546, 918)
(376, 542, 918)
(381, 546, 927)
(386, 541, 927)

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

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: [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 4

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:

  • Générer les permutations des entiers 1, 2, 3, ..., n-1.
  • 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.
  • 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.
  • ...

De façon générique: à 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)