Apa algoritma pemotongan kuku jari Yahudi yang optimal?

Saya sedang mengerjakan perangkat lunak untuk mesin yang secara otomatis akan memotong kuku kaki, sehingga pengguna dapat dengan mudah meletakkan kaki mereka di dalamnya dan menjalankannya daripada harus melakukannya secara manual dengan menggigitnya atau menggunakan gunting kuku.

Persentase yang cukup besar dari basis pengguna potensial kami kemungkinan besar adalah orang Yahudi, dan, jelas, ada tradisi untuk tidak memotong kuku kaki ( atau kuku ) secara berurutan

Tampaknya ada perbedaan pendapat tentang penerapan yang tepat dari tradisi ini, tetapi menurut kami aturan berikut cukup untuk mengakomodasi orang-orang yang praktik keagamaannya melarang pemotongan kuku secara berurutan:

• Tidak ada dua kuku kaki yang berdekatan harus dipotong secara berurutan
• Urutan pemotongan di kaki kiri harus tidak sesuai dengan urutan di kaki kanan
• Urutan pemotongan pada dua proses berturut-turut tidak boleh sama. Urutan seharusnya tidak mudah diprediksi, jadi pengkodean keras urutan alternatif tidak berfungsi.

Beginilah cara kami memutuskan untuk memberi nomor pada jari kaki:

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

Saya telah menulis kode untuk menyelesaikan masalah, tetapi algoritma yang digunakan kurang optimal: pada kenyataannya, kinerja kasus terburuk adalah O (∞) . Cara kerjanya sebanding dengan bogosort . Berikut ini adalah penyederhanaan pseudocode dari kode sebenarnya yang digunakan:

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)

Pada dasarnya, ini menghasilkan urutan acak dan memeriksa apakah memenuhi kriteria. Jika tidak memenuhi kriteria, itu akan dimulai kembali. Ini tidak membutuhkan waktu yang sangat lama, tetapi sangat tidak terduga.

Saya menyadari bahwa cara yang saya lakukan saat ini sangat buruk, tetapi saya kesulitan menemukan cara yang lebih baik. Adakah di antara Anda yang dapat menyarankan algoritme yang lebih elegan dan berperforma baik?

Anda dapat membuat semua urutan pemotongan kuku yang mungkin tanpa batasan, dan kemudian memfilter semua urutan yang melanggar aturan Yahudi. Untungnya, manusia hanya memiliki lima jari per kaki *, jadi hanya ada 5! = 120 urutan tidak terbatas.

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

Untuk menegakkan aturan "jangan berulang dalam urutan yang sama", Anda cukup memilih empat dari urutan di atas, dan menggunakannya secara bergantian. Satu-satunya batasan di sini adalah jika Anda menghitung dua jari kaki besar sebagai "berurutan", maka Anda tidak dapat memilih dua urutan yang berakhir dan dimulai dengan 1, masing-masing.

* Anda mungkin ingin membuat variabel numberOfToesPerFoot, sehingga Anda dapat dengan mudah mengubahnya nanti jika salah satu klien Anda ternyata memiliki jari kaki lebih sedikit dari yang Anda harapkan, atau lebih.

Ada sejumlah urutan terbatas yang memenuhi kebutuhan Anda.

1. Hasilkan semua permutasi dari {1,2,3,4,5}. Hanya ada 120.
2. Tolak yang tidak memenuhi persyaratan dan simpan set yang tersisa (secara permanen).
3. Pilih dua urutan berbeda secara acak. Ingat mana yang Anda gunakan terakhir kali.

EDIT: Jika ini bukan tentang jari-jari kaki, tetapi tentang beberapa masalah acak di mana himpunan bisa jauh lebih besar dari 5, ruang urutan menjadi sangat besar dan peluang untuk mengulangi urutan yang sama pada kaki kedua menjadi sangat kecil. Jadi membuat urutan secara acak dan menolaknya jika cocok adalah ide yang bagus. Menghasilkan urutan acak menurut beberapa aturan seperti "lompat dengan dua atau tiga, lalu isi yang kosong" mungkin akan lebih cepat daripada menghasilkan permutasi dan pengujian acak, dan kemungkinan tumpang tindih akan tetap kecil jika jumlah "jari kaki" besar .

Sebenarnya, saya paling menyukai algoritme asli Anda.

Karena 14 dari 120 permutasi berfungsi, 106 dari 120 tidak. Jadi, setiap cek memiliki peluang 106/120 untuk gagal.

