Quel est l’algorithme optimal de coupe d’ongle juif?

Je travaille sur le logiciel d’une machine qui rognera automatiquement les ongles, afin que les utilisateurs puissent simplement y mettre les pieds et l’exécuter au lieu de le faire manuellement en les mordant ou en utilisant un coupe-ongles.

Un pourcentage non négligeable de notre base d’utilisateurs potentiels sera probablement juif et, de toute évidence, il existe une tradition selon laquelle les ongles ( ou les ongles ) ne sont pas découpés dans un ordre séquentiel.

Il semble y avoir une opinion dissidente sur l’application précise de cette tradition, mais nous pensons que les règles suivantes sont suffisantes pour accueillir les personnes dont les pratiques religieuses interdisent de couper les ongles d’orteil dans l’ordre:

  • Il ne faut pas couper deux ongles adjacents consécutivement
  • La séquence de coupe sur le pied gauche ne doit pas correspondre à la séquence du pied droit
  • La séquence de coupe sur deux exécutions consécutives ne devrait pas être la même. Les séquences ne devraient pas être facilement prévisibles, donc le codage en dur d’une séquence en alternance ne fonctionne pas.

Voici comment nous avons décidé de numéroter les orteils:

5 4 3 2 1 1 2 3 4 5 Left foot Right foot 

J’ai écrit du code pour résoudre le problème, mais l’algorithme utilisé est sous-optimal: en fait, la performance la plus défavorable est O (∞) . La façon dont cela fonctionne est comparable à celle de bogosort . Voici une simplification du pseudocode du code utilisé:

 function GenerateRandomSequence sequence = Array[5] foreach (item in sequence) item = RandomNumberBetween(1,5) return sequence function GetToenailCuttingOrder while (true) sequence = GenerateRandomSequence() if (!AllItemsAreUnique(sequence)) continue if (NoTwoAdjacentItemsHaveConsecutiveNumbers(sequence)) return sequence do leftFootSequence = GetToenailCuttingOrder() rightFootSequence = GetToenailCuttingOrder() until (leftFootSequence != rightFootSequence && leftFootSequence != leftFootSequenceFromLastRun && rightFootSequence != rightFootSequenceFromLastRun) 

Fondamentalement, il génère des séquences aléatoires et vérifie s’ils répondent aux critères. S’il ne répond pas aux critères, il recommence. Cela ne prend pas un temps ridiculement long, mais c’est très imprévisible.

Je me rends compte que la façon dont je le fais actuellement est assez terrible, mais j’ai de la difficulté à trouver une meilleure solution. L’un de vous peut-il suggérer un algorithme plus élégant et plus performant?

Vous pouvez générer toutes les séquences de coupe d’ongle d’orteil possibles sans ressortingction, puis filtrer toutes les séquences qui violent la règle juive. Heureusement, les humains n’ont que cinq orteils par pied *, alors il n’y en a que cinq! = 120 séquences sans ressortingction.

Exemple Python:

 #seq is only valid when consecutive elements in the list differ by at least two. def isValid(seq): for i in range(len(seq)-1): a = seq[i] b = seq[i+1] if abs(ab) == 1: return False return True from itertools import ifilter, permutations validseqs = ifilter(isValid, permutations([1,2,3,4,5])) for i in validseqs: print i (1, 3, 5, 2, 4) (1, 4, 2, 5, 3) (2, 4, 1, 3, 5) (2, 4, 1, 5, 3) (2, 5, 3, 1, 4) (3, 1, 4, 2, 5) (3, 1, 5, 2, 4) (3, 5, 1, 4, 2) (3, 5, 2, 4, 1) (4, 1, 3, 5, 2) (4, 2, 5, 1, 3) (4, 2, 5, 3, 1) (5, 2, 4, 1, 3) (5, 3, 1, 4, 2) 

Pour appliquer la règle “pas de répétitions de la même séquence”, vous pouvez simplement choisir quatre des séquences ci-dessus et les utiliser alternativement. Le seul problème ici est que si vous comptez les deux gros orteils comme “consécutifs”, vous ne pouvez pas choisir deux séquences qui se terminent et commencent par 1, respectivement.

