算法跟蹤大量混洗甲板

Question

可以說應用程序需要高效地存儲大量混洗甲板。是否存在一個恆定的空間，恆時，算法使得：

index = draw_from_shuffled(element_count, number_of_draws_made, random_seed) 

返回的值是下一個卡從有序集合繪製指數。此外，索引不會重複，即：同一張卡片不會被重複繪製兩次。需要存儲大量不同洗牌的套牌將被替換爲隨機數字，該隨機數字提供一種用於訂購該套牌的初始化向量。存儲一個n數量的混洗甲板，將需要存儲整數值的數量n。

那麼像這樣的算法存在？沒有固定時間的一種方法是使用bloom filter來跟蹤已經繪製的卡片。數據要求是恆定的，但最壞的算法複雜度是n!，這是不可取的。

Answer 1

保留52個整數的數組，其中每個項目是所有套牌中對應卡的總數（索引1代表1個心臟，並且該項目最初1000代表1000個套牌）。在繪製函數：

1. 選擇一個隨機值，R，0和1之間

2. 集噸至0

3. 對於每個項目在陣列：

   3-一個。令T = T +項目/總項目

   3-b。如果T> = R遞減項目，則遞減totalItems，返回項目索引012-c。3-c。轉到3

該算法具有恆定的空間和恆定的運行時間複雜度，假設代理的數量適合整數。也許更確切地說，空間複雜性是O(logD)。