1

40 文字の文字列のすべての組み合わせを見つけるにはどうすればよいですか?

D20と 20の組み合わせがいくつできるかを見つけなければなりませんR。

1つの組み合わせのように...

DDDDDDDDDDDDDDDDDDDDRRRRRRRRRRRRRRRRRRRR

それは 1 つの組み合わせですが、残りの組み合わせはどうすればわかりますか?

4

5 に答える 5

2

D20と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

実際に一意の順列を生成したい場合（これはお勧めしません）、それを行う1つの方法はを使用することitertools.combinations(range(40), 20)です。Dここで返される各要素は、20個の整数のタプルになります。これは、その特定の順列におけるそれぞれのインデックスになります。

于 2012-10-02T22:34:54.577 に答える
1

順列はたくさんあります。通常、それらを数えるためだけにそれらをすべて生成することはお勧めできません。これを解決する数式を探すか、動的計画法を使用して結果を計算する必要があります。

于 2012-10-02T22:21:45.693 に答える
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 に答える
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 を使用してこれを行う良い例です: Is there any pre-built method for find all permutations of a given string in 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

Depending on what you want to do with the combinations, there are a lot of ways to figure this out. If you just want to know the number of combinations/permutations that exist, math can tell you that.

If you want to do something like build a brute force algorithm that checks every possible arrangement of a given set of characters, itertools.product() can help.

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

于 2012-10-02T22:26:37.513 に答える