从两个单独的集合中配对有限数量的随机元素的有效方法

本文关键字：随机 方法 有效 元素 两个 集合 单独 | 更新日期: 2023-09-27 18:19:50

我有两个列表(lista和listb(，每个列表都包含未知数量的点(结构中的两个整数(。

我想创建一个包含来自lista和listb的唯一随机配对的新列表。因此，示例条目可能是 [12,14]，其中 12 是 lista 的索引，14 是 listb 的索引。

我还想在调用此函数时设置最大配对数。因此，与其将lista中的每个元素与listb中的每个元素配对，不如将其限制为200个随机配对作为示例。

我的第一个尝试是简单地生成每个可能的配对。打乱该列表并敲掉超过我最大值的任何元素。此解决方案的效率还不够高。

我的下一个尝试是为每个可能的索引的每个原始列表创建一个数组，分别洗牌，然后迭代它们，直到我拥有最大数量的配对(或全部(。这有几个问题，我不确定如何解决。其中之一，lista可能拥有我所知道的1000万个元素。创建一个包含 1000 万个元素的新数组(索引列表(并在我的最大对数可能只有 200 时对其进行洗牌？走那么远似乎很愚蠢。

我考虑过从 lista/listb 中选择随机元素，看看我是否已经将它们配对，然后再将它们添加到新列表中。这也是一个非常愚蠢的选择，因为可以花很多时间一遍又一遍地选择重复的配对。

那么，这里有什么好的选择，或者有一个？我不想遍历每个可能的组合，配对必须是唯一的，从列表中删除选项非常慢，因为当它们非常大时会重新调整数组大小，分布需要在每个列表的选择过程中非常均匀，等等。

感谢您的任何和所有帮助。

编辑 - 我的意思是关于配对本身的独特方面。因此，lista 中的元素 10 可以一遍又一遍地使用，只要 listb 中的元素每次都不同。唯一的问题是我不想立即限制 lista 和 listb，因为我需要为每个配对在两个列表中公平均匀地分布。

从两个单独的集合中配对有限数量的随机元素的有效方法

为了完全避免重复，你可以尝试做一个稀疏的费舍尔-耶茨洗牌。

  • 创建一个Dictionary<int, int> dict，将"Fisher-Yates 数组中不保存自己索引的索引"映射到"该索引处的值"。
  • 对于第 n 项，选择一个从 n(含(到"列表 A 的大小 * 列表 B 的大小"(不包括(的随机数x
    • dict[x] ?? x是您选择的项目。
    • 将dict[n] ?? n存放在dict[x]。
    • 将所选项目映射回一对索引(对于列表 B 索引，除以 ListA 的大小，对于 ListA 索引，用模数除以 ListA 的大小(。

数学或统计爱好者可能会给你一个评估这个的公式，但我只是写了一些测试代码。

代码只是选择随机对，每次看到重复时，它都会再次尝试。然后，对于每个这样的"选择一个随机对直到唯一"循环，它会计算它进行了多少次重试并跟踪它。最后，将其汇总到一个全局数组中，以跟踪这些事物的相对频率。

以下是执行约 1 分钟后的结果：

84382319 81 0 0 0 0 0 0 0 0

这些数字意味着：

  • 超出421912周期 [(84382319+81(/200]：
    • 找到 81 个重复项，但重试未找到重复项(第 3 个数字及以上为 0(
    • 第一次尝试时可以找到84382319唯一的对，没有重复

所以，显然，如果你增加你想要生成的对的数量或降低选择错误的数量，这将开始上升，但我不确定这在实践中会造成问题。

这是我使用的 LINQPad 程序：

static Random R = new Random();
void Main()
{
    var a = 10000;
    var b = 10000;
    var n = 200;
    int[] counts = new int[10];
    var dc = new DumpContainer().Dump();
    while (true)
    {
        var once = Test(a, b, n);
        for (int i = 0; i < once.Length; i++)
            counts[i] += once[i];
        dc.Content = Util.HorizontalRun(true, counts);
    }
}
public static int[] Test(int a, int b, int n)
{
    var seen = new HashSet<Tuple<int, int>>();
    var result = new int[10];
    for (int index = 0; index < n; index++)
    {
        int tries = 0;
        while (true)
        {
            var av = R.Next(a);
            var bv = R.Next(a);
            var t = Tuple.Create(av, bv);
            if (seen.Contains(t))
                tries++;
            else
            {
                seen.Add(t);
                break;
            }
        }
        result[tries]++;
    }
    return result;
}
相关文章：