Panne en Python...

Dominique <zzz@aol.com> writes:

Il m'est demandé "d'arranger la liste en 15 nombres entiers de 1 Í  15 de
telle sorte que la somme de 2 nombres voisins soit toujours un carré
parfait".

...

Je ne suis pas sÍ»r d'être parti dans la bonne direction. Ensuite, si
oui, quelle indication me donneriez-vous pour répondre Í  la question ?
Si non, quelle piste me faudrait-il explorer ?
Merci et bonne journée,

Bonne journée Í  vous aussi !

Nous devons parcourir toutes les permutations de la liste
des nombres de 1 Í  15 (« générateur ») et afficher celles de
ces listes qui répondent Í  la demande (« filtre »).

La bibliothèque standard contient déjÍ  une fonction standard
pour générer de telles permutations.

Cependant, cela conduit Í  un long temps d'exécution du
programme.

Pour accélérer le processus, il faut « mettre le filtre dans
le générateur » ! En d'autres termes, « réduire l'espace de
recherche ».

Pour ce faire, vous devez écrire votre propre fonction pour
générer la permutation. On peut alors reconnaÍ®tre très tÍ´t
quand le début d'une liste ne répond pas Í  la demande et
supprimer alors la génération de toutes les permutations
avec ce début.

De cette manière, il est possible d'écrire un programme qui
donne immédiatement deux solutions.

Dominique <zzz@aol.com> writes:

[...]

Il m'est demandé "d'arranger la liste en 15 nombres entiers de 1 Í  15
de telle sorte que la somme de 2 nombres voisins soit toujours un
carré parfait".

J'ai créé une liste (resu) avec chaque couple susceptible de me donner
un carré parfait :

liste=[2,14,11,5,8,12,6,3,1,9,7,13,5,4,10,15]
resu=[]
deb=[x for x in range(1,16)]
fin=[x for x in range(1,16)]
for i in deb:
for j in fin:
tot=i+j
tot1=[i,j]
tot1.sort()
if tot1 not in resu and i!=j and tot**.5==int(tot**.5):
resu.append(tot1)

Je ne suis pas sÍ»r d'être parti dans la bonne direction.

En fait, pas vraiment. LÍ  tu cherches les couples de nombres formant un
carré, mais le problème principal dans cet exercice c'est d'enchaÍ®ner
les couples...

Au passage : tu n'as pas vraiment besoin de deb et fin, qui ne servent
qu'aux boucles, donc :

for i in range (1, 16):
for j in range (1, 16):
...

Ensuite, tu tries les deux éléments et tu vérifies qu'ils sont
différents, parce que tu veux des couples (i,j) avec i<j. Autant générer
tout de suite les couples pertinents :

for i in range (1, 16):
for j in range (i+1, 16):
...

Ensuite, si oui, quelle indication me donneriez-vous pour répondre Í 
la question ? Si non, quelle piste me faudrait-il explorer ?

Je ne vois pas de raison de penser que 1) il y a forcément une solution,
et 2) on peut directement déterminer la solution (si elle existe donc).
J'en conclue qu'il faudra chercher, c'est-͠-dire essayer d'enchaͮner les
nombres, de toutes les façons possibles, et de voir si on trouve une
solution. C'est donc un problème combinatoire.

(Note que si il y a une solution, alors il y en a au moins une
deuxième -- qui est la liste inversée.)

Ensuite, remarque qu'avec des nombres entre 1 et 15, la somme est au
plus 29. Les seuls carrés qui peuvent apparaÍ®tre sont donc 4, 9, 16 et
25. (Ca simplifie un peu la recherche.)

Quand on cherche comme cela parmi plein de possibilités, il faut
s'imaginer en plein milieu de la recherche : on a déjÍ  enchaÍ®né quelques
nombres (on appelle cela sequence), qu'on ne peut donc plus utiliser :
on appelle restant l'ensemble des nombres encore utilisable (c'est
{1,2,...,15} moins les nombres de sequence, mais c'est pratique de lui
donner un nom).

Au début séquence = [], et restant = {1,...,15}. On va essayer toutes
les premières étapes. Chaque fois qu'on a choisi un nombre x, on se
retrouve avec une nouvelle version : sequence + [x], restant - {x}. On a
donc une (potentiellement grande) hiérarchie de cas Í  essayer :

- on choisit 1 : sequence = [1], restant = {2,...,15}
- on choisit 2, mais 1+2 n'est pas un carré : perdu
- on choisit 3 : sequence = [1,3], restant = {2,4,...,15}
- on choisit 2 : perdu
- on choisit 4 : perdu
... idem avec tous les autres
- on choisit 4 : perdu
...
- on choisit 8 : sequence = [1,8], restant = {2,...,7,9,...,15}
- on choisit 2 : perdu
...
...
- on choisit 2 : sequence = [2], restant = {1,3,...,15}
- on choisit 1 : perdu
...