* Vous souhaiterez peut-être créer une variable numberOfToesPerFoot, de sorte que vous pourrez facilement la modifier ultérieurement si l’un de vos clients s’avère avoir moins d’orteils que prévu ou plus.

Il existe un nombre fini de séquences répondant à vos besoins.

  1. Générez toutes les permutations de {1,2,3,4,5}. Il n’y en a que 120.
  2. Rejeter ceux qui ne répondent pas aux exigences et stocker le jeu restant (en permanence).
  3. Choisissez au hasard deux séquences différentes. Rappelez-vous celles que vous avez utilisées la dernière fois.

EDIT: Si cela ne concerne pas vraiment les orteils, mais certains problèmes aléatoires où le jeu peut être beaucoup plus grand que 5, l’espace de la séquence devient très grand et les chances de répéter la même séquence sur le deuxième pied deviennent très faibles. Générer de manière aléatoire des séquences et les rejeter s’ils correspondent est une bonne idée. Générer des séquences aléatoires selon une règle comme “saute par deux ou trois, puis remplis les blancs” sera probablement plus rapide que de générer des permutations et des tests aléatoires, et les risques de chevauchement seront encore faibles si le nombre de “pieds” est grand .

En fait, j’aime mieux votre algorithme original.

Étant donné que 14 permutations sur 120 fonctionnent, 106 sur 120 ne le sont pas. Donc, chaque vérification a une chance d’échec de 106/120.

Cela signifie que le nombre d’échecs attendu est le suivant:

 1*(106/120) + 2*(106/120)^2 + 3*(106/120)^3 + ... 

Pas trop difficile de résumer cette série infinie:

 S = 1*x + 2*x^2 + 3*x^3 + ... 

Multipliez par x:

 x*S = 1*x^2 + 2*x^3 + ... 

Soustraire:

 S - x*S = x + x^2 + x^3 + ... 

Multipliez par x à nouveau et soustrayez à nouveau:

 x*S - x^2*S = x^2 + x^3 + ... S - 2*x*S + x^2S = x S*(1-x)^2 = x S = x/(1-x)^2 

Depuis x = 106/120, S = 64,9.

Ainsi, en moyenne, votre boucle ne nécessite que 65 itérations pour trouver une solution.

Quelle est la probabilité qu’il prenne, disons, mille itérations?

Eh bien, la probabilité d’échouer à une seule itération est de 104/120, donc la probabilité d’échec de 1000 itérations est de (104/120) ^ 1000, ce qui est quelque chose comme 10 ^ (- 63). C’est-à-dire que vous ne verrez jamais cela se produire dans votre vie, et probablement pas dans la vie de l’univers.

Pas de tables précalculées, adaptation facile à différents nombres de doigts / orteils / mains / pieds, adaptation facile à différents jeux de règles … Qu’est-ce qui ne vous plait pas? La décroissance exponentielle est une chose merveilleuse.

[mettre à jour]

Oups, j’ai eu tort la formule originale … Puisque mes probabilités ne sont pas totalisant 1. 🙂

L’expression correcte du nombre d’échecs attendu est la suivante:

 0*(14/120) + 1*(106/120)*(14/120) + 2*(106/120)^2*(14/120) + ... 

(Par exemple, pour obtenir exactement deux échecs, vous avez besoin de deux échecs suivis d’un succès . Deux échecs ont une probabilité (106/120) ^ 2; un succès a une probabilité (14/120); multipliez-les pour obtenir le poids du “2” terme.)

Donc, mon S est désactivé d’un facteur de (1-x) (c.-à-d. 14/120). Le nombre réel de pannes attendues est juste x / (1-x) = 106/14 = 7,57. Donc, en moyenne, il ne faut que 8 à 9 itérations pour trouver une solution (7,5 échecs plus un succès).

Mon calcul pour le cas “1000 échecs” est toujours correct, je pense.

