从一个固定的字母表中随机访问3个符号的有序集合的枚举

Question

假设我们有一个字母表，比如说，5个字符:ABCDE。

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

所以我们得到以下集合:

1. 美国广播公司
2. 阿布德
3. 阿贝
4. 亚洲农业发展署
5. 高手
6. 艾德
碱
7. 性碱性
8. 公元前
9. 溴化二苯醚
10. CDE

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

现在假设字母表长度为< code>N(本例中为5)，集合长度为< code>M(本例中为3)。知道了< code>N和< code>M，我们怎么可能:

1. 告诉最坏情况下的组合总数O（M N）（本例中的答案为10）
2. 在最坏的情况下输出任意给定数字（给定1，返回ABC；给定5，返回ACE等）的组合O（M N）

通过生成整个列表，用O（M^N）复杂度做这些事情很简单，但我想知道是否有更好的解决方案。

Answer 1

同意第一部分很简单，用你选择的语言写一个类似的等式。

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个组合。

回答你问题的第二部分...我正在考虑这件事，但无论如何都不是直截了当的。

Answer 2

第一个问题的答案很简单：它是C（n，r），我们要从一组大小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))

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

我使用的方法是找到第< code>i个输出集合的第一个元素，使用的思想是剩余集合元素的组合数可以用来找到哪一个应该是给定数字< code > 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个例子都是正确的。

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