随机访问固定字母表中3个符号的有序集合的枚举-Java 学习之路

想象一下，我们有一个字母表，例如5个字符： ABCDE .

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

所以我们得到以下几组：

共10套 . 该命令是词典 .

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

告诉最坏的组合总数 O(M+N) （本例中答案是10）？
输出任意给定数字的组合（给定1，返回ABC;给定5，返回ACE等）最差 O(M+N) ？

通过生成整个列表来做那些具有复杂性的事情是微不足道的，但我想知道是否有更好的解决方案 .

2 回答

1
第一个问题的答案很简单：它是 C(n,r) ，我们将从一组大小 n 中选择 r 项目的所有组合 . 其他地方的公式是here：
```
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 输出集的第一个元素：剩余集合元素的组合数可用于查找哪个应该是给定数字 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（MN），如果我们假设 factorial() 函数可以在恒定时间内计算，我认为这不是一个不好的近似，除非它实施很幼稚 .
回复于 2024-04-16T23:53:25+08:00
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个组合 .

要做你问题的第二部分......我只是想着它，但它不是直截了当的 .
回复于 2024-04-16T23:53:25+08:00

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

2 回答

相关问题