0

これが私が欲しいものです。6 つの A と 2 つの B がある場合、考えられるすべての組み合わせを取得するにはどうすればよいですか?

元： AAAAAABB, AAAAABAB, AAAABAAB, AAABAAAB, AABAAAAB, ABAAAAAB, BAAAAAAB, etc

私は本当に 60 個の A と 20 個の B でこれを行い、結果のどこかに BB がある回数を見つけようとしています。可能であれば、今すぐ賞金を投稿します。

4

6 に答える 6

2

使用itertools.permutations:

>>> from itertools import permutations
for p in permutations('AAAAAA'+'LL'):
    print ("".join(p))
...

setsユニークなアイテムが必要な場合に使用します。

unique=set(i for  i in permutations('AAAAAA'+'LL'))

どこでも 'LL' を含む項目の数を取得するにはsum、ジェネレーター式を使用します。

sum('LL' in "".join(i) for i in permutations('AAAAAA'+'LL'))
于 2013-07-07T21:48:32.150 に答える
2

(多くの重複を返す) の順列を計算するのではなく'A' * 60 + 'B' * 20、可能な文字列を から取得した 20 個の整数 (B の位置を表す) の組み合わせとして表すことができますrange(80)。itertoolsこれらの組み合わせは、 :を使用して計算できますitertools.combinations(range(80), 20)。これにより、調べなければならない文字列の数が 3,535,316,142,212,174,320 にまで削減されます。これは、少なくとも 80 よりもはるかに少ない数です。≈ 7×10^118、順列方法の結果の数。幸いなことにitertools.combinations、反復子が返されるため、整数のリストをテストして 1 離れているペアがあるかどうかを確認する for ループで式を反復するだけです。

于 2013-07-07T22:01:40.390 に答える
0

連続していないB の候補位置を考えてみましょう。

最初の B の開始位置ごとに、少なくとも 1 つの A の間隔をあける必要があります。20 個の B をすべて (20 個の As と共に) 使い切ると、残りの 40 個の As と、その後に発生するものを含む A の末尾が得られます。最後の B なので、合計で 41 A のテールがあります。

0        1         2         3         4                  7         8
1234567890123456789012345678901234567890123...         ...01234567890
BABABABABABABABABABABABABABABABABABABABAAAA               AAAAAAAAAAA

^___________minimal string____________^

                                       ^____________tail____________^

Aさて、ここですべての可能性を数えるために、尾からいくつの位置を移動して B シーケンスに挿入できるかを考えてみましょう。これを任意の の前に移動するとB、新しい一意のシーケンスが得られます。したがって、最大 41 A を 20 の位置のいずれかに移動できます。

  • As を 0 にすると上の文字列になるので、可能性は 1 つだけです。

  • Aを1つ動かすと、20通りの可能性があります。

  • 2 つの A を移動する場合、上記の 1 つの A を移動する可能性のいずれかの 20 の位置のいずれかで移動できるため、20 2になります。

  • A を 3 つ動かすと、20 3になります。ここで何が起こっているかを見ることができます...

式 1: 連続しない Bs を持つ一意の可能性の数 = 20 0 + 20 1 + 20 2 + 20 3 + ... + 20 41

可能性の総数についても同様に、すべての B を隙間なく並べてみましょう。20 個の B の前に挿入できる 60 個の As のテールがあります。

式 2: 一意の可能性の総数 = 20 0 + 20 1 + 20 2 + 20 3 + ... + 20 60

DOが連続する B を持つ可能性の数を見つけるには、 DON'Tでないものを除くすべてであると言っても過言ではありません。これは、式 2 から式 1 を引いたものになります。

式 3: B が 2 つ以上連続する一意の可能性の数 = 20 42 + 20 43 + 20 44 + ... + 20 60

于 2013-07-08T00:27:17.780 に答える
0 
from itertools import combinations
n_A, n_B = 60, 20
total = n_A + n_B
for pos in combinations(range(total), n_B):
    pos = sorted(pos)
    good = sum( i1 + 1 == i2 for i1, i2 in zip(pos, pos[1:]))
    if good:
        l = [ 'B' if i in pos else 'A' for i in range(total) ]
        print "".join(l)
于 2013-07-07T22:27:07.820 に答える
0

皆さんは早い段階で答えを受け入れます：これは非常に短い解決策です：

(60+20)!/(60!*20!) = 60 個の As と 20 個の B の可能な順列は ~3.53*10^18 あります。これで、シーケンス 'BB' を含まないケースを差し引くだけで済みます。これは少しトリッキーかもしれません:

興味深いシーケンスの形式は次のとおりです。

A....ABA....ABA....ABA.... ....ABA....A
<----> <----> <----> <---- ----> <---->
  n1  1  n2  1  n3  1  n4   n20 1 n21

したがって、n1 As、次に 1 B、次に n2 As、次に 1 B が交互に存在します。

n1 + 1 + n2 + 1 + n3 + ... + n20 + 1 + n21 = 80

これは次のようになります: n1 + n2 + n3 + ... + n21 = 60.

n1>=0、n1...n20>=1、n21>=0 であることに注意してください (シーケンスは B で開始または終了できるため)

m1 = n1、m2 = n2 - 1、m3 = n3 - 1、m4 = n4 - 1、...、m20 = n20 - 1、m21 = n21 を代入すると、次のようになります。

m1 + m2 + m3 + ... + m21 = 41 with n1 ... n21 >= 0

そこで、問題を単純な方程式に減らしました。いくつの異なるソリューションがありますか? これは、星と棒の概念 (定理 2)で解決できます。

したがって、解は C_41^{41+21-1} = C_41^61 = 61!/(41!*20!) です。

したがって、「BB」のサブシーケンスがない順列はいくつありますか?

80!/(60!*20!) - 61!/(41!*20!) = 3.529.079.495.508.414.925

プログラミングはまったく必要ありません。:)

于 2013-07-07T23:19:53.163 に答える
0

一意の順列は次のとおりです。

 from itertools import permutations
 unique=set([i for  i in permutations('AAAAAA'+'LL')])

非常に漠然とした議論をする代わりに、最良の答えは次のとおりだと思います: itertools モジュールを見てください。

于 2013-07-07T21:59:04.790 に答える