İsterim oluşturmak benzersiz rasgele sayılar arasında 0 ve 1000 o asla tekrar (yani 6 gelmedi iki kere), ama bu değil tatil gibi bir şey O(N) arama önceki değerler. Bu mümkün mü?

Başlatma 1001 bir dizi değerler 0-1000 ile tamsayılar ve dizi geçerli max Endeksi (1000 ile başlayan bir değişken, max, ayarlayın. Rastgele bir numara, r, 0 ve max arasında tercih, r konumunda numarası konumunda numarasını takas max ve artık geri dönüş konumunda max. 1 ile max azaltma ve devam edin. Max dizinin boyutu 0, max set - 1 ve tekrar yeniden başlatmamız gerek kalmadan başlar.

Güncelleme: Ancak ben ile geldi bu yöntem benim kendi zaman cevap verdim soruyu, sonra biraz araştırma farkındayım bu değiştirilmiş bir sürümü Fisher-Yates bilindiği gibi Durstenfeld-Fisher-Yates ya da Knuth-Fisher-Yates. Açıklama takip etmek biraz zor olabilir bu yana, bir örnek aşağıda (1001 yerine 11 öğe kullanarak) sağladım:

Dizi başladığında 11 öğe dizisi başlatıldı kapalı[n] = n max 10'da başlıyor:

 -- -- -- -- -- -- -- -- -- -- -- 
| 0| 1| 2| 3| 4| 5| 6| 7| 8| 9|10|
 -- -- -- -- -- -- -- -- -- -- -- 
                                ^
                               max    

Her yineleme, rastgele bir sayı r seçilir arasında 0 ve max, dizi[r] ve dizi[max] takas, yeni dizi[max] döndürülür ve max indirildiği:

max = 10, r = 3
            -------------------- 
           v                    v
 -- -- -- -- -- -- -- -- -- -- -- 
| 0| 1| 2|10| 4| 5| 6| 7| 8| 9| 3|
 -- -- -- -- -- -- -- -- -- -- -- 

max = 9, r = 7
                        ----- 
                       v     v
 -- -- -- -- -- -- -- -- -- -- -- 
| 0| 1| 2|10| 4| 5| 6| 9| 8| 7: 3|
 -- -- -- -- -- -- -- -- -- -- -- 

max = 8, r = 1
      -------------------- 
     v                    v
 -- -- -- -- -- -- -- -- -- -- -- 
| 0| 8| 2|10| 4| 5| 6| 9| 1: 7| 3|
 -- -- -- -- -- -- -- -- -- -- -- 

max = 7, r = 5
                  ----- 
                 v     v
 -- -- -- -- -- -- -- -- -- -- -- 
| 0| 8| 2|10| 4| 9| 6| 5: 1| 7| 3|
 -- -- -- -- -- -- -- -- -- -- -- 

...

11 yineleme, dizideki tüm sayıları seçildikten sonra, = = 0, ve dizi elemanları karıştırılan: max

 -- -- -- -- -- -- -- -- -- -- -- 
| 4|10| 8| 6| 2| 0| 9| 5| 1| 7| 3|
 -- -- -- -- -- -- -- -- -- -- -- 

Bu noktada, max 10 sıfırlanabilir ve süreci devam edebilir.