Note que c'est vraiment une grande hiérachie, avec 15 cas au premier
niveau, ayant chacun 14 sous-cas, qui chacun a potentiellement 13
sous-sous-cas. Mais 1) il y plein de cas qu'on abandonne rapidement, et
2) si on trouve une solution, on sera dans un sous-sous-...-sous-cas
(avec 14 "sous").

Au fait : quand est-ce qu'on s'arrête ? DéjÍ , quand on est bloqué
(perdu). Et aussi quand on a tout essayé. Quand est-ce qu'on a trouvé
une solution : quand sequence est de longueur 15 (et restant est vide).

Ce qu'on voit avec la description ci-dessus, c'est qu'il ne suffit pas
de faire deux boucles imbriquées, il faudrait en faire quinze (ou
quatorze), pour essayer tous les ordres des quinze nombres.

Mais on ne va pas faire cela, on va utiliser Í  la place une fonction
récursive, qui va parcourir tout l'arbre des possibilités. On tous les
éléments :

def cherche (sequence, restant):
if ... restant est vide ...:
on a une solution dans sequence -> print
else:
for x in restant: # on essaie tout ce qu'on peut faire
if ... sequence[-1] + x est un carré ...:
cherche (sequence+[x], restant-{x}) # sous-cas

Attention : cette fonction utilise le dernier élément de sequence, il
faut donc l'appeler avec toutes les séquence de longueur 1 possibles

for i in range (1, 16):
cherche ([i], {1,2,...,15} - {i})

Ou alors on intègre cela Í  la fonction, qui devient

def cherche (sequence, restant):
if len (sequence) == 0:
for x in restant:
cherche ([x], {1,...} - {x})
elif ... restant est vide ...:
... comme ci-dessus ...

et on apelle simplement cherche ([], {1,...,15})

C'est l'idée. On peut faire des choses pour simplifier. Par exemple, le
test "sequence[-1]+x est un carré" est un peu compliqué. On peut Í  la
place tester les quatre carrés possibles. Au lieu de

for x in restant:
if ... sequence[-1]+x est un carré ...:
cherche (...)

on peut écrire

for carre in [4, 9, 16, 25]:
candidat = carre - sequence[-1]
if candidat in restant:
cherche (...)

mais ce n'est pas très important pour l'algorithme.

-- Alain.

P/S: cela permet de trouver qu'il n'y a que deux solutions, symétriques

Alain Ketterlin <alain@universite-de-strasbourg.fr.invalid> writes:

Ce qu'on voit avec la description ci-dessus, c'est qu'il ne suffit pas
de faire deux boucles imbriquées, il faudrait en faire quinze (ou
quatorze), pour essayer tous les ordres des quinze nombres.

Mais on ne va pas faire cela, on va utiliser Í  la place une fonction
récursive

On peut résoudre le problème soit avec des boucles imbriquées,
soit avec des fonctions récursives (c'est-Í -dire des fonctions
qui s'appellent elles-mêmes). Pour quelqu'un qui n'est pas
encore Í  l'aise avec les fonctions récursives, une solution
avec des boucles imbriquées pourrait être plus facile -
ou vice versa : pour quelqu'un qui n'est pas encore Í  l'aise
avec les boucles imbriquées, une solution récursive pourrait
être plus facile.

(On pourrait probablement même écrire une solution sans
boucles imbriquées et sans fonction récursive, si au lieu
d'une fonction récursive, on écrit 14 ou 15 fonctions [qui
sont très similaires entre elles]. Cela aiderait quelqu'un
qui n'arrive pas Í  comprendre les fonctions récursives,
mais qui est parfaitement heureux qu'une fonction appelle
une autre fonction).

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 !

J'ai recopié la solution du livre :

****************************

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]]
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)

****************************

Elle me donne deux réponses réciproques :

[8, 1, 15, 10, 6, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9]
[9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8]

Mais je n'arrive pas bien Í  comprendre cette solution...

Bonjour,

Le 02/10/2022 03:56, AIEO a écrit :

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 !

J'ai recopié la solution du livre :

Je n'ai pas compris cette solution tout de suite, mais après un peu de réflexion
c'est ok.

****************************

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]]

Ici, pour un entier a donné entre 1 et 15, v[a-1] est l'ensemble des entiers b
entre 1 et 15 (différents de a) tels que a + b est un carré.

