38

假设我有y不同的值，我想x随机选择它们。这样做的有效算法是什么？我可以只打电话给时间，但如果,很大rand() x，性能会很差。xy

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

您如何有效地生成介于 0 和上限 N 之间的 K 个非重复整数的列表，涵盖了这种置换情况。

4

7 回答 7

64

罗伯特·弗洛伊德（Robert Floyd）为这种情况发明了一种采样算法。它通常优于洗牌然后抓取第一个x元素，因为它不需要 O(y) 存储。正如最初所写的那样，它假设值来自 1..N，但是通过简单地将其产生的值作为下标处理到向量/数组/其他内容中来产生 0..N 和/或使用非连续值是微不足道的。

在伪代码中，算法是这样运行的（摘自 Jon Bentley 的Programming Pearls专栏“A sample of Brilliance”）。

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

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

就, O(x)存储而言，它是O(x) 1和O(1) 。y

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

1 O(x 2 )在所涉及的哈希映射的最坏情况下可以忽略，因为它实际上是不存在的病态情况，其中所有值都具有相同的哈希

于 2010-03-06T22:15:31.597 回答
12

假设您希望订单也是随机的（或者不介意它是随机的），我只会使用截断的 Fisher-Yates 洗牌。启动随机播放算法，但在您选择了第一个x值后停止，而不是“随机选择”所有y这些值。

Fisher-Yates 的工作方式如下：

  • 随机选择一个元素，并将其与数组末尾的元素交换。
  • 递归（或更可能迭代）数组的其余部分，不包括最后一个元素。

第一个之后的步骤不会修改数组的最后一个元素。前两个之后的步骤不会影响最后两个元素。第一个 x 之后的步骤不会影响最后一个 x 元素。因此，此时您可以停止 - 数组的顶部包含均匀随机选择的数据。数组的底部包含一些随机化的元素，但你得到的排列并不是均匀分布的。

当然，这意味着您已经丢弃了输入数组 - 如果这意味着您需要在开始之前对其进行复制，并且 x 与 y 相比较小，那么复制整个数组并不是很有效。请注意，如果您将来要使用它的只是进一步选择，那么它的顺序有点随机这一事实并不重要，您可以再次使用它。因此，如果您多次进行选择，您可能一开始只能做一份副本，并摊销成本。

于 2010-03-07T01:29:24.290 回答
2

如果你真的只需要生成组合——元素的顺序无关紧要——你可以使用组合，因为它们是由 James McCaffrey 实现的。

将此与k-permutations进行对比，其中元素的顺序确实很重要。

在第一种情况下(1,2,3) , (1,3,2) , (2,1,3) , (2,3,1) , (3,1,2) , (3,2,1 )被认为是相同的 - 在后者中，它们被认为是不同的，尽管它们包含相同的元素。

如果您需要组合，您可能真的只需要生成一个随机数（尽管它可能有点大） - 可以直接用于查找第m个组合。由于此随机数表示特定组合的索引，因此您的随机数应介于 0 和C(n,k)之间。计算组合也可能需要一些时间。

这可能只是不值得麻烦 - 除了杰里和费德里科的答案肯定比实施组合更简单。但是，如果您真的只需要一个组合，并且您对生成所需的确切随机位数量感到厌烦，仅此而已...... ;-)

虽然不清楚您是想要组合还是 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-permutations，我一直在闲逛，我相信如果你只需要迭代结果，它在某种程度上是对现有算法的改进。虽然它还需要生成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 洗牌并记住 permutation 中的转置。它没有在任何地方发表，也没有得到任何同行评议。我相信这是一种好奇心，而不是有一些实用价值。尽管如此，我对批评持开放态度，并且通常想知道您是否发现它有任何问题 - 请考虑这一点（并在否决之前添加评论）。

于 2010-03-06T22:21:01.763 回答
1

一点建议：如果 x >> y/2，最好随机选择 y - x 个元素，然后选择互补集。

于 2010-03-06T22:40:14.493 回答
0

例如，如果您有 2^64 个不同的值，则可以使用对称密钥算法（使用 64 位块）来快速重新洗牌所有组合。（例如河豚）。

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

这在纯粹意义上不是随机的，但对您的目的很有用。如果您想使用加密技术之后的任意 # 个不同的值，您可以，但它更复杂。

于 2010-03-07T01:45:29.653 回答
0

诀窍是使用洗牌的变体，或者换句话说，部分洗牌。

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;
}

注意该算法O(n)在时间和空间上都是严格的，产生无偏选择（它是部分无偏洗牌）并且在输入数组上是非破坏性的（就像部分洗牌一样），但这是可选的

从这里改编

更新

IVAN STOJMENOVIC 在“组合对象的随机和自适应并行生成”（第3节）中仅使用一次调用PRNG（伪随机数生成器）的另一种方法，具有（最坏情况）复杂性[0,1]O(N)

在此处输入图像描述

于 2015-08-20T11:28:55.260 回答
0

这是一种简单的方法，只有在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不同的值复制到输出数组，然后对于每个剩余的值，随机决定是否包含该值。

随机数进一步用于选择我们的（可变）输出数组中的一个元素来替换。

于 2016-08-12T02:33:13.493 回答