Shuffle: Neden bir döngü arr [i] arr [r] (r: rasgele 0 - uzunluk - 1) ile eşit rastgele bir karışıklık değil mi?

Question

Şu anda Sedgewick'in Coursera (Java'da öğretilen) algoritmaları dersini alıyorum. Tekdüze rastgele bir karıştırma algoritması oluşturduğunu söylüyor, dizideki her bir indeksi i geçmem gerekiyor, bu öğeyi rastgele bir öğe ile değiştiriyorum. Öğeyi tüm diziden rastgele bir öğe ile değiştirecek olursam, tekdüze rastgele olmaz. Neden olmasın? Eğer her yineleme elemanı için [I], kendi içinde dahil olmak üzere, dizideki bir başka eleman ile tamamen rasgele olarak değiştirilirse, 1/N'den her zaman elemanın [I] nerede biteceğinin olasılığıdır; Yanlılığın nasıl ortaya çıktığını göremiyorum.

Başka bir deyişle o savunmaktadır:

for (var i = 0; i < arr.length; i++){ 
    var r = Math.floor(Math.random() * i + 1) 
    swap(r, i); 
} 

JavaScript Mazeret

for (var i = 0; i < arr.length; i++){ 
    var r = Math.floor(Math.random() * arr.length) 
    swap(r, i); 
} 

üzerinde Yepyeni bir programcı değilim ve onunla daha rahat olduğum gibi :)

Answer 1

Çok basit. matematik. Eğer her bir elemanı tüm setten başka biriyle değiştirirseniz, 0'dan N-1'e, N'den rasgele bir sayı elde edersiniz ve N * N olası sonuçları vardır. N olduğu için! (yani faktöriyel N) maddelerin olası düzenlemeleri ve N ** N, N! tarafından bölünemez, bazı düzenlemeler diğerlerinden daha sık gerçekleşir.

İlk geçişte, uygun bir karıştırma, 0 ile N-1 arasında bir rastgele sayı seçer, ardından 0 ile N-2 arasındaki bir sonraki geçişi, son olarak 0'dan 1'e kadar. Böylece, tam olarak N olacak. ! muhtemel sonuçlar, olası permütasyonların her biri (swapları doğru yaptığınızı varsayarak).