Itu berarti jumlah kegagalan yang diharapkan adalah:

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

Tidak terlalu sulit untuk menjumlahkan seri infinite ini:

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

Kalikan dengan x:

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

Mengurangi:

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

Kalikan dengan x lagi dan kurangi lagi:

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

Karena x = 106/120, S = 64,9.

Jadi, rata-rata loop Anda hanya membutuhkan 65 iterasi untuk menemukan solusi.

Berapa probabilitas yang dibutuhkan, katakanlah, seribu iterasi?

Nah, kemungkinan gagal satu iterasi tunggal adalah 104/120, jadi kemungkinan gagal 1000 iterasi adalah (104/120) ^ 1000, yang kira-kira 10 ^ (- 63). Artinya, Anda tidak akan pernah melihatnya terjadi dalam hidup Anda, dan mungkin tidak dalam seumur hidup alam semesta.

Tidak ada tabel yang telah dihitung sebelumnya, mudah beradaptasi dengan jumlah jari / jari kaki / tangan / kaki yang berbeda, mudah beradaptasi dengan aturan yang berbeda ... Apa yang tidak disukai? Peluruhan eksponensial adalah hal yang luar biasa.

[memperbarui]

Ups, saya salah mendapatkan rumus aslinya ... Karena probabilitas saya tidak berjumlah 1. :-)

Ekspresi yang benar untuk jumlah kegagalan yang diharapkan adalah:

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

(Misalnya, untuk mendapatkan tepat dua kegagalan, Anda memerlukan dua kegagalan diikuti dengan kesuksesan . Dua kegagalan memiliki probabilitas (106/120) ^ 2; satu kesuksesan memiliki probabilitas (14/120); kalikan keduanya untuk mendapatkan bobot untuk Istilah "2".)

Jadi S saya mati dengan faktor (1-x) (yaitu, 14/120). Jumlah kegagalan yang diharapkan sebenarnya hanya x / (1-x) = 106/14 = 7,57. Jadi rata-rata hanya butuh 8-9 iterasi untuk menemukan solusi (7,5 kegagalan plus satu sukses).

Matematika saya untuk kasus "1000 kegagalan" masih benar, saya kira.

Yang jelas: Temukan satu pesanan yang berhasil, dan buat kode keras. Tapi saya rasa Anda tidak ingin melakukan itu.

Anda dapat menghasilkan permutasi jauh lebih baik daripada cara Anda melakukannya. Anda tidak perlu melakukan pengambilan sampel penolakan. Gunakan pengacakan Fisher Yates pada permutasi yang diurutkan awal (1, 2, .. 5), dan Anda akan memiliki permutasi acak. http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

Tetapi secara umum, metode hasilkan dan uji tampaknya baik-baik saja bagi saya, selama kemungkinan menghasilkan entri yang berhasil cukup tinggi. Saya yakin ada banyak urutan yang valid sesuai dengan kriteria Anda, begitu Anda beralih ke permutasi acak, saya ragu Anda harus melakukan banyak iterasi penolakan.

Tidak ada yang benar-benar baru di sini, solusi yang sama @Kevin sudah diposting, tapi saya pikir menarik untuk melihat bagaimana diterjemahkan ke bahasa fungsional. Dalam hal ini, Mathematica :

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

Beberapa penjelasannya:

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

Hasil akhirnya adalah:

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

Sunting

Atau, lebih sulit untuk dijelaskan, tetapi lebih singkat:

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

Sebenarnya tidak ada alasan untuk memasukkan keacakan ke dalam masalah ini. Hanya ada 14 urutan yang memenuhi masalah ini, dan tentunya beberapa urutan urutan tersebut akan paling memuaskan rasa estetika yang Anda coba tampung. Jadi, Anda sebaiknya mengurangi masalah ini menjadi algoritme untuk memilih urutan dari 14 itu, mungkin dalam urutan yang telah ditentukan sebelumnya.

Implementasi Javascript dari algoritma untuk menemukan 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)

EDIT: Persyaratan baru bahwa urutan harus dibuat secara acak tidak dapat dengan mudah dipenuhi. Hal terbaik yang mungkin dapat Anda lakukan adalah membuatnya menjadi pseudorandom, yang sama deterministiknya dengan hard-coding sebelumnya, dan karenanya tidak memuaskan takhayul siapa pun.