根据多数约束过滤 python 中的笛卡尔积（笛卡尔幂）

Question

我想知道基数幂 X^n（一组 X 本身的基数乘积，n 次）中的元素数量，其中有一个多数约束：X^n 中有多少元素具有（相对) 集合中一个元素的多数（比如 x）？

最重要的是，我想将基数中的一个元素固定为某个值（比如第二个），并计算具有该固定值的可能性的数量。

举个简单的例子，X={A, B, C}，n=4。问题是：有多少个 A 在第二个位置的四字母单词具有（相对）多数 A（答案：13，参见 here）？有多少人拥有 B 的（相对）多数？

在具有 3 行 ({A, B, C}) 和 n=4 列的网络中，假设路径从左到右（例如，使用节点 A1，然后是 B2，然后是 A3，最后是 C3），则问题变成：有多少条路径经过节点 A2 并且具有（相对）多数 A 节点？

I'm looking for a closed form formula，但找不到。

是否可以枚举所有产品并在 python 中进行筛选？

我的原始集合中有 8 个元素，我重复了它们 n=24 次。它非常大 (>10'9)，但它可能会被简化，也许吧？

Answer 1

我无法给你理论上的答案，但这里有一些 python 代码可以帮助你入门。

import itertools, collections

items = 'ABCDEFGH'
n = 4

r = collections.Counter()

# for symmetry reasons, it doesn't matter which position you "fix"
# so to count `'ABCD'^n` with fixed 'A' 
# we have to count `'ABCD'^n-1` and just add 1 for 'A'.    

for p in itertools.product(items, repeat=n-1):
    c = collections.Counter(p)
    c['A'] += 1
    m = c.most_common(2)
    if len(m) == 1 or m[0][1] > m[1][1]:
        r[m[0][0]] += 1
    else:
        r['no_major'] += 1

print r

关于您的具体数字，迭代 8^24 项听起来不现实。在你走到这一步之前，你必须推导出一个公式！

Answer 2

无法过滤且存在闭式公式（见数学here）

下面是 python 中解决这个问题的方法（灵感来自 here）：

安装sympy in order to have symbolic algebra in python (download，解压，进入文件夹，python setup.py install，就这样）
导入东西

from sympy.abc import x

from sympy import expand

from sympy import factorial

注意：不要使用 math 的阶乘，而是 sympy 的阶乘；所以不要 from math import factorial（参见）。

展开 多项式

d1 = expand()

提取系数

print d1[x**n]

对于简单的例子 here (n=4, m=3)，我们需要在此之上导入求和，字母j, k,

from sympy import summation

from sympy.abc import j, k

import math

d1 = expand(summation(x**(k-1)/factorial(k-1)*summation(x**(j-1)/factorial(j-1), (j, 1, k))**2, (k, 0, 4))).as_coefficients_dict()

d1[x**3] * math.factorial(3)

答案是13。

对于大例子， n=24，m=8：

d2 = expand(summation(x**(k-1)/factorial(k-1)*summation(x**(j-1)/factorial(j-1), (j, 1, k))**7, (k, 0, 24))).as_coefficients_dict()

d2[x**23] * math.factorial(23)

解是 105097074808684277656。计算需要 1-2 小时。

根据多数约束过滤 python 中的笛卡尔积（笛卡尔幂）

Filter cartesian products (cartesian powers) in python based on majority constraint

python

combinatorics

cartesian-product