Qual é o algoritmo de corte de unha judaico ideal?

Estou trabalhando no software para uma máquina que cortará automaticamente as unhas dos pés, para que os usuários possam simplesmente colocar os pés nela e executá-la em vez de ter que fazer isso manualmente, mordendo-as ou usando um cortador de unhas.

Uma porcentagem considerável de nossa base de usuários em potencial provavelmente será judia e, evidentemente, há uma tradição de não aparar as unhas dos pés ( ou unhas ) em ordem sequencial

Parece haver opinião divergente sobre a aplicação precisa dessa tradição, mas pensamos que as seguintes regras são suficientes para acomodar pessoas cujas práticas religiosas proíbem cortar as unhas dos pés na ordem:

• Duas unhas adjacentes não devem ser cortadas consecutivamente
• A sequência de corte do pé esquerdo não deve corresponder à sequência do pé direito
• A sequência de corte em duas execuções consecutivas não deve ser a mesma. As sequências não devem ser facilmente previsíveis, portanto, codificar uma sequência alternada não funciona.

É assim que decidimos numerar os dedos dos pés:

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

Eu escrevi um código para resolver o problema, mas o algoritmo usado é abaixo do ideal: na verdade, o desempenho do pior caso é O (∞) . A forma como funciona é comparável ao bogosort . Aqui está uma simplificação de pseudocódigo do código real usado:

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)

Basicamente, ele gera sequências aleatórias e verifica se atendem aos critérios. Se não atender aos critérios, é reiniciado. Não leva um tempo ridiculamente longo, mas é muito imprevisível.

Percebo que a maneira como estou fazendo isso é terrível, mas estou tendo problemas para encontrar uma maneira melhor. Algum de vocês pode sugerir um algoritmo mais elegante e de desempenho?

Você pode gerar todas as sequências de corte de unha possíveis sem restrições e, em seguida, filtrar todas as sequências que violam a regra judaica. Felizmente, os humanos têm apenas cinco dedos por pé *, então existem apenas 5! = 120 sequências irrestritas.

Exemplo 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 impor sua regra de "não repetir a mesma sequência", você pode escolher apenas quatro das sequências acima e usá-las alternadamente. O único problema aqui é que se você contar os dois dedões do pé como "consecutivos", não poderá escolher duas sequências que terminem e comecem com 1, respectivamente.

* Você pode querer criar uma variável numberOfToesPerFoot, para que possa alterá-la facilmente mais tarde se algum de seus clientes tiver menos dedos do que o esperado ou mais.

Existe um número finito de sequências que satisfazem seus requisitos.

1. Gere todas as permutações de {1,2,3,4,5}. Existem apenas 120.
2. Rejeite aqueles que não satisfaçam os requisitos e armazene o conjunto restante (permanentemente).
3. Escolha aleatoriamente duas sequências diferentes. Lembre-se de quais você usou da última vez.

EDITAR: Se não se trata realmente de dedos, mas de algum problema aleatório em que o conjunto pode ser muito maior que 5, o espaço da sequência torna-se muito grande e a chance de repetir a mesma sequência no segundo pé torna-se muito pequena. Portanto, é uma boa ideia gerar sequências aleatoriamente e rejeitá-las se corresponderem. Gerar sequências aleatórias de acordo com alguma regra como "pular em dois ou três, e preencher os espaços em branco" provavelmente será mais rápido do que gerar permutações e testes aleatórios, e a chance de sobreposição ainda será pequena se o número de "dedos" for grande .

Na verdade, gosto mais do seu algoritmo original.

Visto que 14 de 120 permutações funcionam, 106 de 120 não funcionam. Portanto, cada verificação tem 106/120 de chance de falhar.

Isso significa que o número esperado de falhas é:

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

Não é muito difícil somar essa série infinita:

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

Multiplique por x:

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

Subtrair:

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

Multiplique por x novamente e subtraia novamente:

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

Uma vez que x = 106/120, S = 64,9.

Portanto, em média, seu loop precisa de apenas 65 iterações para encontrar uma solução.

Qual é a probabilidade de que isso leve, digamos, mil iterações?

Bem, a probabilidade de falhar em qualquer iteração única é 104/120, então a probabilidade de falhar em 1000 iterações é (104/120) ^ 1000, que é algo como 10 ^ (- 63). Ou seja, você nunca verá isso acontecer em sua vida, e provavelmente não durante a vida do universo.

Sem tabelas pré-computadas, fácil adaptação a diferentes números de dedos / pés / mãos / pés, fácil adaptação a diferentes conjuntos de regras ... O que há para não gostar? A decadência exponencial é uma coisa maravilhosa.

[atualizar]

Opa, eu entendi errado a fórmula original ... Já que minhas probabilidades não somam 1. :-)

A expressão correta para o número esperado de falhas é:

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

(Por exemplo, para obter exatamente duas falhas, você precisa de duas falhas seguidas de um sucesso . Duas falhas têm probabilidade (106/120) ^ 2; um sucesso tem probabilidade (14/120); multiplique-os juntos para obter o peso para o Termo "2".)

Portanto, meu S está errado por um fator de (1-x) (ou seja, 14/120). O número real de falhas esperado é apenas x / (1-x) = 106/14 = 7,57. Portanto, em média, leva apenas 8-9 iterações para encontrar uma solução (7,5 falhas mais um sucesso).

Minha matemática para o caso das "1000 falhas" ainda está correta, eu acho.

O óbvio: encontre um pedido que funcione e codifique-o. Mas eu não acho que você queira fazer isso.

Você pode gerar permutações muito melhor do que a maneira como está fazendo. Você não precisa fazer amostragem de rejeição. Use um embaralhamento de Fisher Yates em uma permutação inicialmente classificada (1, 2, .. 5) e você terá uma permutação aleatória. http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

Mas, em geral, o método de geração e teste parece totalmente bom para mim, desde que a probabilidade de gerar uma entrada bem-sucedida seja alta o suficiente. Tenho certeza de que existem muitas sequências válidas de acordo com seus critérios, uma vez que você alternar para uma permutação aleatória, duvido que você terá que fazer muitas iterações de rejeição.

Nada realmente novo aqui, a mesma solução que o @Kevin já postou, mas acho interessante ver como se traduz para uma linguagem funcional. Neste caso, o Mathematica :

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

Algumas explicações:

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

O resultado final é:

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

Ou, mais difícil de explicar, mas mais curto:

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

Não há realmente nenhuma razão para introduzir aleatoriedade neste problema. Existem apenas 14 sequências que satisfazem esse problema e, certamente, alguma ordem dessas sequências satisfaria melhor o senso estético que você está tentando acomodar. Portanto, você deve apenas reduzir esse problema a um algoritmo para selecionar uma sequência dessas 14, provavelmente em uma ordem predefinida.

Implementação Javascript do algoritmo para encontrar o 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: O novo requisito de que as sequências devem ser geradas aleatoriamente não pode ser atendido facilmente. O melhor que você provavelmente pode fazer é gerá-los pseudo-aleatoriamente, o que é tão determinístico quanto codificá-los com antecedência e, portanto, não deve satisfazer as superstições de ninguém.