gpt4 book ai didi

c# - 如何有效地生成组合而不重复它们之间的特定数字

转载 作者:可可西里 更新时间:2023-11-01 08:49:16 30 4
gpt4 key购买 nike


如何有效地生成不重复的数字组合集合,其中所有集合彼此之间都有特定的独特数字。
*注意:范围编号始终从 0 开始。


例子:

范围编号 (numbers[ ]) = 0,1,2,3,4,5,6,7 ==> 总共 8 个数字 (n)
组合 (k) = 5 个数字。
不同的数字(nD) = 2 个数字。


结果:
0 1 2 3 4
0 1 2 5 6
0 1 3 5 7
0 1 4 6 7
0 2 3 6 7
0 2 4 5 7
0 3 4 5 6
有7种有效组合


它是如何组装的:

因为我不善言辞,所以让我把它们想象成这样: enter image description here

解释一下他们独特的数字: enter image description here

我们可以将它们汇总到下表中: enter image description here


到目前为止我取得了什么

我目前的解决方案效率很低(或者你可以称之为蛮力)。
* 首先我为每个组合循环。 ==> k C n
* 然后我为有效组合创建一个临时文件。
* 然后,对于每个组合,我都会针对我的温度进行验证,如果有效则将其存储在温度中,否则忽略它。
就是这样。

这是我在控制台应用程序中的代码:

class Program
{
static List<int[]> ValidCombinations;

static void Main()
{
ValidCombinations = new List<int[]>();

int[] numbers = Enumerable.Range(0, 8).ToArray();
int n = numbers.Length;
const int k = 5;
const int nD = 2;

int maxIntersect = k - nD;

int iCombination = 0;
int iValidCombination = 0;
int[] _temp = new int[k];
foreach (int[] c in FindCombinations(k, n))
{
// #Print out
for (int i = 0; i < n; i++)
{
if (c.Contains(i))
Console.Write(c[Array.IndexOf(c, i)] + " ");
else
Console.Write("_ ");
}

// Save to List
if (IsValidSet(c, maxIntersect))
{
_temp = new int[k];
for (int i = 0; i < c.Length; i++)
{
_temp[i] = c[i];
}
ValidCombinations.Add(_temp);
iValidCombination++;
Console.Write(" ### --> {0}", string.Join(" ", c));
}
Console.WriteLine();

iCombination++;
}
Console.WriteLine("\nTotal Combination = {0}", iCombination);
Console.WriteLine("Valid Combination Found = {0}", iValidCombination);
}

public static IEnumerable<int[]> FindCombosRec(int[] buffer, int done, int begin, int end)
{
for (int i = begin; i < end; i++)
{
buffer[done] = i;

if (done == buffer.Length - 1)
yield return buffer;
else
foreach (int[] child in FindCombosRec(buffer, done + 1, i + 1, end))
yield return child;
}
}

public static IEnumerable<int[]> FindCombinations(int m, int n)
{
return FindCombosRec(new int[m], 0, 0, n);
}

private static bool IsValidSet(int[] set, int maxIntersect)
{
foreach (var item in ValidCombinations)
{
if (set.Intersect(item).Count() > maxIntersect)
return false;
}

return true;
}
}

我从 here 得到了生成组合的基本代码.


问题

这是可行的,但对于更大范围的数字,此解决方案将花费大量时间才能完成。我知道,因为涉及组合算法,但必须有某种捷径或模式来简化它(我的小脑袋没弄明白)

非常感谢。

最佳答案

您的矩阵表示表明此问题与寻找一组固定大小、常数 Hamming weight 的不同二进制字同源或至少非常相似。并且有一个常量 Hamming distance在任何一对之间。

图形:

enter image description here

this question 中所述,这个问题不一定是微不足道的。特别是,建议的解决方案解释了如何构建 Hadamard matrix , 哪些行是您要查找的二进制单词。

Image taken from http://mathworld.wolfram.com/images/eps-gif/HadamardMatrices_800.gif

这看起来与您的矩阵非常相似。无论如何,您需要的是更通用的东西。与那种情况不同,您不希望每对行的距离正好为 n/2。 , 但距离不变 d < n/2 .

底线

轻松生成具有恒定大小(由您的 numbers 数组的长度确定)、恒定权重(由您的 k 确定)和恒定距离(由您的 nD 确定)的二进制字集的可能性在很大程度上取决于这些参数。鉴于some techniques for generating those sets依赖于对这些参数的一些假设,我的猜测是一般情况下没有有效的算法。

无论如何,如果您改写您的问题并在 MathOverflow 上提问,它可能会有用。 ,也许将这个问题和我链接的问题联系起来。

算法建议

至于算法(就像您的算法一样,不适用于大数),您可以尝试以下方法:

  1. 生成由k组成的二进制字后面跟着 (numbers.Length - nD)零并将其存储在列表中
  2. 迭代生成每一个恰好有 2*nD 的单词与你原来的词有点不同。
  3. 对于每个生成的单词,只有当它有 2*nD 时才尝试将其存储在列表中列表中每个词的距离。

与您的方法没有太大不同,但我认为您的方法可能会更好一些。

关于c# - 如何有效地生成组合而不重复它们之间的特定数字,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41607608/

30 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com