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

Question

Je suis en train de travailler sur le logiciel pour une machine qui va automatiquement ajuster les ongles de pied, de sorte que les utilisateurs peuvent tout simplement mettre les pieds dans et exécuter, au lieu d'avoir à le faire manuellement en les mordant ou à l'aide d'un coupe-ongle.

Un pourcentage important de notre potentiel de base de l'utilisateur sera susceptible d'être Juif, et, évidemment, il y a une tradition de ne pas le parage des ongles (ou les ongles) dans un ordre séquentiel

Il semble que l'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 d'interdire la coupe des ongles de pied dans l'ordre:

• Pas de deux adjacentes ongles doivent être coupés de façon consécutive
• La séquence de coupe sur le pied gauche ne doit pas correspondre à la séquence sur le pied droit
• La séquence de coupe sur les deux séries consécutives ne doit pas être le même. Les séquences ne devrait pas être facilement prévisible, donc coder en dur une séquence alternée ne fonctionne pas.

C'est ainsi que 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-optimale: en effet, dans le pire des cas, la performance est O(∞). Le fonctionnement est comparable à bogosort. Voici un pseudo-code de la simplification 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. Si elle ne remplit pas les critères, il recommence. Il ne faut pas un trop long laps de temps, mais il est très imprévisible.

Je me rends compte que la façon dont je suis en train de faire c'est assez terrible, mais je vais avoir du mal à trouver une meilleure façon. Qui de vous proposer un plus élégant et performant algorithme?

Answer 1

Vous pourriez générer tous les possibles de l'ongle du découpage des séquences, sans restriction, puis filtrer toutes les séquences qui violent la règle juive. Heureusement, les humains ont seulement cinq orteils à chaque pied*, donc il y a seulement 5! = 120 sans restriction de séquences.

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(a-b) == 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 faire valoir vos "pas de répétitions de la même séquence de" la règle, vous pouvez simplement choisir quatre des séquences susmentionnées, et de les utiliser alternativement. Le seul hic, c'est que si vous comptez les deux gros orteils "consécutifs", alors vous ne pouvez pas choisir deux séquences se terminer et commencer avec 1, respectivement.

*Vous pouvez faire un numberOfToesPerFoot variable, de sorte que vous pouvez facilement changer plus tard si l'un de vos clients a moins orteils que vous attendez, ou plus.

Answer 2

Il y a un nombre fini de séquences qui répondent à vos exigences.

1. Générer toutes les permutations de {1,2,3,4,5}. Il y a seulement 120.
2. Rejeter ceux qui ne satisfont pas aux exigences et stocker l'ensemble restant (de façon permanente).
3. Choisir au hasard deux séquences différentes. Rappelez-vous ceux qui vous avez utilisé la dernière fois.

EDIT: Si ce n'est pas vraiment sur les orteils, mais à propos de certains aléatoire problème où le jeu peut être beaucoup plus grand que 5, la séquence de l'espace devient très grand et la possibilité de répéter la même séquence sur le deuxième pied devient très faible. Donc, au hasard la génération de séquences et de la rejeter si elles correspondent est une bonne idée. Génération de séquences aléatoires selon certaines règles de type "hop par groupes de deux ou trois, puis de remplir les blancs" sera probablement plus rapide que la génération aléatoire de combinaisons et d'essais, et de la possibilité de chevauchement sera toujours faible si le nombre de "pieds" est grande.

Answer 3

En fait, j'aime votre algorithme original de mieux.

Depuis le 14 de 120 permutations de travail, 106 de 120 ne le font pas. De sorte que chaque case a un 106/120 chance d'échouer.

Cela signifie que le nombre de défaillances est:

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

Pas trop dur pour la somme de cette série infinie:

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

Multiplier par x:

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

Soustraire:

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

Multiplier par x et soustraire de 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

Puisque x = 106/120, S = 64.9.

Donc, en moyenne, votre boucle besoins seulement 65 itérations pour trouver une solution.

Quelle est la probabilité qu'il prend, disons, un millier d'itérations?

Ainsi, la probabilité de défaut d'une seule itération est 104/120, de sorte que la probabilité de défaut de 1000 itérations (104/120)^1000, ce qui est quelque chose comme 10^(-63). C'est, vous n'aurez plus jamais le voir arriver dans votre vie, et probablement pas dans la durée de vie de l'univers.

Pas de tables précalculées, facile à adapter à différents nombres de doigts/orteils/mains/pieds, facile à adapter à différents jeux de règles... n'est-Ce pas? Décroissance exponentielle est une chose merveilleuse.

[mise à jour]

Oups, je l'ai fait entrer la formule originale de mal... Depuis mon probabilités n'est pas nécessairement égal à 1. :-)

L'expression correcte pour le nombre de défaillances est:

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 suivie par un succès. Deux échecs ont une probabilité (106/120)^2; une réussite a une probabilité (14/120); multiplier ces ensemble pour obtenir le poids pour la "2".)

Donc, mon S est éteint par un facteur (1-x) (c'est à dire, 14/120). Le réel est prévu que le nombre de défaillances est juste x/(1-x) = 106/14 = 7.57. Donc, il faut en moyenne seulement 8-9 itérations pour trouver une solution (7.5 échecs de plus un succès).

Mes calculs pour le "1000 échecs" est toujours correct, je pense.

Answer 4

L'évidence: Trouver une commande qui fonctionne, et de coder en dur. Mais je ne pense pas que vous voulez faire.

Vous pouvez générer des permutations beaucoup mieux que la façon dont vous le faites. Vous n'avez pas besoin de faire un rejet de l'échantillonnage. Utiliser un Fisher Yates shuffle sur un triée au départ de permutation (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, de générer et de tester la méthode semble tout à fait bien pour moi, tant que la probabilité de générer un succès d'entrée est assez élevé. Je suis sûr qu'il y a autant de valable séquences en fonction de vos critères, une fois que vous passez à une permutation aléatoire, je doute que vous aurez à faire beaucoup de rejet d'itérations.

Answer 5

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]]