1

想象一下，我们有一个由 5 个字符组成的字母表：ABCDE。

我们现在要枚举所有可能的 3 个这些字母的集合。每个字母只能出现一次是一个集合，字母的顺序无关紧要（因此应该对集合中的字母进行排序）。

所以我们得到以下集合：

  1. 美国广播公司
  2. ABD
  3. 安倍
  4. ACD
  5. 高手
  6. ADE
  7. BCD
  8. 公元前
  9. 溴化二苯醚
  10. CDE

一共10套。该顺序是按字典顺序排列的。

现在让我们假设字母长度为N（本例中为 5），集合长度为（本例中为M3）。知道N并且M，如果可能的话，我们怎么能：

  1. 说出最坏情况下的组合总数O(M+N)（本例中的答案是 10）？
  2. 在最坏的情况下输出任何给定数字的组合（给定 1，返回 ABC；给定 5，返回 ACE 等等）O(M+N)？

通过生成整个列表来完成这些复杂的事情是微不足道的O(M^N)，但我想知道是否有更好的解决方案。

4

2 回答 2

1

第一个问题的答案很简单：就是C(n,r)，我们r要从一组 size 中选择所有项目的组合n。公式在其他地方：

C(n,r) = n! / (r! (n-r)!)

选择i'th组合而不计算所有其他组合的能力将取决于是否具有将组合编号i与组合相关联的编码。这将更具挑战性，需要更多的思考......

（编辑）

在对问题进行了更多思考之后，Python 中的解决方案如下所示：

from math import factorial

def combination(n,r):
    return factorial(n) / (factorial(r) * factorial(n-r))

alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

def showComb(n,r,i,a):
    if r < 1:
        return ""
    rr = r-1
    nn = max(n-1,rr)
    lasti = i
    i -= combination(nn,rr)
    j = 0
    while i > 0:
        j += 1
        nn = max(nn-1,1)
        rr = min(rr,nn)    # corrected this line in second edit
        lasti = i
        i -= combination(nn,rr)
    return a[j] + showComb(n-j-1,r-1,lasti,a[(j+1):])

for i in range(10):
    print(showComb(5,3,i+1,alphabet))

...输出问题中显示的列表。

我使用的方法是找到i'th输出集合的第一个元素，使用剩余集合元素的组合数可用于查找给定 number 的第一个元素的想法i。

也就是说，对于 C(5,3)，第一个 C(4,2) (=6) 输出集的第一个字符为 'A'，然后下一个 C(3,1) (=3) 输出集具有'B' 然后 C(1,1) (=1) 集合将 'C' 作为它们的第一个字符。

然后该函数递归地找到剩余的元素。请注意，它showComb()是尾递归的，因此如果您愿意，可以将其表示为循环，但我认为在这种情况下递归版本更容易理解。

为了进一步测试，以下代码可能有用：

import itertools

def showCombIter(n,r,i,a):
    return ''.join(list(itertools.combinations(a[0:n],r))[i-1])

print ("\n")

# Testing for other cases   
for i in range(120):
    x = showComb(10,3,i+1,alphabet)
    y = showCombIter(10,3,i+1,alphabet)
    print(i+1,"\t",x==y,"\t",x,y)

...这证实了这个案例的所有 120 个例子都是正确的。

我没有准确计算时间复杂度，但调用次数showComb()将是r并且while循环将执行n次数或更少。因此，在问题的术语中，如果我们假设函数可以在恒定时间内计算，我很确定复杂度将小于 O(M+N)，factorial()我认为这不是一个糟糕的近似值，除非它的实现是幼稚的。

于 2013-03-30T03:09:10.210 回答
0

同意第一部分很容易，将与此类似的等式放入您选择的语言中。

x=12
y=5
z=1
base=1
until [[ $z -gt y ]]
do
 base=`echo $x $z $base|awk '{print ($1/$2) * $3}'`
 x=`expr $x - 1`
 z=`expr $z + 1`
 echo base:$base
done

echo $base

上面的示例使用 12 个项目，以 5 个为一组排列，共有 792 种组合。

做你问题的第二部分......我只是在想它，但无论如何都不是直截了当的。

于 2013-03-30T04:51:13.810 回答