L’évidence: Trouvez une commande qui fonctionne et codez-la. Mais je ne pense pas que tu veuilles faire ça.

Vous pouvez générer des permutations beaucoup mieux que la manière dont vous le faites. Vous n’avez pas besoin de faire un échantillonnage de rejet. Utilisez un mélangeur Fisher Yates sur une permutation initialement sortingée (1, 2, .. 5) et vous aurez une permutation aléatoire. http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

Mais en général, la méthode de génération et de test me semble parfaitement appropriée, tant que la probabilité de générer une entrée réussie est suffisamment élevée. Je suis sûr qu’il y a beaucoup de séquences valides selon vos critères, une fois que vous passez à une permutation aléatoire, je doute que vous ayez à faire beaucoup d’itérations de rejet.

Rien de vraiment nouveau ici, la même solution @Kevin déjà publiée, mais je trouve intéressant de voir comment cela se traduit dans un langage fonctionnel. Dans ce cas, Mathematica :

 Extract[#,Position[Times @@ (Abs@#-1)&/@ Differences/@ #, Except@0, 1][[2 ;;]]] &@ Permutations@Range@5 

Quelques explications:

 Permutations@Range@5 Calculates all permutations of {1, 2, 3, 4, 5} Differences Calculate the differences between adjacent elements (we wish to discard all lists containing +1 or -1) Times @@ (Abs@#-1) Abs turns the -1s into +1s, and then to zeros by subtracting one, then TIMES multiplies all elements, giving zero when the original result of "Differences" contained a +1 or a -1 Position ... Except@0 Returns the position of the non zero results Extract Returns the original elements according to the calculated positions 

Le résultat final est:

 {{1, 3, 5, 2, 4}, {1, 4, 2, 5, 3}, {2, 4, 1, 3, 5}, {2, 4, 1, 5, 3}, {2, 5, 3, 1, 4}, {3, 1, 4, 2, 5}, {3, 1, 5, 2, 4}, {3, 5, 1, 4, 2}, {3, 5, 2, 4, 1}, {4, 1, 3, 5, 2}, {4, 2, 5, 1, 3}, {4, 2, 5, 3, 1}, {5, 2, 4, 1, 3}, {5, 3, 1, 4, 2}} 

modifier

Ou, plus difficile à expliquer, mais plus courte:

 Reap[ Table[ If[Times @@ (Abs@Differences@i - 1) != 0, Sow@i], {i, Permutations@Range@5}]][[2, 1]] 

Il n’y a vraiment aucune raison d’introduire le hasard dans ce problème. Il n’y a que 14 séquences qui satisfont à ce problème et certaines commandes de ces séquences satisferaient mieux le sens esthétique que vous essayez de prendre en compte. Ainsi, vous devez simplement réduire ce problème à un algorithme permettant de sélectionner une séquence parmi celles 14, probablement dans un ordre prédéfini.

Implémentation Javascript de l’algorithme pour trouver le 14:

 function swap (a, i, j) { var temp = a[i] a[i]=a[j] a[j]=temp } function permute (b, n, a) { if (n==4) { b.push(a.slice(0)) //copy array } else { for (var i = n; i < 5; i++) { swap(a,n,i) permute(b, n+1, a) swap(a,n,i) } } } var a = [1,2,3,4,5] var b = [] var c = [] permute(b,0,a) for (var i = 1; i < b.length-1; i++) { var good = true for (var j = 0; j < b[i].length; j++) { if (Math.abs(b[i][j-1]-b[i][j]) < 2 || Math.abs(b[i][j]-b[i][j+1]) < 2) { good = false } } if (good) c.push(b[i].join('')) } console.log(c) 

EDIT: La nouvelle exigence selon laquelle les séquences doivent être générées de manière aléatoire ne peut pas être facilement satisfaite. Le mieux que vous puissiez probablement faire est de les générer de manière pseudo-aléatoire, ce qui est tout aussi déterministe que de les coder en dur à l'avance, et ne devrait donc pas satisfaire les superstitions de quiconque.