Jaki jest optymalny algorytm obcinania paznokci żydowskich?

Pracuję nad oprogramowaniem do maszyny, która będzie automatycznie przycinać paznokcie, tak aby użytkownicy mogli po prostu włożyć w nią stopy i uruchomić ją, zamiast robić to ręcznie, gryząc je lub używając obcinaczy do paznokci.

Znaczny procent naszej potencjalnej bazy użytkowników będzie prawdopodobnie pochodzenia żydowskiego i najwyraźniej istnieje tradycja nie przycinania paznokci u nóg ( lub paznokci ) w kolejności sekwencyjnej

Wydaje się, że istnieją odrębne opinie na temat dokładnego stosowania tej tradycji, ale uważamy, że poniższe zasady są wystarczające, aby dostosować się do osób, których praktyki religijne zabraniają przycinania paznokci w celu:

• Żadne dwa sąsiadujące paznokcie nie powinny być przycinane jeden po drugim
• Sekwencja cięcia na lewej stopie nie powinna odpowiadać sekwencji na prawej stopie
• Sekwencja cięcia w dwóch kolejnych seriach nie powinna być taka sama. Sekwencje nie powinny być łatwe do przewidzenia, więc zakodowanie na stałe sekwencji naprzemiennej nie działa.

Oto jak zdecydowaliśmy się ponumerować palce:

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

Napisałem kod, aby rozwiązać problem, ale zastosowany algorytm jest nieoptymalny: w rzeczywistości najgorsza wydajność to O (∞) . Sposób działania jest porównywalny z bogosortem . Oto uproszczenie pseudokodu używanego kodu:

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)

Zasadniczo generuje losowe sekwencje i sprawdza, czy spełniają kryteria. Jeśli nie spełnia kryteriów, zaczyna się od nowa. Nie zajmuje to absurdalnie długiego czasu, ale jest bardzo nieprzewidywalne.

Zdaję sobie sprawę, że sposób, w jaki obecnie to robię, jest dość okropny, ale mam problem z wymyśleniem lepszego sposobu. Czy ktoś z was może zaproponować bardziej elegancki i skuteczniejszy algorytm?

Możesz wygenerować wszystkie możliwe sekwencje cięcia paznokci u stóp bez żadnych ograniczeń, a następnie odfiltrować wszystkie sekwencje, które naruszają żydowskie reguły. Na szczęście ludzie mają tylko pięć palców na stopę *, więc jest ich tylko 5! = 120 nieograniczonych sekwencji.

Przykład Pythona:

#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)

Aby wymusić regułę „bez powtórzeń tej samej sekwencji”, możesz po prostu wybrać cztery z powyższych sekwencji i używać ich naprzemiennie. Jedyny haczyk polega na tym, że jeśli policzysz dwa duże palce jako „następujące po sobie”, nie możesz wybrać dwóch sekwencji kończących się i rozpoczynających się odpowiednio 1.

* Możesz chcieć utworzyć zmienną numberOfToesPerFoot, aby móc ją łatwo zmienić później, jeśli którykolwiek z Twoich klientów okaże się mieć mniej lub więcej palców u nóg, niż się spodziewasz.

Istnieje skończona liczba sekwencji, które spełniają Twoje wymagania.

1. Wygeneruj wszystkie permutacje {1,2,3,4,5}. Jest ich tylko 120.
2. Odrzuć te, które nie spełniają wymagań i zachowaj pozostały zestaw (na stałe).
3. Wybierz losowo dwie różne sekwencje. Zapamiętaj, których użyłeś ostatnio.

EDYCJA: Jeśli tak naprawdę nie chodzi o palce, ale o jakiś przypadkowy problem, w którym zbiór może być znacznie większy niż 5, przestrzeń sekwencji staje się bardzo duża, a szansa powtórzenia tej samej sekwencji na drugiej stopie staje się bardzo mała. Tak więc losowe generowanie sekwencji i odrzucanie ich, jeśli pasują do siebie, to dobry pomysł. Generowanie losowych sekwencji według jakiejś reguły, takiej jak „przeskakuj po dwóch lub trójek, a następnie wypełnij puste miejsca” będzie prawdopodobnie szybsze niż generowanie losowych permutacji i testowanie, a szansa na nakładanie się będzie nadal niewielka, jeśli liczba „palców u nóg” jest duża .

Właściwie najbardziej podoba mi się twój oryginalny algorytm.

