Каков оптимальный еврейский алгоритм резки ногтей

Question

Я работаю над программным обеспечением для машины, которая будет автоматически подстригать ногти на ногах, чтобы пользователи могли просто поставить в нее ноги и запустить ее вместо того, чтобы делать это вручную, кусая их или используя кусачки для ногтей.

Значительный процент нашей потенциальной пользовательской базы, скорее всего, будет евреем, и, очевидно, существует традиция не обрезать ногти на ногах ( или ногти ) в последовательном порядке

Кажется, существует особое мнение относительно точного применения этой традиции, но мы считаем, что следующие правила достаточны, чтобы приспособить людей, религиозная практика которых запрещает обрезать ногти на ногах в порядке:

• Нет двух смежных ногтейследует обрезать последовательно
• Последовательность обрезки на левой ноге не должна совпадать с последовательностью на правой ноге
• Последовательность обрезки на двух последовательных прогонах не должна быть одинаковой.Последовательности не должны быть легко предсказуемыми, поэтому жесткое кодирование альтернативной последовательности не работает.

Вот как мы решили подсчитать пальцы:

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

Я написалкод для решения проблемы, но используемый алгоритм является неоптимальным: на самом деле, производительность в худшем случае составляет O (∞) .То, как это работает, сравнимо с bogosort .Вот упрощение псевдокода фактического используемого кода:

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)

По сути, он генерирует случайные последовательности и проверяет, соответствуют ли они критериям.Если он не соответствует критериям, он начинается заново.Это не займет смехотворно много времени, но это очень непредсказуемо.

Я понимаю, что то, как я сейчас это делаю, довольно ужасно, но у меня возникают проблемы с поиском лучшего способа,Кто-нибудь из вас может предложить более элегантный и производительный алгоритм?

Answer 1

Вы можете сгенерировать все возможные последовательности резания ногтей без ограничений, а затем отфильтровать все последовательности, которые нарушают еврейское правило. К счастью, у людей только пять пальцев на ногу *, поэтому их всего 5! = 120 неограниченных последовательностей.

Пример 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)

Чтобы применить правило «нет повторов одной и той же последовательности», вы можете просто выбрать четыре из указанных выше последовательностей и использовать их поочередно. Единственный улов здесь заключается в том, что если вы считаете два больших пальца «последовательными», то вы не можете выбрать две последовательности, которые заканчиваются и начинаются с 1 соответственно.

* Возможно, вы захотите создать переменную numberOfToesPerFoot, чтобы вы могли легко изменить ее позже, если у любого из ваших клиентов окажется меньше пальцев, чем вы ожидаете, или больше.

Answer 2

Существует конечное число последовательностей, которые удовлетворяют вашим требованиям.

1. Создание всех перестановок {1,2,3,4,5}.Их всего 120.
2. Отклонить те, которые не удовлетворяют требованиям, и сохранить оставшийся набор (навсегда).
3. Произвольно выбрать две разные последовательности.Вспомните, какие из них вы использовали в прошлый раз.

РЕДАКТИРОВАТЬ: Если это не совсем пальцы, а о какой-то случайной проблеме, где набор может быть намного больше 5, пространство последовательности становится очень большим ивероятность повторить ту же последовательность на второй ноге становится очень маленькой.Так что случайная генерация последовательностей и отклонение их, если они совпадают, хорошая идея.Генерирование случайных последовательностей в соответствии с некоторым правилом, таким как «скачай по двое или по трое, затем заполняй пробелы», вероятно, будет быстрее, чем генерация случайных перестановок и тестирования, и вероятность совпадения все равно будет небольшой, если число «пальцев» большое.

Answer 3

На самом деле мне больше всего нравится ваш оригинальный алгоритм.

Поскольку 14 из 120 перестановок работают, 106 из 120 - нет.Таким образом, у каждой проверки есть шанс неудачи 106/120.

Это означает, что ожидаемое количество неудач:

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

Не слишком сложно суммировать этот бесконечный ряд:

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

Умножить на x:

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

Вычесть:

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

Снова умножить на x и снова вычесть:

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

Так как x =106/120, S = 64,9.

Итак, в среднем вашему циклу требуется всего 65 итераций , чтобы найти решение.

Какова вероятность того, что он принимает, скажем, тысяча итераций?

Что ж, вероятность сбоя одной итерации равна 104/120, поэтому вероятность сбоя 1000 итераций равна (104/120) ^ 1000, что примерно равно 10 ^ (- 63).То есть вы никогда не увидите, чтобы это произошло в вашей жизни, и, вероятно, не в жизни вселенной.

Нет предварительно вычисленных таблиц, простая адаптация к разному количеству пальцев рук / ног / рук / ног, легкая адаптация кразные наборы правил ... Что не нравится?Экспоненциальный спад - замечательная вещь.

[обновление]

Упс, я действительно ошибся в оригинальной формуле ... Так как мои вероятности не суммируются в 1.: -)

Правильное выражение для ожидаемого количества отказов:

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

(Например, чтобы получить ровно два сбоя, вам нужно два сбоя , за которыми следует успех . Два сбоя имеютвероятность (106/120) ^ 2; один успех имеет вероятность (14/120); умножьте их вместе, чтобы получить вес для термина "2".)

Таким образом, мой S выключен с коэффициентом (1-х) (т. Е. 14/120).Фактическое ожидаемое количество отказов просто х / (1-х) = 106/14 = 7,57.Так что в среднем требуется всего 8-9 итераций , чтобы найти решение (7,5 сбоев плюс один успех).

Моя математика для случая "1000 сбоев" все еще верна, я думаю.

Answer 4

Очевидное: найдите один ордер, который работает, и жестко запишите его. Но я не думаю, что ты хочешь это сделать.

Вы можете генерировать перестановки гораздо лучше, чем то, как вы это делаете. Вам не нужно делать выборку отклонения. Используйте перетасовку Фишера-Йетса в первоначально отсортированной перестановке (1, 2, .. 5), и вы получите случайную перестановку. http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

Но в целом метод генерации и тестирования кажется мне вполне подходящим, если вероятность генерации успешной записи достаточно высока. Я уверен, что есть много правильных последовательностей в соответствии с вашими критериями, как только вы переключитесь на случайную перестановку, я сомневаюсь, что вам придется делать много итераций отклонения.

Answer 5

Ничего действительно нового здесь, то же решение @Kevin уже выложено, но я думаю, интересно посмотреть, как оно переводится на функциональный язык. В этом случае Mathematica :

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

Некоторые объяснения:

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

Окончательный результат:

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

Редактировать

Или, более сложно объяснить, но короче:

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

Answer 6

Нет никакой причины вводить случайность в эту проблему.Есть только 14 последовательностей, которые удовлетворяют этой проблеме, и, конечно, некоторое упорядочение этих последовательностей лучше всего удовлетворяет эстетическому смыслу, который вы пытаетесь приспособить.Таким образом, вы должны просто свести эту проблему к алгоритму выбора последовательности из этих 14, возможно, в заранее установленном порядке.

Реализация алгоритма нахождения Javascript для 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)

РЕДАКТИРОВАТЬ: Новое требование о том, что последовательности должны быть созданы случайным образом, не может быть легко выполнено.Лучшее, что вы, вероятно, можете сделать, это генерировать их псевдослучайно, что является столь же детерминированным, как и жесткое их кодирование заранее, и поэтому не должно удовлетворять чьим-либо суевериям.