Bonjour
1 2 3 1 2 1 3 me semble pas mal.

Mais 3 2 3 1 3 2 3 n'est pas plus long et ouvre des perspectives
4 3 4 2 4 3 4 1 4 3 4 2 4 3 4

C'est plus que pas mal pour comme il est  impossible de faire mieux. Par contre pour , même si les conditions sont respectées, il y a moyen de faire plus court donc pas mal effectivement

Dommage, travailler par récurrence me plaisait comme idée et me semblait déjà pas mal pour retrouver les permutations. Pour le moment, je ne vois pas d'autre idée générale.

J'avoue, ta version a le mérite d'être simple mais l'ordre de grandeur sera nettement mieux que ce que tu penses (polynomial et pas exponentiel), il faut avoir pitié des esclaves numériques qui vont traiter les données
Disons que tu étais mieux parti pour optimiser avec ta première proposition, en effet à partir du moment où un chiffre n'apparait qu'une fois, on est fichu car on se retrouve à doubler la taille du cas précédent.

Ouais. Mais je n'ai pas d'autre idée que de bidouiller pour le moment, et je n'ai pas envie de bidouiller.

Bon d'accord mais même sans avoir la version optimisée, essayons de faire mieux à peu de frais et sans trop bidouiller.
En admettant qu'on découpe la suite à trouver en morceaux successifs, qu'est-ce qu'on peut mettre dans le i^ème morceau pour être sûr d'y trouver le chiffre que l'on veut (c'est à dire le i^ème chiffre de notre permutation) ?

Ouais, on peut répéter fois  1 2 3 ... n, ce qui fait . OK, c'est nettement mieux que .. On peut même enlever le premier 1 et le dernier n, ce qui fait
2 3 4 1 2 3 4 1 2 3 4 1 2 3

Ah ben voilà, l'ordre de grandeur est le bon, maintenant il faut encore un peu optimiser ce qu'on met dans chaque morceau.
Tu as une bonne idée pour enlever le premier et le dernier mais pourquoi ne pas la pratiquer entre chaque morceau ? Toujours sans vraiment bidouiller
Bon ensuite, pour avoir la version vraiment optimale, il faut quand même un peu bidouiller ce qu'on met dans chaque morceau, je donnerai un indice mais pas avant demain soir histoire de laisser un peu de suspens.

Alors l'idée est de mélanger ce que propose GBZM entre tous les morceaux et le fait qu'au moins un des morceaux contiendra (du moins dans la plupart des cas) 2 chiffres successifs de notre permutation si on commence tous les morceaux par le même chiffre.
C'est compliqué à donner un indice sans donner la réponse du coup dites moi quand vous voulez le résultat si personne n'a envie de bidouiller.

Et y a-t-il une démonstration du fait que c'est bien la longueur minimale ?

Par récurrence et une initialisation par ordinateur, on devrait s'en sortir, et d'ailleurs cela devrait peut-être t'aider à trouver.
On rajoute un premier morceau devant la suite du rang précédent, morceau qui doit être aussi rentable que possible autrement dit, il doit être suffisant pour les configurations n***... et *n**...
On introduit des n à des endroits bien choisis dans la suite du rang précédent de sorte à valider les configurations **n**... jusqu'à ...***n, évidemment on en rajoute le moins possible.

Ça ne répond pas vraiment à la question de la démonstration de la minimalité.

Je n'aurais pas mieux

Bonjour,
Je ne suis pas sûr d' avoir bien compris...
pour 4:
34212343243132  soit 14  chiffres mais on devrait tomber à 12

Suite,
Je propose 13 pour n=4
2124234123421

En effet, on devrait pouvoir tomber à 12 mais dans ta proposition avec 13 comment on fait pour obtenir 3214 ? Si on ne peut pas, elle n'est pas valable malheureusement

Je tente 12
214234123421
ce qui donnerait la serrure suivante.

c'est très joli mais et 3214 alors ? Je ne le vois toujours pas

Effectivement ;
j'ai un  13 corrigé mais pour 12 toujours un manquant

Bonjour,
Après une pénible nuit de grippe..
En observant la solution de GBMZ pour n=3
on voit que la répétition 123123 ne suffit pas pour le seul cas 321
et qu'il faut finir par 1.
J'en ai déduit que pour 4 il faudra faire pareil.
soit la suite  1234123412341.
Par analogie on peut "postuler" que pour  n il faudra n(n-1)+1 chiffres.
Soit pour 5  : 21 chiffres 4 séquences de1à 5+1
123451234512345123451

En fait, on peut même utiliser seulement chiffres, dis moi si tu veux la manière de le construire ou si tu préfères chercher encore un peu.

Merci,
Il vaut mieux laisser venir d'autres participants ,mais je serais
curieux de  voir une solution  12 chiffres pour 3.

Bonjour,
Pas de succès ...
Je n'ai pas trouvé de suite <13 pour n=3
Merci de me donner l'astuce

Voilà ma source mais pour les non anglophones
On repart de la solution de GBZM 1231213
Puis on rajoute 123...n devant la suite et le chiffre n devant chacun des n-3 derniers 2 de la suite
123412314213
1234512341523145213
1234561234516234156231456213

Bonjour et merci.
Il semble que  la solution n'est pas unique.
Par exemple pour n=4
123412314213 et 124312413421
la première ayant l'avantage de se générer plus facilement.