Forum de mathématiques - Bibm@th.net

Ernst

Membre

Inscription : 30-01-2024

Messages : 325

Re : 15 boules à classer

j’ai remarqué que pour sept boules il suffisait de cinq recours à l’appareil.

Bonjour,

Personnellement il me faut six passages pour ranger parfaitement sept boules en barrette. Si elles sont disposées aux positions de 1 à 7 et qu’on ordonne successivement les triplets 1,3,7 puis 2,4,6 puis 3,4,5 puis 1,2,3 puis 5,6,7 puis 3,4,5 on obtiendra toujours une barrette parfaitement rangée. Avec une séquence plus courte je trouve toujours des exceptions.

Ernst

Membre

Inscription : 30-01-2024

Messages : 325

Re : 15 boules à classer

Bonjour,

Un peu mieux, une séquence fonctionnelle de 26 triplets qui range n’importe quelle barrette de 15 boules non identifiables :

# === Paramètres ===
N = 15
D_values = [2,11,9,12,3,14,5,8,4,13,6,15,7,10,1]  # 15 valeurs quelconques
S = [
    [1,5,15],[2,10,14],[3,11,13],[4,6,12],[5,8,11],
    [1,7,10],[6,9,15],[2,3,6],[10,12,14],[6,8,10],
    [1,4,5],[9,11,13],[5,7,9],[11,12,15],[3,4,5],
    [9,10,11],[13,14,15],[5,6,7],[7,8,9],[1,2,3],
    [11,12,13],[3,4,5],[9,10,11],[5,6,7],[7,8,9],
    [10,11,12]
    ]

bar = [None] + D_values  # base 1

print(f"\n{N} valeurs distinctes aux indices 1..{N} :")
print(bar[1:])

for step, (i, j, k) in enumerate(S, start=1):
    trio = sorted([bar[i], bar[j], bar[k]])
    bar[i], bar[j], bar[k] = trio
    print(f"on échange {[i,j,k]} et on obtient")
    print(f"{bar[1:]}({step})")

print(f"Barrette finale triée en {len(S)} étapes.\n")

À noter que la distribution précédente est maintenant triée à la vingt-troisième étape, mais les boules étant indistinctes, on ne peut bien sûr pas le savoir.

Tout contre-exemple est bienvenu, mes vérifications étant loin d’épuiser les 15! distributions possibles.

jpp

Membre

Inscription : 31-12-2010

Messages : 1 160

Re : 15 boules à classer

Salut,

Ernst:  poste 51 , tu compares deux fois le même triplet 3,4,5 .  Bizarre quand-même.

2 boules ne doivent jamais se retrouver dans deux pesées.

1,2,4.
2,3,5
3,4,6
4,5,7
5,6,1
6,7,2
7,1,3. Chaque boule est comparée avec les six autres en trois pesées.

Ernst

Membre

Inscription : 30-01-2024

Messages : 325

Re : 15 boules à classer

tu compares deux fois le même triplet 3,4,5 .  Bizarre quand-même.

Hello jpp,

Oui, c’est normal, les pesées ne concernent pas les boules qui restent indistinctes, mais les emplacements. Avec quatre emplacements on peut imaginer la séquence [1,2,3], [2,3,4], [1,2,3] qui marche très bien. Le premier triplet pousse la boule lourde vers la droite, le deuxième la met à l’extrémité et ramène à la deuxième place la boule la plus légère si elle était tout à droite, et dans ce cas le dernier triplet met la plus légère tout à gauche.

2 boules ne doivent jamais se retrouver dans deux pesées.

1,2,4.
2,3,5
3,4,6
4,5,7
5,6,1
6,7,2
7,1,3. Chaque boule est comparée avec les six autres en trois pesées.

La caractéristique de ce tri 'en aveugle', c'est que les boules se déplacent et ce ne sont pas toujours les mêmes que l'on évalue quand près quelques mouvements on sélectionne des emplacements. Ceci dit, il est facile d’introduire ces données dans un programme Python et de le coller dans le cadre de gauche de Basthon :

# === Paramètres ===
N = 7
D_values = [6,3,1,7,5,2,4]  # 7 valeurs quelconques

# === attention, triplets en ordre ascendant ===
S = [[1,2,4],[2,3,5],[3,4,6],[4,5,7],[1,5,6],[2,6,7],[1,3,7]]

bar = [None] + D_values  # base 1

print(" ");print(f"{N} valeurs distinctes aux indices 1..{N} :")
print(bar[1:])

for step, (i, j, k) in enumerate(S, start=1):
    trio = sorted([bar[i], bar[j], bar[k]])
    bar[i], bar[j], bar[k] = trio
    print(f"on échange {[i,j,k]} et on obtient")
    print(f"{bar[1:]}({step})")

print(f"Barrette finale en {len(S)} étapes.");print(" ")
 

En cliquant ‘Exécuter’ en bas on produit :

