4

给定一个固定长度的位数组以及它包含的 0 和 1 的数量，我如何安排所有可能的组合，以便返回第 i 个组合花费尽可能少的时间？它们返回的顺序并不重要。

这是一个例子：

array length = 6
number of 0s = 4
number of 1s = 2

可能的组合 (6! / 4! / 2!) 000011 000101 000110 001001 001010 001100 010001 010010 010100 011000 100001 100010 100100 101000 110000

问题 第 1 组合 = 000011 第 5 组合 = 001010 第 9 组合 = 010100

使用不同的排列方式，例如 100001 100010 100100 101000 110000 001100 010001 010010 010100 011000 000011 000101 000110 001001 001010

它应返回第 1 个组合 = 100001 第 5 个组合 = 110000 第 9 个组合 = 010100

目前我正在使用 O(n) 算法来测试每个位是 1 还是 0。问题是我需要处理很多非常长的数组（大约 10000 位），所以它仍然非常慢（而且缓存是不可能的）。我想知道您是否认为可能存在更快的算法。

谢谢

4

3 回答 3

1

我不确定我是否理解这个问题，但如果你只想要第 i 个组合而不生成其他组合，这里有一个可能的算法：

有 C(M,N)=M!/(N!(MN)!) 个将 N 位设置为 1 的组合，最高位在位置 M。

你想要第 i 个：你迭代地递增 M 直到 C(M,N)>=i

while( C(M,N) < i ) M = M + 1

这将告诉您设置的最高位。当然，您使用迭代计算组合

C(M+1,N) = C(M,N)*(M+1)/(M+1-N)

找到后，您会遇到查找第 (iC(M-1,N)) 个 N-1 位组合的问题，因此您可以在 N 中应用递归...
这是 D=C(M+) 的可能变体1,N)-C(M,N)，并且 I=I-1 使其从零开始

SOL=0
I=I-1
while(N>0)
    M=N
    C=1
    D=1
    while(i>=D)
        i=i-D
        M=M+1
        D=N*C/(M-N)
        C=C+D
    SOL=SOL+(1<<(M-1))
    N=N-1
RETURN SOL

如果你有那么多位，这将需要大整数运算......

于 2012-08-18T23:54:54.333 回答
0

您的问题似乎受到二项式系数的限制。在您给出的示例中，问题可以翻译如下：

有 6 个项目，一次可以选择 2 个。通过使用二项式系数，可以将唯一组合的总数计算为 N! / (K! (N - K)!，对于 K = 2 的情况，简化为 N(N-1)/2。将 6 代入 N，我们得到 15，这与您计算的组合数量相同6！/ 4！/ 2！ - 这似乎是另一种计算二项式系数的方法，这是我以前从未见过的。我也尝试过其他组合，两个公式产生相同数量的组合。所以，它看起来像您的问题可以转化为二项式系数问题。

鉴于此，您似乎可以利用我编写的一个类来处理处理二项式系数的常用函数：

  1. 将任何 N 选择 K 的所有 K 索引以良好的格式输出到文件。K-indexes 可以替换为更具描述性的字符串或字母。这种方法使得解决这类问题变得非常简单。

  2. 将 K 索引转换为已排序二项式系数表中条目的正确索引。这种技术比依赖迭代的旧已发布技术快得多。它通过使用帕斯卡三角形固有的数学属性来做到这一点。我的论文谈到了这一点。我相信我是第一个发现并发表这种技术的人，但我可能是错的。

  3. 将已排序二项式系数表中的索引转换为相应的 K 索引。

  4. 使用Mark Dominus方法计算二项式系数，它不太可能溢出并且适用于更大的数字。

  5. 该类是用 .NET C# 编写的，并提供了一种通过使用通用列表来管理与问题相关的对象（如果有）的方法。此类的构造函数采用一个名为 InitTable 的 bool 值，当它为 true 时，将创建一个通用列表来保存要管理的对象。如果此值为 false，则不会创建表。无需创建表即可执行上述 4 种方法。提供了访问器方法来访问表。

  6. 有一个关联的测试类，它显示了如何使用该类及其方法。它已经用 2 个案例进行了广泛的测试，并且没有已知的错误。

要了解此类并下载代码，请参阅制表二项式系数。

将此类转换为您选择的语言应该不难。

可能存在一些限制，因为您使用的 N 非常大，最终可能会创建比程序可以处理的更大的数字。如果 K 也可以很大，则尤其如此。目前，该类仅限于 int 的大小。但是，更新它以使用 long 应该不难。

于 2012-09-25T11:21:57.240 回答
0

如果排序无关紧要（它只需要保持一致），我认为最快的做法是让组合（i）返回任何你想要的具有所需密度的东西，第一次用参数调用组合（）一世。然后将该值存储在成员变量中（例如，将值 i 作为键并将您返回的组合作为其值的哈希图）。第二次调用combination(i)，你只需在hashmap中查找i，找出你之前返回的内容，然后再次返回。

当然，当您返回参数（i）的组合时，您需要确保它不是您之前为其他参数返回的东西。

如果您将被要求返回的数字明显小于组合总数，那么第一次调用组合（i）的一个简单实现是使用全 0 生成一个正确长度的值，随机设置 num_ones位为 1，然后确保它不是您已经为不同的 i 值返回的位。

于 2012-08-18T19:30:16.967 回答