Ponieważ 14 ze 120 permutacji działa, 106 na 120 nie działa. Więc każdy test ma 106/120 szans na niepowodzenie.

Oznacza to, że oczekiwana liczba awarii to:

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

Nietrudno podsumować tę nieskończoną serię:

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

Pomnóż przez x:

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

Odejmować:

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

Ponownie pomnóż przez x i odejmij ponownie:

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

Ponieważ x = 106/120, S = 64,9.

Tak więc średnio Twoja pętla potrzebuje tylko 65 iteracji, aby znaleźć rozwiązanie.

Jakie jest prawdopodobieństwo, że potrzeba, powiedzmy, tysiąca iteracji?

Cóż, prawdopodobieństwo niepowodzenia dowolnej pojedynczej iteracji wynosi 104/120, więc prawdopodobieństwo niepowodzenia 1000 iteracji wynosi (104/120) ^ 1000, czyli około 10 ^ (- 63). Oznacza to, że nigdy nie zobaczysz, jak to się wydarzyło w swoim życiu i prawdopodobnie nie za życia wszechświata.

Brak wstępnie obliczonych tabel, łatwe dostosowanie do różnej liczby palców rąk / stóp / dłoni / stóp, łatwe dostosowanie do różnych zestawów reguł ... Czego nie lubić? Rozpad wykładniczy to cudowna rzecz.

[aktualizacja]

Ups, źle zrozumiałem oryginalną formułę ... Ponieważ moje prawdopodobieństwa nie sumują się do 1. :-)

Prawidłowe wyrażenie dla oczekiwanej liczby błędów to:

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

(Na przykład, aby uzyskać dokładnie dwie porażki, potrzebujesz dwóch niepowodzeń, po których następuje sukces . Dwie porażki mają prawdopodobieństwo (106/120) ^ 2; jeden sukces ma prawdopodobieństwo (14/120); pomnóż je razem, aby uzyskać wagę dla Termin „2”).

Więc moje S jest wyłączone o współczynnik (1-x) (tj. 14/120). Rzeczywista oczekiwana liczba awarii to po prostu x / (1-x) = 106/14 = 7,57. Tak więc średnio potrzeba tylko 8-9 iteracji, aby znaleźć rozwiązanie (7,5 niepowodzenia plus jeden sukces).

Myślę, że moja matematyka dla przypadku „1000 niepowodzeń” jest nadal poprawna.

To oczywiste: znajdź jedno działające zamówienie i zakoduj je na stałe. Ale myślę, że nie chcesz tego robić.

Możesz generować permutacje znacznie lepiej niż sposób, w jaki to robisz. Nie musisz próbować odrzucać. Użyj tasowania Fisher Yates na początkowo posortowanej permutacji (1, 2, .. 5), a otrzymasz losową permutację. http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

Ogólnie rzecz biorąc, metoda generowania i testowania wydaje mi się całkowicie w porządku, o ile prawdopodobieństwo wygenerowania udanego wpisu jest wystarczająco wysokie. Jestem pewien, że istnieje wiele prawidłowych sekwencji zgodnych z twoimi kryteriami, po przełączeniu się na losową permutację wątpię, że będziesz musiał wykonać wiele iteracji odrzucenia.

Nie ma tu nic nowego, to samo rozwiązanie @Kevin zostało już opublikowane, ale myślę, że interesujące jest zobaczenie, jak przekłada się na język funkcjonalny. W tym przypadku Mathematica :

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

Kilka wyjaśnień:

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

Ostateczny wynik to:

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

Edytować

Lub trudniej wyjaśnić, ale krócej:

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

Naprawdę nie ma powodu, aby wprowadzać przypadkowość do tego problemu. Jest tylko 14 sekwencji, które rozwiązują ten problem i na pewno pewne uporządkowanie tych sekwencji najlepiej zaspokoi zmysł estetyczny, który próbujesz dostosować. Dlatego powinieneś po prostu zredukować ten problem do algorytmu wybierania sekwencji z tych 14, prawdopodobnie w ustalonej kolejności.

Implementacja algorytmu JavaScript do znajdowania 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)

EDYCJA: Nowy wymóg, że sekwencje muszą być generowane losowo, nie może być łatwo spełniony. Najlepsze, co prawdopodobnie możesz zrobić, to wygenerować je pseudolosowo, co jest tak samo deterministyczne, jak zakodowanie ich z wyprzedzeniem, a więc nie powinno zaspokajać niczyich przesądów.