random - Fisher-Yates Shuffle：如果在 m 次后停止，则随机？

Question

我有整数 1,2,3,...,n 我必须从中随机选择 m < n 个不同的整数。我打算将这些整数放入一个数组中，然后使用 Fisher Yates Shuffle：

随机选择数组中的一个条目。将其与最后一个条目交换。然后，在数组中随机选择一个条目，最后一个条目除外。将其与倒数第二个条目交换。重复直到最后 m 个条目以这种方式获得。

问题

我的理解是，如果持续到 n 次，那么每次可能的安排都同样可能与这种洗牌。因此，如果在 m < n 次后停止，最后 m 个条目的每一个排列都是同样可能的。因此，最后 m 个条目是我需要的 m 个随机不同整数。

我的理解正确吗？

Answer 1

是的，也许更容易前进：

让rand(z)返回范围内[0..z)

for (int i = 0; i < m; i++)
    swap(X[i], X[i+rand(n-i)])

X[0..m-1]现在是随机样本