7 valeurs distinctes aux indices 1..7 :
[6, 3, 1, 7, 5, 2, 4]
on échange [1, 2, 4] et on obtient
[3, 6, 1, 7, 5, 2, 4](1)
on échange [2, 3, 5] et on obtient
[3, 1, 5, 7, 6, 2, 4](2)
on échange [3, 4, 6] et on obtient
[3, 1, 2, 5, 6, 7, 4](3)
on échange [4, 5, 7] et on obtient
[3, 1, 2, 4, 5, 7, 6](4)
on échange [1, 5, 6] et on obtient
[3, 1, 2, 4, 5, 7, 6](5)
on échange [2, 6, 7] et on obtient
[3, 1, 2, 4, 5, 6, 7](6)
on échange [1, 3, 7] et on obtient
[2, 1, 3, 4, 5, 6, 7](7)
Barrette finale en 7 étapes.
 

et on s’aperçoit que parfois cela ne marche pas toujours aussi bien qu'on le souhaiterait...

renéb

Membre

Inscription : 15-01-2023

Messages : 61

Re : 15 boules à classer

Bonsoir,

j’ai remarqué que pour sept boules il suffisait de cinq recours à l’appareil.

Ben oui il en faut 6;  j'avais en tête une résolution de ce défit en partageant  les données en quatre groupes, de les classer léger ou lourd pour, ensuite, les réunir.
Cette scission est possible par groupes de 7 chacun départagé en + lourd ou plus léger
J'y suis parvenu mais j'égalise les 27 recours pour classer les 15 boules.
Python est d'une grande aide pour tester les trouvailles.
Je cherche encore.

renéb

Membre

Inscription : 15-01-2023

Messages : 61

Re : 15 boules à classer

Bonjour,

Ernst,

Bravo!

J'ai testé ton algorithme avec 100000  tirages au sort de 15 chiffres.
Quelques secondes et aucun pépin.
Il t'aura fallu pas mal de temps pour mettre en ordre les triplets, je présume.
Chapeau bas en tous cas.
C'est une méthode sur mesure et qu'on ne peut plus courte (pour l'instant).

A bientôt.

R.

Ernst

Membre

Inscription : 30-01-2024

Messages : 325

Re : 15 boules à classer

Il t'aura fallu pas mal de temps pour mettre en ordre les triplets, je présume.

Bonjour renéb,

Hé hé, je suis dessus depuis le 8 septembre, suite à ton intervention qui relançait le truc. J’ai mis du temps mais enfin ça y est, j’arrive moi aussi à ton premier résultat : 15 boules indistinctes, 25 passages de la machine à trois boules à la fois, rail qui se retrouve rangé quelle que soit la disposition de départ.

Ouf, il était temps. :-)

Ce que j'ai aimé dans cette histoire, c’est la mise au point d’un algorithme. L’écriture du code est une corvée que l’assistance numérique me rend maintenant moins pénible (encore que), la réflexion peut enfin consacrer davantage de temps à l’heuristique elle-même.

Jusqu’à présent, je calculais le score d’un triplet en considérant les améliorations qu’il permettait (calcul du gain qu’obtient chaque permutation) et je choisissais d’appliquer le triplet ayant le score le plus haut. Une fois les rails améliorés, je recommençais sur ceux-ci.

Après réflexion, j’ai adopté le calcul d’un score pour les rails eux-mêmes sans plus m’occuper d’autre chose, plus ils sont dans le désordre et plus le score est élevé, le triplet qui permet d’obtenir le score le plus bas sur tous rails confondus est le meilleur à ce stade, et c’est lui que j’applique. Une fois les rails améliorés même chose, je recommence sur ceux-ci.

Nette amélioration :

# === Paramètres ===
N = 15
D_values = [2,11,9,12,3,14,5,8,4,13,6,15,7,10,1]  # 15 valeurs quelconques

# === attention, triplets en ordre ascendant ===
S = [[1,5,15],[2,10,14],[3,11,13],[4,9,12],[5,8,11],
     [6,10,15],[1,7,9],[9,13,14],[2,5,7],[1,3,6],
     [11,12,15],[6,9,11],[4,8,10],[10,12,13],[7,8,9],
     [3,4,5],[5,6,7],[1,2,3],[9,10,11],[13,14,15],
     [11,12,13],[3,4,5],[7,8,9],[9,10,11],[5,6,7]]
   
bar = [None] + D_values  # base 1

print(" ");print(f"{N} valeurs distinctes aux indices 1..{N} :")
print(bar[1:])

for step, (i, j, k) in enumerate(S, start=1):
    trio = sorted([bar[i], bar[j], bar[k]])
    bar[i], bar[j], bar[k] = trio
    print(f"on échange {[i,j,k]} et on obtient")
    print(f"{bar[1:]}({step})")

print(f"Barrette finale, {len(S)} étapes.");print(" ")
 

Pour le moment, cette séquence chez moi a déjà résisté à plus de dix milliards de distributions aléatoires (Fisher-Yates), j’ai l’impression que cette fois c’est du solide…

