1

I do have a piece of code that compute partitions of a set of (potentialy duplicated) integers. But i am interested in the set of possible partition and there multiplicity.

You can for exemple launch the follwoing code :

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

This code computes, for several examples of tuples of integer numbers (generated by np.ndindex) the partitions and counts i need. Everything happens in the _partition and the _Pi functions, this is were you should look at.

If you look closely at how these two functions are working, you'll see that they comput eevery potential partition and THEN count up how many times they appeared. For small problems, this is fine, but if the size of the prolbme increase, this starts to take a looooot of time. Try setting sh = (5,5,5), you'll see what i mean;

So the problem is the following :

Is there a way to compute directly the partitions and there number of occurences instead ?

Edit: I cross-posted on mathoverflow there, and they propose a solution in this article, in corrolary 2.10 (page 10 of the pdf). The problem could be solved by implmenting the sets p(v,r) in this corrolary.

I was hoping, as in the univariate case, that those sets would have a nice recursive expression but i ould not find one yet.

More Edit : This problem is equivalent to finding all (multiset)-partitions of a multiset. If the solution for finding (set)-partitions of a set is given by Bell partial polynomials, here we need multivariate version of these polynomials.

lrnv
  • 1,038
  • 8
  • 19
  • To make sure I understand: the tuple (0, 1, 2) means 0 copies of '0', one copy of '1', and 2 copies of '2'? And the number of partitions in this case would be 4? – Roy2012 Jun 24 '20 at 15:29
  • Yes, you understood correctly ! As the output of my code shows, there are 4 possible partitions, two with multiplicity One and two with multiplicity Two in this case. For higher problems, those multiplicity add up and slow me down a lot. – lrnv Jun 24 '20 at 15:33
  • The problem you're describing is referred to as partition of multi-set. I couldn't find a good solution, but there are a number of references to it in various places. For example, see here: https://math.stackexchange.com/questions/1381495/what-is-the-number-of-set-partitions-of-1-1-2-2-3-3 – Roy2012 Jun 24 '20 at 15:57
  • Yeah this is not quite exactly the same thing since there multiset is quite peculiar and they find a solution that would not apply to me; But indeed, this is my problem. – lrnv Jun 25 '20 at 08:31
  • Well, apparently - it's a hard problem. If I may ask - what's the use-case? – Roy2012 Jun 25 '20 at 08:33
  • also the same quesiton in ruby here : https://stackoverflow.com/questions/42215165/yielding-partitions-of-a-multiset-with-ruby The use case is Faa di bruno multivariate formula. Look at the post of Mathoverflow if you want to undertand more precisely; Actualy, i might have a solution that solves the math problem but i still cant work out the implementation -- i'll edit the post so you can see what i mean. – lrnv Jun 25 '20 at 08:39

0 Answers0