python - 如何在 Python 3 中将迭代过程扩展到大尺寸

Question

抛硬币 n 次(n=10)后，有 2^10=1024 种可能的结果。我用过

lst = [list(i) for i in itertools.product([0, 1], repeat=n)] 

得到n=10所有可能的结果，然后我想找出组的数量(m)，它被定义为硬币相同面的最大连续序列。比如HHHTTHTTHT，这个结果的组数是6，分别是(HHH)(TT)(H)(TT)(H)(T)。我雇用了

group=[len([len(list(grp)) for k, grp in groupby(x)]) for x in lst]

求出 10 次抛硬币的每个对应组合的组数 (m)。最后，我得到了组数大于6(m)的可能组合的数量，例如，

Group6=len(list(filter(lambda x:x>m,group)))

但是，当 throw 次数增加时，例如 (n=200,m=110) 或 (n=500, m=260)。我在Python中仍然使用与上面相同的代码，但是它耗时并且我认为它超过了python的内存大小。当 n 和 m 很大时，有人可以帮我弄清楚如何解决这个问题吗？谢谢

Answer 1

遍历所有可能的 throw 绝对不适用于大的 n(我猜这里的 n 已经比 20 大了)。只能使用一些组合学有效地计算这一点。

让我们首先从一个简单的例子开始:最少两组进行四次 throw :如果我们想计算导致两次更多组的 throw 次数。有几种可能性(我们将组编号为 1、2 等):

两组:

1112
1122
1222

三组:

1123
1223
1233

四组:

1234

我们知道组 G1 的值将不同于 G2 的值，G2 的值将不同于 G3 等等。所以它认为:

G1 != G2 != G3 != ... != Gn

因为只有两个值(heads 和 tails)，这意味着如果我们确定第一组，我们就确定了值对于所有组。如果 G1 是正面，则所有偶数组都是反面，所有奇数组都是正面。

所以这意味着对于上面的每个组合，恰好有两个配置。这意味着对于 n=4,m=1 的情况，有 2×7=14 个配置(这正是我们在使用您问题中的程序计算时得到的) .

现在我们仍然要面对的唯一问题是如何我们将计算这些 super 配置。我们可以通过引入我称之为升级的符号来做到这一点:

You notate an increase of the group with 1 and the same group with 0.

所以现在 1223 变成了 0101:我们升级了第二个和第四个索引上的组。而 1234 是 0111。这有什么帮助？事实上，对于 k 个组，我们只需要计算具有 k-1 个升级的组合数。所以这意味着组合的数量 (k-1 nCr n-1)。 n 是字符串的长度(或 throw 的总数)，k 是组数*。现在 (k-1 nCr n) 定义为:(n-1)!/((k-1)!*(n-k)!)。使用 ! 阶乘。我从here 借用了一种计算nCr 的方法:

导入操作符作为操作从 functools 导入减少

def ncr(n, r):
    r = min(r, n-r)
    if r == 0: return 1
    return reduce(op.mul,range(n-r+1,n+1))//reduce(op.mul,range(1,r+1))

现在最后一步只是计算高于 m 到 n 的每个 k 的组合数(乘以二) .所以:

def group_num(n,m):
    total = 0
    for i in range(m+1,n+1):
        total += ncr(n-1,i-1)
    return 2*total

或将其放入单行中:

def group_num(n,m):
    return 2*sum(ncr(n-1,i-1) for i in range(m+1,n+1))

现在我们可以测试我们的代码了:

>>> group_num(4,1)
14
>>> group_num(10,6)
260
>>> group_num(200,110)
125409844583698900384745448848066934911164089598228258053888
>>> group_num(500,260)
606609270097725645141493459934317664675833205307408583743573981944035656294544972476175251556943050783856517254296239386495518290119646417132819099088

哪些是预期数字(前两个)。正如您所看到的那样，总量急剧增加，因此即使是一次计算一次抛掷次数的最快算法也很容易被这种方法超越(计算结果不到一秒)。

ncr 函数可以在 O(n) 中计算(但这甚至可以通过对阶乘使用 memoize 来改进)；因此 group_num 函数在 O((n-m)×n) 中计算(没有内存优化)。因此，这完全超过了指数行为。