(finalement c'est bien toi qui avais raison, la solution c'est 25, je n'ai jamais réussi à obtenir moins)

syrac

Membre

Inscription : 27-05-2014

Messages : 201

Re : 15 boules à classer

Bonjour,

Je n'ai pas tout lu mais je suppose que le problème revient à utiliser l'algorithme de file d'attente de tas (ou de file d'attente prioritaire) pour réunir 5 sous-listes de 3 entiers triés en une liste unique triée. On obtient le résultat en 15 itérations :

import heapq

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

# Initialisation du tas : (valeur, index_liste, index_element)
heap = []
for i, sous_liste in enumerate(sous_listes):
    if sous_liste:  # s'assurer qu'elle n'est pas vide
        heapq.heappush(heap, (sous_liste[0], i, 0))

resultat = []
while heap:
    valeur, i, j = heapq.heappop(heap)
    resultat.append(valeur)
    # Si la sous-liste a un prochain élément
    if j + 1 < len(sous_listes[i]):
        heapq.heappush(heap, (sous_listes[i][j + 1], i, j + 1))

print(resultat)   # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

Chercher de la documentation en français sur cet algorithme n'est pas chose aisée (c'est sans doute une question de prompt), mais on en trouve en anglais.

renéb

Membre

Inscription : 15-01-2023

Messages : 61

Re : 15 boules à classer

Bonjour,

...réunir 5 sous-listes de 3 entiers triés en une liste unique triée.On obtient le résultat en 15 itérations :

Avec d'autres sous-listes de 3 entiers  triés , ça marche (évidemment).
L'énoncé stipule15 boules non identifiées.
Il faudra 5 opérations supplémentaires pour arriver à ces 5 sous-listes de 3 entiers triés.
20 itérations donc.
Je vais essayer de comprendre l’algorithme employé.

R.

syrac

Membre

Inscription : 27-05-2014

Messages : 201

Re : 15 boules à classer

Je vais essayer de comprendre l’algorithme employé.

Reprenons les sous-listes de mon précédent message : [[4,5,6], [1,2,3], [13,14,15], [7,8,9], [10,11,12]].

Imagine que tu aies 5 files d’attente, chacune devant un guichet.
Chaque file est déjà ordonnée : les personnes les plus petites (valeurs les plus faibles) sont en tête.

Exemple :
File A : [4, 5, 6]
File B : [1, 2, 3]
File C : [13, 14, 15]
etc.

Tu veux créer une seule file globale, du plus petit au plus grand, mais tu ne peux voir que la première personne de chaque file. Tu procèdes en posant 5 papiers sur une table, chacun indiquant la "taille" (la valeur) de la première personne de chaque file : 4, 1, 13, 7, 10. Parmi ces 5, la plus petite est 1 (file B[0]) $\rightarrow$ tu la déplaces vers ta file finale. Puis tu remplaces le contenu de ce papier par la valeur de la personne suivante dans la même file (file B[1] = 2). Ensuite tu répètes :

• Regarder les 5 premiers (bien sûr, seulement ceux encore actifs),

• Prendre le plus petit,

• L'ajouter à la file finale puis le remplacer par le suivant dans sa file (s’il en reste).

Le tas ( heapq ) fait ça automatiquement : il garde toujours le plus petit élément accessible sur le dessus, et se réorganise à chaque ajout/retrait.

Maintenant tu vas me demander ce qu'est un tas et comment il s'organise. Ou plus précisément, qu'est-ce qu'un tas min ( min-heap ) ?  Un tas min est une structure de données qui stocke des éléments de façon organisée, avec une seule règle stricte : l’élément le plus petit est toujours "en haut" (sur le dessus), ce qui permet de le récupérer instantanément. Mais contrairement à une liste triée, tout le reste n’est pas entièrement ordonné ; seule la position du minimum est garantie, ce qui veut dire que le tas min est suffisamment organisé pour que le minimum soit toujours au sommet.

Dire que "le tas se réorganise automatiquement" signifie qu'à chaque ajout ou retrait, il réajuste ses éléments en coulisses pour que le plus petit soit toujours le premier disponible, sans que toi tu aies à trier quoi que ce soit. C'est la raison pour laquelle on utilise la librairie heapq. Tout ce qu'elle fait n'est pas public, ce que tu vois de l'algorithme ne suffirait pas à effectuer le tri. Si tu veux savoir comment min-heap procède – ou si tu veux en créer une implémentation personnelle – tu dois chercher des explications sur ce qu'il fait exactement.

Dernière modification par syrac (27-11-2025 18:47:42)

Ernst

Membre

Inscription : 30-01-2024

Messages : 325

Re : 15 boules à classer

Je n'ai pas tout lu mais je suppose que le problème revient à utiliser l'algorithme de file d'attente de tas

Bonsoir,

Eh non, le problème des boules avec dispositif ternaire strict (tris de 3 éléments seulement) ne revient PAS à utiliser l'algorithme de file d'attente de tas. Celui-ci (heapq) permet d'extraire le minimum global parmi 5 candidats en une opération. Or le dispositif ternaire de l'énoncé impose des tris de 3 boules par appel, et donc plusieurs tris ternaires pour extraire ce minimum global. Pas du tout la même chose.