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'))

sum要在任何地方使用和生成器表达式获取包含“LL”的项目数：

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

您可以'A' * 60 + 'B' * 20将可能的字符串表示为从range(80). 这些组合可以使用itertools:来计算itertools.combinations(range(80), 20)。这将您必须检查的字符串数量减少到只有......呃...... 3,535,316,142,212,174,320，这至少比 80 少很多！≈ 7×10^118，为排列方式的结果数。幸运的是，itertools.combinations它返回一个迭代器，因此只需使用 for 循环遍历表达式，在该循环中测试整数列表以查看是否有任何对相距 1。

于 2013-07-07T22:01:40.390 回答
0

独特的排列是：

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

我认为最好的答案，而不是一个非常模糊的讨论是：看看itertools 模块，它有一些不错的东西给你。

于 2013-07-07T21:59:04.790 回答
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!) = ~3.53*10^18 可能的 60 As 和 20 Bs 排列。现在您只需减去不包含序列“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

因此，我们将您的问题简化为一个简单的方程式。有多少种不同的解决方案？这可以通过星条形概念（定理二）来解决。

所以解决方案是 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

我们只考虑 B 的不连续的候选位置：

对于第一个 B 的每个起始位置，您需要至少间隔一个 A。用完所有 20 个 B（以及 20 个 As），并且您有一个 A 的尾部，其中包含剩余的 40 个 As 以及出现在最后一个 B，所以你总共有 41 个 A 的尾巴。

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

^___________minimal string____________^

                                       ^____________tail____________^

现在，为了计算这里的所有可能性，让我们考虑一下我们可以从尾部移动多少个位置A并将其插入 B 序列中。您可以将它移动到任何前面B，您将获得一个新的独特序列。因此，您最多可以将 41 个 As 移动到 20 个位置中的任何一个。

  • 如果你移动零作为，你会得到上面的字符串，所以只有一种可能性。

  • 如果你移动一个A，有20种可能性。

  • 如果你移动两个 A，你可以在上述移动一个 A 的任何一种可能性中的 20 个位置中的任何一个位置上移动一个 A，所以你有 20 2。

  • 如果移动三个 As，则为 20 3。你可以看到这里发生了什么...

等式 1：非连续 B 的唯一可能性数 = 20 0 + 20 1 + 20 2 + 20 3 + ... + 20 41

至于可能的总数，让我们做同样的事情，并安排所有的 B 没有间隙。现在有60个A的尾巴，可以插入20个B中的任何一个前面。

等式 2：唯一可能性的总数 = 20 0 + 20 1 + 20 2 + 20 3 + ... + 20 60

并且要找到DO有连续 B 的可能性的数量，可以公平地说，除了那些DON'T之外的所有可能性。这将是等式 2 减去等式 1。

等式 3：两个或多个连续 B 的唯一可能性数 = 20 42 + 20 43 + 20 44 + ... + 20 60

于 2013-07-08T00:27:17.780 回答