在實踐中置換小型集

想像一下我們有一套 $ S $ 的 $ m $ 元素，我們想要置換集合元素。因此，每個元素的原始位置在置換後應該是未知的。如果我們定義一個置換函式為 $ \pi: {0,1}^n \rightarrow {0,1}^n $ , 那麼集合元素是安全置換的，如果 $ n\le|S| $ 在哪裡 $ n $ 是安全參數。所以要置換 $ S $ 我們的確是 $ \pi (i)=r_i $ ， 在哪裡 $ i $ 是集合中元素的原始索引，並且 $ r_i $ 是它的新索引。

但是，如果集合大小很小 ( $ |S|< n $ ) 似乎安全置換它的唯一方法是先填充它然後置換它，這會增加儲存成本。

問題：有沒有比上述方案更好、更具成本效益的置換集合的方法？

如果您可以生成統一的隨機數，則可以使用Fisher-Yates的變體。

//given an array s with the elements to be permuted
for i from n-1 to 1:
   t = rand(0, i) # inclusive
   swap(s[i], s[t])

引用自：https://crypto.stackexchange.com/questions/27178