Path: ...!weretis.net!feeder8.news.weretis.net!news.mixmin.net!aioe.org!No6DEx/YTI7k1hrrhSmZAA.user.46.165.242.75.POSTED!not-for-mail
From: Alain Ketterlin <alain@universite-de-strasbourg.fr.invalid>
Newsgroups: fr.comp.lang.python
Subject: Re: [NON RESOLU] : Panne en Python...
Date: Sun, 02 Oct 2022 13:35:24 +0200
Organization: =?utf-8?Q?Universit=C3=A9?= de Strasbourg
Message-ID: <87sfk6wj9f.fsf@universite-de-strasbourg.fr.invalid>
References: <th0qot$afg6$1@dont-email.me> <thar3q$hqs$1@gioia.aioe.org>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Injection-Info: gioia.aioe.org; logging-data="35212"; posting-host="No6DEx/YTI7k1hrrhSmZAA.user.gioia.aioe.org"; mail-complaints-to="abuse@aioe.org";
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.2 (gnu/linux)
Cancel-Lock: sha1:qlDTm4D5AOaBARcW+I3A1Yob/tg=
X-Notice: Filtered by postfilter v. 0.9.2
Bytes: 7361
Lines: 164

AIEO <zzz@aol.com> writes:

> Le 28/09/2022 =C3=A0 08:49, Dominique a =C3=A9crit :
>
> Bon, j'abdique. J'ai tent=C3=A9 avec itertools.permutations. Cette foncti=
on
> est tr=C3=A8s int=C3=A9ressante, mais elle =C3=A9choue avec 15 chiffres =
=3D> freeze de
> mon PC !

Avec 15 chiffres il y a 15! permutations (=C3=A0 peu pr=C3=A8s 1300 milliar=
ds).
Ton PC n'est pas gel=C3=A9, il travaille : s'il produit une permutation par
nano-secondes, il mettra 20 minutes. (Une permutation par nano-seconde ?
M=C3=AAme pas en r=C3=AAve. 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=C3=A9sultat, celui-ci prend
trop de place (130 Go multipli=C3=A9 par la taille d'un liste -- quelques
dizaines d'octets).

> J'ai recopi=C3=A9 la solution du livre :

Bon sang mais qui =C3=A9crit des trucs pareils, et qui les publie ? Il
devrait y avoir une taxe carbone sp=C3=A9ciale pour ce genre de code. Et tu
devrais te faire rembourser.

> l15=3D[n for n in range(1,16)]
> v=3D[[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 =C3=A0 un
point de la recherche on choisit x, le suivant ne peut =C3=AAtre qu'un
=C3=A9l=C3=A9ment de v[x-1]. Par exemple v[4-1] c'est [5,12], cad tous les =
nombres
qui peuvent appara=C3=AEtre apr=C3=A8s 4.

(Personnellement, j'aurais =C3=A9crit v=3D[None, [3,8,15], ...], comme cela
onpourrait utiliser simplement v[x].)

> t=3D[]
> 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)=3D=3Dl15:
>         print(l)

Quelque chose a chang=C3=A9 l'indentation. Je suppose que t.append() est da=
ns
le corps de la derni=C3=A8re boucle, et le reste apr=C3=A8s le nid de boucl=
es.

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=C3=A9rifier ensuite si elles sont effectivement des r=C3=A9ponses. Il faut
vraiment dessiner ce que fait ce programme sous la forme d'un arbre.

Donc, on essaie toutes les possibilit=C3=A9s pour le premier nombre. Pour
chacune de ces possibilit=C3=A9s, on essaie les candidats (indiqu=C3=A9s pa=
r v)
pour le nombre suivant. Et pour chacun de ceux-l=C3=A0, le suivant du suiva=
nt
(indiqu=C3=A9 par v[suivant-1]). Etc. Pour les 15 chiffres. Il faut faire
l'exercice =C3=A0 la main pour se rendre compte (j'avais mis un extrait dans
une r=C3=A9ponse pr=C3=A9c=C3=A9dente, il y en a un autre fragment plus bas=
).

Quand on ex=C3=A9cut=C3=A9 la boucle la plus profonde, on a produit une s=
=C3=A9quence
de 15 nombres o=C3=B9 la somme de deux nombres cons=C3=A9cutifs est un carr=
=C3=A9. Y
compris des trucs sans espoir, du genre [1, 8, 1, 8, ..., 8, 1]. La
condition qui reste =C3=A0 v=C3=A9rifier est que tous les nombres sont diff=
=C3=A9rents.

Le code ci-dessus ne fait pas la v=C3=A9rification tout de suite. Il collec=
te
toutes les suites de 15 nombres [a,...,o] dans une liste (t). Il y en a
s=C3=BBrement un paquet : ton "print(t)" doit etre illisible. Mais tu faire
"print ([a, ..., o])" dans la derni=C3=A8re boucle.

Apr=C3=A8s avoir fait le tour de toutes les possibilit=C3=A9s, on repasse l=
a liste
t en revue, et on affiche seulement les listes qui r=C3=A9pondent au crit=
=C3=A8re
"tous les chiffres sont diff=C3=A9rents". On pourrait changer le test
"sorted(l) =3D=3D l15" en "len (set(l)) =3D=3D 15", ce qui =C3=A9viterait u=
n tri.

On pourrait aussi faire ce test =C3=A0 l'int=C3=A9rieur de la boucle la plus
profonde, cela =C3=A9viterait de remplir t avec des listes incorrectes.


Le probl=C3=A8me est =C3=A9vident : on place dans t des tas de listes qui ne
sont pas des permutations. Par exemple=20

- a=3D1 -> v[0] =3D [3, 8, 15]
  - b=3D3
    ...
  - b=3D8 -> v[7] =3D [1, 8]
    - c=3D1
      ...
    - c=3D8
      ...
  - b=3D15
    ...

Pour les cas c=3D1 et c=3D8 on va encore faire chaque fois 12 boucles
imbriqu=C3=A9es pour rien (parce qu'on a d=C3=A9j=C3=A0 utilis=C3=A9 1 et 8=
, il y a donc des
doublons dans la liste finale).

On peut garder l'id=C3=A9e des boucles imbriqu=C3=A9es, et emp=C3=AAcher to=
ut de suite
de continuer si v nous indique un nombre d=C3=A9j=C3=A0 utilis=C3=A9

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=C3=A9cessaire 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=C3=A9j=C3=A0 on va beaucoup plus vite, quand on arrive d=
ans la
boucle la plus profonde (apr=C3=A8s 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 =C3=A9liminent vraiment beaucoup de cas.


Evidemment si on veut maintenant les solutions avec par exemple les
nombres de 1 =C3=A0 30 au lieu de 15, il faut =C3=A9crire 30 boucles et 28 =
tests
pour trouver les 40 solutions... Le programme a une taille
proportionnelle =C3=A0 la taille de la liste. On peut faire mieux, mais je
crois que je l'ai d=C3=A9j=C3=A0 dit.

-- Alain.