计算具有多重性且无顺序的集合分区的计数

Question

我有一段代码可以计算一组（可能重复的）整数的分区。但我感兴趣的是一组可能的划分和多重性

例如，您可以启动以下代码：

import numpy as np
from collections import Counter
import pandas as pd

def _B(i):
    # for a given multiindex i, we defined _B(i) as the set of integers containg i_j times the number j:
    if len(i) != 1:
        B = []
        for j in range(len(i)):
            B.extend(i[j]*[j])
    else:
        B = i*[0]
    return B

def _partition(collection):
    # from here: https://stackoverflow.com/a/62532969/8425270
    if len(collection) == 1:
        yield (collection,)
        return
    first = collection[0]
    for smaller in _partition(collection[1:]):
        # insert `first` in each of the subpartition's subsets
        for n, subset in enumerate(smaller):
            yield smaller[:n] + ((first,) + subset,) + smaller[n + 1 :]
        # put `first` in its own subset
        yield ((first,),) + smaller

def to_list(tpl):
    # the final hierarchy is
    return list(list(i) if isinstance(i, tuple) else i for i in tpl)


def _Pi(inst_B):
    # inst_B must be a tuple
    if type(inst_B) != tuple :
        inst_B = tuple(inst_B)
    pp = [tuple(sorted(p)) for p in _partition(inst_B)]
    c = Counter(pp)
    Pi = c.keys()
    N = list()
    for pi in Pi:
        N.append(c[pi])
    Pi = [to_list(pi) for pi in Pi]
    return Pi, N


if __name__ == "__main__":

    import cProfile
    pr = cProfile.Profile()
    pr.enable()
    sh = (3, 3, 3)
    rez = list()
    rez_sorted= list()
    rez_ref = list()
    for idx in np.ndindex(sh):
        if sum(idx) > 0:
            print(idx)
            Pi, N = _Pi(_B(idx))
            print(pd.DataFrame({'Pi': Pi, 'N': N * np.array([np.math.factorial(len(pi) - 1) for pi in Pi])}))
    pr.disable()
    # after your program ends
    pr.print_stats(sort="tottime")

对于整数元组的几个示例（由np.ndindex生成），这段代码计算我需要的分区和计数。一切都发生在_partition和_Pi函数中，这是您应该看到的

如果您仔细观察这两个函数是如何工作的，您将看到它们计算每个潜在分区，然后计算它们出现的次数。对于小问题，这很好，但是如果prolbme的大小增加，这将开始花费大量的时间。试试设置sh = (5,5,5)，你会明白我的意思

因此，问题如下：

有没有办法直接计算分区，而不是计算发生的次数？

编辑：我在mathoverflow there上交叉发布，他们在corrolary 2.10（pdf第10页）的this article中提出了一个解决方案。这一问题可以通过在这个迭代中实现集合p（v，r）来解决

我希望，就像在单变量情况下一样，这些集合会有一个很好的递归表达式，但我还没有找到

更多编辑：这个问题相当于查找多集的所有（多集）分区。如果求集的（集）-划分的解是由Bell部分多项式给出的，这里我们需要这些多项式的多元版本