1

如何找到 40 个字母字符串的所有组合？

D我必须找出 20和 20R可以组成多少种组合。

因为在一种组合中可能是......

DDDDDDDDDDDDDDDDDDDDRRRRRRRRRRRRRRRRRRRR

那是1个组合，现在我该如何计算其余的？

4

5 回答 5

2

要计算 20D和 20的每个组合R，我们可以认为有 40 个“槽”，其中 20 个槽将由 填充D，其余的将由 填充R。所以，我们可以用C(40, 20)来计算组合的总数，或者40选20，可以用下面的公式来表示：

40!/(20!*(40-20)!)

或者在 Python 中：

>>> import math
>>> math.factorial(40) / (math.factorial(20) * math.factorial(40-20))
137846528820L

请注意，这与具有 20和 20的字符串的唯一排列数相同，但如果您只计算该字符串的排列数，您将计算出很多重复项，如果您尝试通过以下方式计算创建每个排列都需要很长时间。DR

如果您想实际生成独特的排列（我不建议这样做），一种方法是使用itertools.combinations(range(40), 20). 这里返回的每个元素都是 20 个整数的元组，这将是该D特定排列中每个元素的索引。

于 2012-10-02T22:34:54.577 回答
1

有很多排列组合。仅仅为了计算它们而生成它们通常不是一个好主意。您应该寻找一个数学公式来解决这个问题，或者可能使用动态编程来计算结果。

于 2012-10-02T22:21:45.693 回答
0

这是一个内置在 itertools 中的不错的函数：

这直接取自此链接：9.7。itertools — 创建迭代器以实现高效循环的函数

def permutations(iterable, r=None):
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = range(n)
    cycles = range(n, n-r, -1)
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return

编辑

我已经包含了一个我在 SO 上找到的链接，它提供了一个使用 JavaScript 执行此操作的很好的示例：是否有任何预先构建的方法可以在 JavaScript 中查找给定字符串的所有排列？

如果您不介意 PHP，以下是直接取自此链接的示例：4.26。查找数组的所有排列

注意：要使用该pc_permute函数，您需要将字符串分成字符数组。

function pc_permute($items, $perms = array( )) {
    if (empty($items)) { 
        print join(' ', $perms) . "\n";
    }  else {
        for ($i = count($items) - 1; $i >= 0; --$i) {
             $newitems = $items;
             $newperms = $perms;
             list($foo) = array_splice($newitems, $i, 1);
             array_unshift($newperms, $foo);
             pc_permute($newitems, $newperms);
         }
    }
}
于 2012-10-02T22:14:43.823 回答
0

根据您想对组合执行的操作，有很多方法可以解决这个问题。如果您只想知道存在的组合/排列的数量，数学可以告诉您。

如果您想做一些事情，比如构建一个蛮力算法来检查给定字符集的所有可能排列，itertools.product() 可以提供帮助。

http://docs.python.org/library/itertools.html#module-itertools

于 2012-10-02T22:26:37.513 回答
0

这是一个生成所有不同排列的生成器。 

def distinct_pem(A,D):
    if A==0: yield 'D'*D
    elif D==0: yield 'A'*A
    elif A==1 and D==1:
        yield 'AD'
        yield 'DA'
    else:
        if A>=2:
            for string in distinct_pem(A-2,D):
                yield  'AA'+string
        if A>1 and D>1:
            for string in distinct_pem(A-1,D-1):
                yield  'AD'+string
                yield  'DA'+string
        if D>=2:
            for string in distinct_pem(A,D-2):
                yield  'DD'+string

对于 10，这是非常快的，但它与 20（也许它可以变得更有效率？）斗争。

于 2012-10-02T23:30:53.707 回答