AIEO <
zzz@aol.com> writes:
Le 28/09/2022 à 08:49, Dominique a écrit :
>
Bon, j'abdique. J'ai tenté avec itertools.permutations. Cette fonction
est très intéressante, mais elle échoue avec 15 chiffres => freeze de
mon PC !
Avec 15 chiffres il y a 15! permutations (à peu près 1300 milliards).
Ton PC n'est pas gelé, il travaille : s'il produit une permutation par
nano-secondes, il mettra 20 minutes. (Une permutation par nano-seconde ?
Même pas en rêve. Avec une par micro-seconde, il faut 360 heures, soit
15 jours. Et je serais surpris qu'on y arrive en Python.)
Mais tu n'auras vraisemblablement jamais le résultat, celui-ci prend
trop de place (130 Go multiplié par la taille d'un liste -- quelques
dizaines d'octets).
J'ai recopié la solution du livre :
Bon sang mais qui écrit des trucs pareils, et qui les publie ? Il
devrait y avoir une taxe carbone spéciale pour ce genre de code. Et tu
devrais te faire rembourser.
l15=[n for n in range(1,16)]
v=[[3,8,15],[7,14],[1,6,13],[5,12],[4,11],[3,10],[2,9],[1,8],[7],[6,15],[5,14],[4,13],[3,12],[2,11],[1,10]]
On trouve dans v les successeurs possibles d'un nombre x. Donc si à un
point de la recherche on choisit x, le suivant ne peut être qu'un
élément de v[x-1]. Par exemple v[4-1] c'est [5,12], cad tous les nombres
qui peuvent apparaître après 4.
(Personnellement, j'aurais écrit v=[None, [3,8,15], ...], comme cela
onpourrait utiliser simplement v[x].)
t=[]
for a in range(1,16):
for b in v[a-1]:
for c in v[b-1]:
for d in v[c-1]:
for e in v[d-1]:
for f in v[e-1]:
for g in v[f-1]:
for h in v[g-1]:
for i in v[h-1]:
for j in v[i-1]:
for k in v[j-1]:
for l in v[k-1]:
for m in v[l-1]:
for n in v[m-1]:
for o in v[n-1]:
>
t.append([a,b,c,d,e,f,g,h,i,j,k,l,m,n,o])
#print(t)
for l in t:
if sorted(l)==l15:
print(l)
Quelque chose a changé l'indentation. Je suppose que t.append() est dans
le corps de la dernière boucle, et le reste après le nid de boucles.
Ce truc est une variante de ce que proposait Stefan. Pour comprendre, il
faut se souvenir que le but ici est de chercher une solution, ce qui
veut dire produire un certain nombre de suites de 15 chiffres, pour
vérifier ensuite si elles sont effectivement des réponses. Il faut
vraiment dessiner ce que fait ce programme sous la forme d'un arbre.
Donc, on essaie toutes les possibilités pour le premier nombre. Pour
chacune de ces possibilités, on essaie les candidats (indiqués par v)
pour le nombre suivant. Et pour chacun de ceux-là, le suivant du suivant
(indiqué par v[suivant-1]). Etc. Pour les 15 chiffres. Il faut faire
l'exercice à la main pour se rendre compte (j'avais mis un extrait dans
une réponse précédente, il y en a un autre fragment plus bas).
Quand on exécuté la boucle la plus profonde, on a produit une séquence
de 15 nombres où la somme de deux nombres consécutifs est un carré. Y
compris des trucs sans espoir, du genre [1, 8, 1, 8, ..., 8, 1]. La
condition qui reste à vérifier est que tous les nombres sont différents.
Le code ci-dessus ne fait pas la vérification tout de suite. Il collecte
toutes les suites de 15 nombres [a,...,o] dans une liste (t). Il y en a
sûrement un paquet : ton "print(t)" doit etre illisible. Mais tu faire
"print ([a, ..., o])" dans la dernière boucle.
Après avoir fait le tour de toutes les possibilités, on repasse la liste
t en revue, et on affiche seulement les listes qui répondent au critère
"tous les chiffres sont différents". On pourrait changer le test
"sorted(l) == l15" en "len (set(l)) == 15", ce qui éviterait un tri.
On pourrait aussi faire ce test à l'intérieur de la boucle la plus
profonde, cela éviterait de remplir t avec des listes incorrectes.
Le problème est évident : on place dans t des tas de listes qui ne
sont pas des permutations. Par exemple
- a=1 -> v[0] = [3, 8, 15]
- b=3
...
- b=8 -> v[7] = [1, 8]
- c=1
...
- c=8
...
- b=15
...
Pour les cas c=1 et c=8 on va encore faire chaque fois 12 boucles
imbriquées pour rien (parce qu'on a déjà utilisé 1 et 8, il y a donc des
doublons dans la liste finale).
On peut garder l'idée des boucles imbriquées, et empêcher tout de suite
de continuer si v nous indique un nombre déjà utilisé
for a in range(1,16):
for b in v[a-1]:
for c in v[b-1]:
if c not in [a,b]: # <- sinon, on passe au b suivant
for d in v[c-1]:
if d not in [a,b,c]: # <- sinon on passe au c suivant
for e in v[d-1]:
if e not in [a,b,c,d]: # etc.
for f in v[e-1]:
... etc.
(le test n'est pas nécessaire dans le boucle sur b, il n'y a pas de x
tel que x est dans v[x-1])
Si on fait cela, déjà on va beaucoup plus vite, quand on arrive dans la
boucle la plus profonde (après le test qu'on y ajoute), on a une
solution.
On a l'impression qu'on fait beaucoup plus de travail, mais ce n'est pas
vrai, parce que les tests éliminent vraiment beaucoup de cas.
Evidemment si on veut maintenant les solutions avec par exemple les
nombres de 1 à 30 au lieu de 15, il faut écrire 30 boucles et 28 tests
pour trouver les 40 solutions... Le programme a une taille
proportionnelle à la taille de la liste. On peut faire mieux, mais je
crois que je l'ai déjà dit.
-- Alain.
Panne en Python...
Re: Panne en Python...
