algorithm - sistemas - la lru y la segunda oportunidad son políticas de

¿Cuál es el algoritmo óptimo de corte judío de uña?

Question

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

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

Parece haber una opinión disidente sobre la aplicación precisa de esta tradición, pero creemos que las siguientes reglas son suficientes para dar cabida a las personas cuyas prácticas religiosas prohíben cortar 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 carreras 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 contar los dedos de los pies:

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

He escrito un código para resolver el problema, pero el algoritmo utilizado no es óptimo: de hecho, el peor de los casos 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 forma mejor. ¿Alguno de ustedes puede sugerir un algoritmo más elegante y de rendimiento?

Answer 1

En realidad, me gusta mejor tu algoritmo original.

Como 14 de las 120 permutaciones funcionan, 106 de 120 no lo hacen. Entonces, cada cheque tiene una probabilidad 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 sumar esta serie infinita:

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

Multiplicar por x:

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

Sustraer:

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

Multiplicar por x nuevamente y restar 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

Como x = 106/120, S = 64.9.

Por lo tanto, en promedio, su bucle solo necesita 65 iteraciones para encontrar una solución.

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

Bueno, la probabilidad de fallar en una sola iteración es 104/120, por lo que la probabilidad de fallar 1000 iteraciones es (104/120) ^ 1000, que es algo así como 10 ^ (- 63). Es decir, nunca verás que ocurra en tu vida, y probablemente no en 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 le gusta? La descomposición exponencial es algo maravilloso.

[actualizar]

Vaya, obtuve la fórmula original incorrecta ... 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 fallas, necesita dos fallas seguidas de un éxito . Dos fallas tienen una probabilidad (106/120) ^ 2; un éxito tiene una probabilidad (14/120); multiplíquelas para obtener el peso del "2" término)

Entonces mi S está desactivada 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. Por lo tanto, en promedio, se necesitan solo 8-9 iteraciones para encontrar una solución (7.5 fallas más un éxito).

Mi matemática para el caso de "1000 fallas" sigue siendo correcta, creo.

Answer 2

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

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

EDITAR: Si esto no es realmente sobre los dedos del pie, sino sobre algún problema aleatorio donde el conjunto puede ser mucho mayor que 5, el espacio de 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 al azar y rechazarlas si coinciden es una buena idea. Generar secuencias aleatorias de acuerdo con una regla como "saltar de dos en dos o 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 la cantidad de "dedos de los pies" es grande .

Answer 3

Lo obvio: encuentre un orden 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 necesita hacer un muestreo de rechazo. Use una combinación aleatoria de Fisher Yates en una permutación ordenada inicialmente (1, 2, ... 5), y obtendrá 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.

Answer 4

Nada realmente nuevo aquí, la misma solución @Kevin ya ha publicado, pero creo interesante ver cómo se traduce a 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 corto:

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

Answer 5

Podrías generar todas las secuencias posibles de corte de uña 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 tu regla "no se repite la misma secuencia", puedes elegir cuatro de las secuencias anteriores y usarlas alternativamente. La única pega aquí es que si cuentas los dos dedos gordos como "consecutivos", entonces no puedes elegir dos secuencias que terminan y comienzan con 1, respectivamente.

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

Answer 6

Realmente no hay ninguna razón para introducir la aleatoriedad en este problema. Solo hay 14 secuencias que satisfacen este problema, y ​​seguramente algún orden de esas secuencias satisfará mejor el sentido estético que intentas acomodar. Por lo tanto, debería simplemente reducir este problema a un algoritmo para seleccionar 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 se generen al azar no se puede cumplir fácilmente. Lo mejor que puedes hacer es generarlos de forma pseudoaleatoria, lo cual es tan determinista como codificarlos por adelantado, y por lo tanto no deberían satisfacer las supersticiones de nadie.