algorithmselect一个单一的，随机组合的值？

说我有不同的价值观，我想随机select其中的x 。 什么是有效的algorithm呢？ 我可以只调用rand() x次，但如果x ， y很大，性能会很差。

请注意，这里需要组合 ：每个值应该有相同的概率被选中，但是它们在结果中的顺序并不重要。 当然，任何生成排列的algorithm都是合格的，但是我想知道是否有可能在没有随机顺序要求的情况下更有效地做到这一点。

如何有效地生成0和上限N之间的K个非重复整数列表，覆盖这种情况下的排列。

Answer 1

罗伯特·弗洛伊德为这种情况发明了一种抽样algorithm。 它通常优于洗牌，然后抓取前x元素，因为它不需要O（y）存储。 正如它原来写的，它假定从1..N的值，但它是微不足道的产生0..N和/或使用非连续的值，只要将它产生的值作为下标处理成vector/数组/ /什么。

在pseuocode中，algorithm是这样运行的（从Jon Bentley的编程珍珠专栏“Brilliance样本”中窃取）。

 initialize set S to empty for J := NM + 1 to N do T := RandInt(1, J) if T is not in S then insert T in S else insert J in S 

最后一点（插入J如果T已经在S）是棘手的部分。 底线是它确保了插入J的正确math概率，从而产生无偏差的结果。

它是O（x） ¹和O（1）关于y ， O（x）的存储。

请注意，根据问题中的组合标签，algorithm只保证结果中每个元素出现的概率相等，而不是它们在其中的相对顺序。

---

_{在所涉及的散列图的最坏情况下，可以忽略} ¹ _{O（x ² ） ，因为这是一个几乎不存在的病理情况，其中所有的值都具有相同的散列}

Answer 2

假设你想要的顺序也是随机的（或者不介意它是随机的），我只会使用一个截断的Fisher-Yates混洗。 启动shufflealgorithm，但是一旦你select了第一个x值，而不是“随机select”所有y值，就停下来。

Fisher-Yates的工作如下：

• 随机select一个元素，并将其与数组末尾的元素交换。
• 对数组的其余部分进行recursion（或更可能的迭代），排除最后一个元素。

第一个之后的步骤不要修改数组的最后一个元素。 前两个步骤之后的步骤不影响最后两个元素。 第一个x之后的步骤不会影响最后的x个元素。 所以在这一点上，你可以停止 – 数组的顶部包含均匀随机select的数据。 数组的底部包含一些随机的元素，但是你得到的排列不是均匀分布的。

当然，这意味着你已经抛出了input数组 – 如果这意味着你需要在开始之前取得它的副本，并且x比y小，那么复制整个数组效率不高。 不过请注意，如果将来你将要使用它，那么这个select是随机的，然而事实上，它是随机的顺序并不重要，你可以再次使用它。 因此，如果您多次进行select，您可能在开始时只能执行一个副本，并摊销成本。

Answer 3

如果你真的只需要生成组合 ，元素的顺序无关紧要，你可以使用组合元素， 例如James McCaffrey在这里实现的 组合元素。

将其与k-排列进行对比，其中排列元素的顺序很重要。

在第一种情况下（1,2,3） ， （1,3,2） ， （2,1,3） ， （2,3,1） ， （3,1,2） ， （3,2,1 ）被认为是相同的 – 在后者中，它们被认为是不同的，尽pipe它们包含相同的元素。

如果你需要组合，你可能真的只需要生成一个随机数（虽然它可能有点大），可以直接用来find第m个组合。 由于这个随机数表示特定组合的索引，所以随机数应该在0和C（n，k）之间 。 计算组合元素也可能需要一些时间。

这可能是不值得的麻烦 – 除了杰里和费德里科的答案肯定比实施combinadics更简单。 但是，如果你真的只需要一个组合，而且你对于生成需要的随机位的确切数量并没有更多的东西，

虽然不清楚是否需要组合或k-排列，这里是后者的C＃代码（是的，如果x> y / 2，我们可以只产生一个补码，但是我们会留下必须的组合被洗牌得到一个真正的k-排列）：

 static class TakeHelper { public static IEnumerable<T> TakeRandom<T>( this IEnumerable<T> source, Random rng, int count) { T[] items = source.ToArray(); count = count < items.Length ? count : items.Length; for (int i = items.Length - 1 ; count-- > 0; i--) { int p = rng.Next(i + 1); yield return items[p]; items[p] = items[i]; } } } class Program { static void Main(string[] args) { Random rnd = new Random(Environment.TickCount); int[] numbers = new int[] { 1, 2, 3, 4, 5, 6, 7 }; foreach (int number in numbers.TakeRandom(rnd, 3)) { Console.WriteLine(number); } } } 

