Amis des tris ternaires, bonjour,
Deux améliorations majeures :
1) au lieu de vérifier la validité d’une séquence en essayant au hasard sur 15! = 1 307 674 368 000 rails, on peut en fait la vérifier de façon irréfutable avec seulement 32 768 rails, ce qui est extrêmement rapide. Effectivement, il existe un théorème qui stipule que si un réseau de comparaisons avec N entrées trie correctement toutes les 2^N séquences possibles de 0 et de 1, alors il trie correctement toutes les séquences de nombres quels qu’ils soient !
Theorem 28.2
2) en plus de javascript, j’ai décidé de paralléliser massivement les calculs (j’ai une RTX 4060). En vitesse, donc en capacité d’exploration, je gagne facilement un facteur 10. Résultat ? Les S(24) tombent comme des mouches.
[[1,6,13],[2,8,15],[3,9,14],[4,7,12],[5,10,11],[11,13,15],[1,4,5],[6,8,10],[7,9,11],[2,4,7],[10,12,14],[3,5,6],[6,8,10],[11,12,13],[1,2,3],[13,14,15],[7,8,9],[9,10,11],[5,6,7],[3,4,5],[11,12,13],[7,8,9],[5,6,7],[9,10,11]]
[[1,6,14],[2,7,13],[3,8,15],[4,9,12],[5,10,11],[6,8,10],[1,3,5],[11,12,15],[2,4,6],[5,7,9],[9,12,14],[10,11,13],[6,8,10],[3,4,5],[13,14,15],[7,8,9],[5,6,7],[9,10,11],[1,2,3],[11,12,13],[7,8,9],[3,4,5],[9,10,11],[5,6,7]]
[[1,6,15],[2,9,14],[3,10,13],[4,7,12],[5,8,11],[1,3,5],[6,8,10],[11,13,15],[7,9,11],[2,4,6],[10,12,14],[5,7,9],[6,8,10],[3,4,5],[11,12,13],[9,10,11],[13,14,15],[1,2,3],[5,6,7],[7,8,9],[3,4,5],[11,12,13],[9,10,11],[5,6,7]]
etc.
Soit dit en passant, j'ai toujours pensé que S(25) était l’optimum, il y a donc eu tout à la fois un plaisir et une déception à tomber sur ces records. Comme quoi...