Par exemple pour a=3, v[2]=[1,6,13], et on a :
3 + 1 = 4
3 + 6 = 9
3 + 13 = 16

[Note : il y a un nombre de trop dans v[]. Lequel est-ce ?]

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])

Ceci choisit pour chaque voisin d'un entier possible un autre entier tel que
la somme des deux soit un carré. Mais il est possible que la liste commence
par [1,3,1,... par exemple, o͹ le nombre 1 est répété.

#print(t)
for l in t:
if sorted(l)==l15:

LÍ  on trie la liste obtenue. Si tous les nombres sont différents, on doit
obtenir la liste triée des entiers de 1 Í  15, c'est-Í -dire l15.

print(l)

Seulement si c'est le cas, on affiche le résultat.

****************************

Elle me donne deux réponses réciproques :

[8, 1, 15, 10, 6, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9]
[9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8]

Mais je n'arrive pas bien Í  comprendre cette solution...

Voir l'explication ci-dessus.

Cordialement,
--
Olivier Miakinen

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

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.

Le 02/10/2022 Í  13:35, Alain Ketterlin a écrit :
Olivier et Alain,

Je vous remercie l'un et l'autre pour vos explications détaillées qui
m'ont permis d'y voir plus clair. Je me replongerai dedans dans d'autres
exercices. En effet, il y en a plusieurs qui font appel Í  combinaison de
valeurs.

LÍ , je cherche comment répondre Í  une question simple : soit le nombre
123456789, o͹ placer 3 signes + ou - de telle sorte qu'on obtienne 100 ?
Tous les chiffres doivent, bien sÍ»r, être utilisés et dans leur ordre
croissant, du style (faux ici) 1234-456-7+89
Je cherche Í  créer un ensemble de liste o͹ la première ferait de 1 Í  6
chiffres, la 2e idem mais du caractère 2 Í  7, la 3e 3 Í  8 et la dernière
4 Í  9. Puis je placerai toutes les combinaisons de + et de moins entre
pour voir si une me donne 100. Est-ce la bonne piste ? Je verrai...

Bon dimanche Í  tous,

Dominique

AIEO <zzz@aol.com> writes:

LÍ , je cherche comment répondre Í  une question simple : soit le nombre
123456789, o͹ placer 3 signes + ou - de telle sorte qu'on obtienne 100
? Tous les chiffres doivent, bien sÍ»r, être utilisés et dans leur
ordre croissant, du style (faux ici) 1234-456-7+89
Je cherche Í  créer un ensemble de liste o͹ la première ferait de 1 Í  6
chiffres, la 2e idem mais du caractère 2 Í  7, la 3e 3 Í  8 et la
dernière 4 Í  9. Puis je placerai toutes les combinaisons de + et de
moins entre pour voir si une me donne 100. Est-ce la bonne piste ? Je
verrai...

Oui c'est cela. Il faut découper les 9 chiffres en 4 parties, de toutes
les façons possibles, et pour chaque découpage placer les signes de
toutes les façons possibles, et tester si on a une solution. Dans cette
énigme, je ne vois pas de façon d'éliminer a priori des découpages (sauf
anecdote, du genre "que des plus", ou première partie de longueur 2 et
que des moins).

Note que si tu découpes en 4 parties de longueurs l1 l2 l3 et l4, tu as
des conditions :

1) 1 <= l1 <= 9 - 3 (il faut garder au moins un chiffre pour les 3 autres)
2) 1 <= l2 <= 9 - l1 - 2
3) 1 <= l3 <= 9 - l1 - l2 - 1
4) l4 = 9 - l1 - l2 - l3 est toujours fixé

Pour les opérations, c'est commode de consider des variables s1, s2, s3
qui peuvent prendre les valeurs -1 ou +1 : tu peux alors calculer le
résultat en écrivant a + s1*b + s2*c + s3*d, o͹ a b c et d sont les
valeurs des quatres parties. Si tu veux afficher joliment, tu peux
utiliser {-1: "-", +1: "+"}[s1] (ou même "?+-"[s1] mais ça c'est
ultra-geek).

-- Alain.

P/S: il y a une seule solution

Le 02/10/2022 Í  15:58, Alain Ketterlin a écrit :

P/S: il y a une seule solution

Tu es vexant, je planche lÍ -dessus depuis 2 jours :-))

--
Dominique
Esto quod es

AIEO <zzz@aol.com> writes:

P/S: il y a une seule solution

Tu es vexant, je planche lÍ -dessus depuis 2 jours :-))

Te laisse pas impressionner, je suis un vieux singe, je connais toutes
les grimaces (ou presque). Ce sont des problèmes classiques.

-- Alain.