另一个更详细的生成k-置换的实现 ，我已经说了，我相信，如果你只需要迭代结果，就可以改进现有的algorithm。 虽然它也需要生成x个随机数，但在这个过程中只使用O（min（y / 2，x））存储器：

  /// <summary> /// Generates unique random numbers /// <remarks> /// Worst case memory usage is O(min((emax-imin)/2, num)) /// </remarks> /// </summary> /// <param name="random">Random source</param> /// <param name="imin">Inclusive lower bound</param> /// <param name="emax">Exclusive upper bound</param> /// <param name="num">Number of integers to generate</param> /// <returns>Sequence of unique random numbers</returns> public static IEnumerable<int> UniqueRandoms( Random random, int imin, int emax, int num) { int dictsize = num; long half = (emax - (long)imin + 1) / 2; if (half < dictsize) dictsize = (int)half; Dictionary<int, int> trans = new Dictionary<int, int>(dictsize); for (int i = 0; i < num; i++) { int current = imin + i; int r = random.Next(current, emax); int right; if (!trans.TryGetValue(r, out right)) { right = r; } int left; if (trans.TryGetValue(current, out left)) { trans.Remove(current); } else { left = current; } if (r > current) { trans[r] = left; } yield return right; } } 

总体思路是做一个Fisher-Yates洗牌 ， 记住排列中的换位 。 它没有发表在任何地方，也没有收到任何同行评议。 我相信这是一种好奇心，而不是具有一定的实用价值。 尽pipe如此，我还是非常乐于接受批评，并且一般想知道你是否发现任何问题 – 请考虑一下（并在投票之前添加一条评论）。

Answer 4

有一点build议：如果x >> y / 2，最好随机selecty – x个元素，然后select补集。

Answer 5

如果x或y很大，为什么performance会很差呢？ 你期待什么performance？ 即你如何提议在小于O（x）的时间内随机selectx项目？

在C ++中，您可以使用std::random_shuffle ，然后select第一个x项目。 std::random_shuffle使用了std::random_shuffle提到的Fisher-Yates shuffle。

Answer 6

例如，如果您有2 ^ 64个不同的值，则可以使用对称密钥algorithm（使用64位块）快速重新组合所有组合。 （如Blowfish）。

 for(i=0; i<x; i++) e[i] = encrypt(key, i) 

这不是纯粹意义上的随机性，而是可以用于您的目的。 如果你想用encryption技术处理任意数量的不同值，你可以但更复杂。

Answer 7

诀窍是使用混洗或换句话说部分混洗。

 function random_pick( a, n ) { N = len(a); n = min(n, N); picked = array_fill(0, n, 0); backup = array_fill(0, n, 0); // partially shuffle the array, and generate unbiased selection simultaneously // this is a variation on fisher-yates-knuth shuffle for (i=0; i<n; i++) // O(n) times { selected = rand( 0, --N ); // unbiased sampling N * N-1 * N-2 * .. * N-n+1 value = a[ selected ]; a[ selected ] = a[ N ]; a[ N ] = value; backup[ i ] = selected; picked[ i ] = value; } // restore partially shuffled input array from backup // optional step, if needed it can be ignored for (i=n-1; i>=0; i--) // O(n) times { selected = backup[ i ]; value = a[ N ]; a[ N ] = a[ selected ]; a[ selected ] = value; N++; } return picked; } 

注意algorithm在时间和空间上严格为O(n) ，产生无偏select （这是一个部分无偏置的混洗 ），对input数组无损 （作为部分混洗），但是这是可选的

改编自这里

更新

另一种方法是使用IVAN STOJMENOVIC的“ [0,1]的PRNG （伪随机数发生器） ，“关于组合对象的随机和自适应并行生成” （第3节），对O(N)案件）的复杂性

Answer 8

这是一个简单的方法来做到这一点，如果Y比X大得多，那么效率就会很低。

 void randomly_select_subset( int X, int Y, const int * inputs, int X, int * outputs ) { int i, r; for( i = 0; i < X; ++i ) outputs[i] = inputs[i]; for( i = X; i < Y; ++i ) { r = rand_inclusive( 0, i+1 ); if( r < i ) outputs[r] = inputs[i]; } } 

基本上，将不同值的第一个X复制到输出数组中，然后为每个剩余值随机决定是否包含该值。

随机数进一步用于select我们（可变）输出数组的元素进行replace。