[algorithm] 최적의 유대인 발톱 절단 알고리즘은 무엇입니까?

저는 발톱을 자동으로 다듬는 기계를위한 소프트웨어를 개발 중입니다. 사용자는 발톱을 물거나 손톱깎이를 사용하여 수동으로 할 필요없이 간단히 발을 넣고 실행할 수 있습니다.

잠재적 인 사용자 기반의 상당 부분이 유대인 일 가능성이 높으며, 발톱 ( 또는 손톱 )을 순차적으로 다듬지 않는 전통 이 있습니다.

이 전통의 정확한 적용에 대해 반대 의견이있는 것 같지만, 우리는 종교적 관습이 발톱을 순서대로 자르는 것을 금지하는 사람들을 수용하기에 다음 규칙으로 충분하다고 생각합니다.

• 인접한 발톱 두 개를 연속적으로 절단해서는 안됩니다.
• 왼쪽 발의 절단 순서가 오른쪽 발의 순서와 일치하지 않아야합니다.
• 두 번 연속 실행되는 절단 순서는 동일하지 않아야합니다. 시퀀스는 쉽게 예측할 수 없어야하므로 교대 시퀀스를 하드 코딩하는 것은 작동하지 않습니다.

이것이 우리가 발가락 번호를 결정한 방법입니다.

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)

기본적으로 무작위 시퀀스를 생성하고 기준을 충족하는지 확인합니다. 기준을 충족하지 않으면 다시 시작됩니다. 엄청나게 긴 시간이 걸리지는 않지만 예측할 수 없습니다.

나는 현재 내가하고있는 방식이 꽤 끔찍하다는 것을 알고 있지만 더 나은 방법을 찾는 데 어려움을 겪고 있습니다. 더 우아하고 성능이 좋은 알고리즘을 제안 할 수 있습니까?

답변

#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*(106/120) + 2*(106/120)^2 + 3*(106/120)^3 + ...

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

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

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

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

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

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

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)