CODEWITHSUNDEEP
algorithmpartitioningcombinatorics
Azizi
Azizi

Reputation: 43

Number of partitions with a given constraint

Consider a set of 13 Danish, 11 Japanese and 8 Polish people. It is well known that the number of different ways of dividing this set of people to groups is the 13+11+8=32:th Bell number (the number of set partitions). However we are asked to find the number of possible set partitions under a given constraint. The question is as follows:

A set partition is said to be good if it has no group consisting of at least two people that only includes a single nationality. How many good partitions there are for this set? (A group may include only one person.)

The brute force approach requires going though about 10^26 partitions and checking which ones are good. This seems pretty unfeasible, especially if the groups are larger or one introduces other nationalities. Is there a smart way instead?

EDIT: As a side note. There probably is no hope for a really nice solution. A highly esteemed expert in combinatorics answered a related question, which, I think, basically says that the related problem, and thus this problem also, is very difficult to solve exactly.

Upvotes: 4

Views: 510

Answers (2)

Karoly Horvath
Karoly Horvath

Reputation: 96266

Here's a solution using dynamic programming.

It starts from an empty set, then adds one element at a time and calculates all the valid partitions.

The state space is huge, but notice that to be able to calculate the next step we only need to know about a partition the following things:

  • For each nationality, how many sets it contains that consists of only a single member of that nationality. (e.g.: {a})
  • How many sets it contains with mixed elements. (e.g.: {a, b, c})

For each of these configurations I only store the total count. Example:

[0, 1, 2, 2] -> 3
{a}{b}{c}{mixed} 
   e.g.: 3 partitions that look like: {b}, {c}, {c}, {a,c}, {b,c}

Here's the code in python:

import collections
from operator import mul
from fractions import Fraction

def nCk(n,k):
  return int( reduce(mul, (Fraction(n-i, i+1) for i in range(k)), 1) )

def good_partitions(l):
    n = len(l)
    i = 0
    prev = collections.defaultdict(int)
    while l:
        #any more from this kind?
        if l[0] == 0:
            l.pop(0)
            i += 1
            continue
        l[0] -= 1
        curr = collections.defaultdict(int)

        for solution,total in prev.iteritems():
            for idx,item in enumerate(solution):
                my_solution = list(solution)
                if idx == i:
                    # add element as a new set
                    my_solution[i] += 1
                    curr[tuple(my_solution)] += total
                elif my_solution[idx]:
                    if idx != n:
                        # add to a set consisting of one element
                        # or merge into multiple sets that consist of one element
                        cnt = my_solution[idx]
                        c = cnt
                        while c > 0:
                            my_solution = list(solution)
                            my_solution[n] += 1
                            my_solution[idx] -= c
                            curr[tuple(my_solution)] += total * nCk(cnt, c)
                            c -= 1
                    else:
                        # add to a mixed set
                        cnt = my_solution[idx]
                        curr[tuple(my_solution)] += total * cnt

        if not prev:
            # one set with one element
            lone = [0] * (n+1)
            lone[i] = 1
            curr[tuple(lone)] = 1

        prev = curr
    return sum(prev.values())

print good_partitions([1, 1, 1, 1])      # 15
print good_partitions([1, 1, 1, 1, 1])   # 52
print good_partitions([2, 1])            # 4
print good_partitions([13, 11, 8])       # 29811734589499214658370837

It produces correct values for the test cases. I also tested it against a brute-force solution (for small values), and it produces the same results.

Upvotes: 2

btilly
btilly

Reputation: 46408

An exact analytic solution is hard, but a polynomial time+space dynamic programming solution is straightforward.

First of all, we need an absolute order on the size of groups. We do that by comparing how many Danes, Japanese, and Poles we have.

Next, the function to write is this one.

m is the maximum group size we can emit

p is the number of people of each nationality that we have left to split

max_good_partitions_of_maximum_size(m, p) is the number of "good partitions"
we can form from p people, with no group being larger than m

Clearly you can write this as a somewhat complicated recursive function that always select the next partition to use, then call itself with that as the new maximum size, and subtract the partition from p. If you had this function, then your answer is simply max_good_partitions_of_maximum_size(p, p) with p = [13, 11, 8]. But that is going to be a brute force search that won't run in reasonable time.

Finally apply https://en.wikipedia.org/wiki/Memoization by caching every call to this function, and it will run in polynomial time. However you will also have to cache a polynomial number of calls to it.

Upvotes: 0

Related Questions