¿Cuál es el algoritmo óptimo para cortar las uñas de los pies judíos?

Estoy trabajando en el software para una máquina que recorta automáticamente las uñas de los pies, de modo que los usuarios puedan simplemente poner sus pies en él y ejecutarlo en lugar de tener que hacerlo manualmente mordiéndolos o usando un cortaúñas.

Es probable que un porcentaje considerable de nuestra base de usuarios potenciales sea judío y, evidentemente, existe una tradición de no recortar las uñas de los pies ( o las uñas de las manos ) en orden secuencial.

Parece haber opiniones discrepantes sobre la aplicación precisa de esta tradición, pero creemos que las siguientes reglas son suficientes para adaptarse a las personas cuyas prácticas religiosas prohíben cortarse las uñas de los pies en orden:

• No se deben cortar dos uñas de los pies adyacentes consecutivamente
• La secuencia de corte en el pie izquierdo no debe coincidir con la secuencia en el pie derecho
• La secuencia de corte en dos corridas consecutivas no debe ser la misma. Las secuencias no deben ser fácilmente predecibles, por lo que codificar una secuencia alterna no funciona.

Así es como hemos decidido numerar los dedos de los pies:

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

He escrito código para resolver el problema, pero el algoritmo utilizado es subóptimo: de hecho, el peor rendimiento de caso es O (∞) . La forma en que funciona es comparable a bogosort . Aquí hay una simplificación de pseudocódigo del código real utilizado:

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)

Básicamente, genera secuencias aleatorias y comprueba si cumplen los criterios. Si no cumple con los criterios, comienza de nuevo. No toma una cantidad de tiempo ridículamente larga, pero es muy impredecible.

Me doy cuenta de que la forma en que lo estoy haciendo actualmente es bastante terrible, pero tengo problemas para encontrar una mejor manera. ¿Alguno de ustedes puede sugerir un algoritmo más elegante y eficaz?

Podría generar todas las secuencias posibles de corte de uñas de los pies sin restricciones y luego filtrar todas las secuencias que violen la regla judía. Afortunadamente, los humanos solo tienen cinco dedos por pie *, ¡así que solo hay 5! = 120 secuencias sin restricciones.

Ejemplo de 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)

Para hacer cumplir su regla de "no repetir la misma secuencia", puede elegir cuatro de las secuencias anteriores y utilizarlas alternativamente. El único inconveniente aquí es que si cuenta los dos dedos gordos del pie como "consecutivos", entonces no puede elegir dos secuencias que terminen y comiencen con 1, respectivamente.

* Es posible que desee crear una variable numberOfToesPerFoot, para poder cambiarla fácilmente más tarde si alguno de sus clientes tiene menos dedos de los que espera, o más.

Existe un número finito de secuencias que satisfacen sus requisitos.

1. Genere todas las permutaciones de {1,2,3,4,5}. Solo hay 120.
2. Rechace los que no cumplan los requisitos y almacene el juego restante (permanentemente).
3. Elija al azar dos secuencias diferentes. Recuerda cuáles usaste la última vez.

EDITAR: Si esto no se trata realmente de los dedos de los pies, sino de algún problema aleatorio en el que el conjunto puede ser mucho mayor que 5, el espacio de la secuencia se vuelve muy grande y la posibilidad de repetir la misma secuencia en el segundo pie se vuelve muy pequeña. Así que generar secuencias aleatoriamente y rechazarlas si coinciden es una buena idea. Generar secuencias aleatorias de acuerdo con alguna regla como "saltar de dos en dos o de tres en tres, luego completar los espacios en blanco" probablemente será más rápido que generar permutaciones y pruebas aleatorias, y la posibilidad de superposición seguirá siendo pequeña si el número de "dedos" es grande .

De hecho, me gusta más tu algoritmo original.

Dado que 14 de 120 permutaciones funcionan, 106 de 120 no lo hacen. Entonces, cada cheque tiene una probabilidad de 106/120 de fallar.

Eso significa que el número esperado de fallas es:

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

No es demasiado difícil resumir esta serie infinita:

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

Multiplica por x:

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

Sustraer:

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

Multiplique por x nuevamente y reste nuevamente:

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

Dado que x = 106/120, S = 64,9.

Entonces, en promedio, su ciclo necesita solo 65 iteraciones para encontrar una solución.

¿Cuál es la probabilidad de que se necesiten, digamos, mil iteraciones?

Bueno, la probabilidad de fallar en una sola iteración es 104/120, por lo que la probabilidad de fallar en 1000 iteraciones es (104/120) ^ 1000, que es algo así como 10 ^ (- 63). Es decir, nunca verá que suceda durante su vida, y probablemente no durante la vida del universo.

Sin tablas precalculadas, fácil adaptación a diferentes números de dedos de manos / pies / manos / pies, fácil adaptación a diferentes conjuntos de reglas ... ¿Qué no me gusta? La descomposición exponencial es algo maravilloso.

[actualizar]

Vaya, me equivoqué con la fórmula original ... Ya que mis probabilidades no suman 1. :-)

La expresión correcta para el número esperado de fallas es:

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

(Por ejemplo, para obtener exactamente dos fallos, necesita dos fallos seguidos de un éxito . Dos fallas tienen probabilidad (106/120) ^ 2; un éxito tiene probabilidad (14/120); multiplíquelas para obtener el peso de la Término "2".)

Entonces mi S está apagado por un factor de (1-x) (es decir, 14/120). El número real esperado de fallas es solo x / (1-x) = 106/14 = 7.57. Entonces, en promedio, solo toma 8-9 iteraciones a para encontrar una solución (7.5 fallas más un éxito).

Creo que mis cálculos para el caso de "1000 fallos" siguen siendo correctos.

Lo obvio: encuentre un pedido que funcione y codifíquelo. Pero no creo que quieras hacer eso.

Puede generar permutaciones mucho mejor que la forma en que lo está haciendo. No es necesario realizar un muestreo de rechazo. Utilice una reproducción aleatoria de Fisher Yates en una permutación ordenada inicialmente (1, 2, .. 5), y tendrá una permutación aleatoria. http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

Pero en general, el método de generar y probar me parece totalmente correcto, siempre que la probabilidad de generar una entrada exitosa sea lo suficientemente alta. Estoy seguro de que hay muchas secuencias válidas de acuerdo con sus criterios, una vez que cambie a una permutación aleatoria, dudo que tenga que hacer muchas iteraciones de rechazo.

Nada realmente nuevo aquí, la misma solución que @Kevin ya publicó, pero creo que es interesante ver cómo se traduce en un lenguaje funcional. En este caso, Mathematica :

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

Algunas explicaciones:

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

El resultado final es:

{{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}}

Editar

O, más difícil de explicar, pero más breve:

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

Realmente no hay razón para introducir aleatoriedad en este problema. Solo hay 14 secuencias que satisfacen este problema, y ​​seguramente algún orden de esas secuencias satisfaría mejor el sentido estético que está tratando de adaptarse. Por lo tanto, debería reducir este problema a un algoritmo para elegir una secuencia de esos 14, probablemente en un orden preestablecido.

Implementación de Javascript del algoritmo para encontrar el 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)

EDITAR: El nuevo requisito de que las secuencias deben generarse aleatoriamente no se puede cumplir fácilmente. Lo mejor que puede hacer probablemente es generarlos pseudoaleatoriamente, lo cual es tan determinista como codificarlos antes de tiempo, por lo que no debería satisfacer las supersticiones de nadie.