Fisher-Yates shuffle ünlü algoritma rasgele uzunlukta bir dizi N kapsamalıdır için kullanılabilir:

For k = 1 to N
    Pick a random integer j from k to N
    Swap A[k] and A[j]

Tekrar ve tekrar yapmak için değil söylendi bu yaygın bir hatadır bu

For k = 1 to N
    Pick a random integer j from 1 to N
    Swap A[k] and A[j]

O, N, k, rasgele bir tamsayı toplama yerine, N. 1 arasında rastgele bir tamsayı almak

Eğer bu hatayı yaparsanız ne olur? Sonuç permütasyon eşit dağıtılmış değil biliyorum, ama ortaya çıkan bir dağıtım olacak ne var bilmiyorum. Özellikle, herkes elemanlarının son pozisyon olasılık dağılımları için bir ifade var mı?

Ampirik Bir Yaklaşım.

İşte İncelenmiştir: hatalı algoritması uygulamak

p = 10; (* Range *)
s = {}
For[l = 1, l <= 30000, l  , (*Iterations*)
   a = Range[p];
   For[k = 1, k <= p, k  , 
     i = RandomInteger[{1, p}];
     temp = a[[k]];
     a[[k]] = a[[i]];
     a[[i]] = temp
   ];
   AppendTo[s, a];
]  

Hemen her tamsayı her pozisyonda sayısı:

r = SortBy[#, #[[1]] &] & /@ Tally /@ Transpose[s]  

Bu sonuç dizilerde üç pozisyon alalım ve bu duruma: her tamsayı için frekans dağılımı arsa

Pozisyon 1 için frekans dağılımı

Pozisyon için 5 (orta)

Ve pozisyon için 10 (son):

ve burada tüm pozisyonları birlikte çizilen dağıtımı var:

Burada 8 pozisyonları üzerinde daha iyi bir istatistik var:

Bazı gözlemler:

• Tüm pozisyonlar için olasılığını "1" Aynı (1/n).
• Olasılık matrisi simetrik anti-çapraz büyük saygı ile
• Yani, son olarak herhangi bir sayı için olasılık pozisyon da üniforma (1/n)

Bu özellikleri aynı noktaya (ilk özellik) tüm çizgilerin başlangıç bakarak ve geçen yatay çizgi (üçüncü özellik) görselleştirmek olabilir.

İkinci özellik satır pozisyonları olduğu aşağıdaki matris temsili örnek, görülebilir, sütunlar yolcu sayısını ve rengini deneysel olasılık temsil eder:

Bir 100x100 matris:

Edit

Sadece eğlence için, ikinci diyagonal elemanı (ilk 1/n) için tam formülü hesapladım. Gerisi yapılabilir, ama bir sürü iş var.

h[n_] := (n-1)/n^2   (n-1)^(n-2) n^(-n)

6 değerler n=3 doğrulandı( {8/27, 57/256, 564/3125, 7105/46656} )

Edit

@Biraz genel açık hesaplama cevap wnoise çalışma, biraz daha bilgi alabiliriz.

Yerine 1/n ile p[n], bu yüzden hesaplamalar tutun unevaluated, örneğin ilk bölümü matrisi ile n=7 (görmek için tıklayın daha büyük bir resim):

Hangi n değerleri için diğer sonuçlar ile karşılaştırdıktan sonra, bize bilinen bazı tamsayı dizileri tanımlamak matrix'te

{{  1/n,    1/n      , ...},
 {... .., A007318, ....},
 {... .., ... ..., ..},
 ... ....,
 {A129687, ... ... ... ... ... ... ..},
 {A131084, A028326 ... ... ... ... ..},
 {A028326, A131084 , A129687 ... ....}}

Harika o dizileri (farklı işaretler ile bazı durumlarda) bulabilirsiniz http://oeis.org/

Genel problem çözme daha zordur, ama bu bir başlangıç olur umarım