Set partition with constraints in Python

Question

I had a hard time to deal with a group partition issue. Will someone shed some light for me please?

Let me simplify my question. I want to divide ten numbers (i.e., 0, 1, ..., 9) into three groups, with (4, 3, 3) numbers each group. The conditions are:

1. Within-group sequence dones't matter. For example, [(0, 1, 2, 3), (4, 5, 6), (7, 8, 9)] will be treated to be the same as [(3, 0, 1, 2), (5, 6, 4), (7, 8, 9)].

2. I want to keep (1, 2, 3) always in the same group, and so does for (7, 8).

How can I list all the possible grouping scenarios which meet the above criteria? Thanks a lot!

I am using Python 2.7.

Answer 1

So you want to partition in 3 blocks of size 4,3,3, with (1,2,3) in one block and (7,8) in one block.

That means that 1,2,3 and 7,8 cannot be in same block.

Let first forget the keyboard and analyse the problem

IMHO, you should separate 3 cases :

• 1,2,3 are in block of size 4 (case 1)
• 7,8 are in block of size 4 (case 2)
• neither 1,2,3 nor 7,8 and in block of size 4 (case 3)

Case 1

• one element from (0,4,5,6,9) goes in block containing (1, 2, 3)
• one other element from (0,4,5,6,9) goes in block containing (7,8)

total : 5*4 = 20 different partitions

Case 2

• two elements from (0,4,5,6,9) go in block containing (7,8)

total : 5*4/2 = 10 different partitions (/2 because you want combinations and not permutations)

Case 3

• one element from (0,4,5,6,9) goes in block containing (7,8)

total : 5 different partitions

So you know you shall have 35 different partitions

Python code :

def gen():
    B1 = [1,2,3]
    B2 = [7,8]
    C = [x for x in range(10) if x not in B1 + B2 ]
    def gen1():
        for x in C:
            c = C[:]
            b1 = B1[:]
            b1.append(x)
            c.remove(x)
            for y in c:
                c1 = c[:]
                b2 = B2[:]
                b2.append(y)
                c1.remove(y)
                yield(b1, b2, c1)
    def gen2():
        for i in range(len(C)-1):
            for j in range(i+1, len(C)):
                b2 = B2 + [C[i], C[j]]
                c = [C[k] for k in range(len(C)) if k not in (i,j)]
                yield (B1, b2, c)
    def gen3():
        for x in C:
            b2 = B2[:]
            c = C[:]
            c.remove(x)
            b2.append(x)
            yield(B1, b2, c)
    for g in (gen1, gen2, gen3):
        for t in g():
            yield t

And you get correctly :

>>> list(gen())
[([1, 2, 3, 0], [7, 8, 4], [5, 6, 9]), ([1, 2, 3, 0], [7, 8, 5], [4, 6, 9]),
 ([1, 2, 3, 0], [7, 8, 6], [4, 5, 9]), ([1, 2, 3, 0], [7, 8, 9], [4, 5, 6]),
 ([1, 2, 3, 4], [7, 8, 0], [5, 6, 9]), ([1, 2, 3, 4], [7, 8, 5], [0, 6, 9]),
 ([1, 2, 3, 4], [7, 8, 6], [0, 5, 9]), ([1, 2, 3, 4], [7, 8, 9], [0, 5, 6]),
 ([1, 2, 3, 5], [7, 8, 0], [4, 6, 9]), ([1, 2, 3, 5], [7, 8, 4], [0, 6, 9]),
 ([1, 2, 3, 5], [7, 8, 6], [0, 4, 9]), ([1, 2, 3, 5], [7, 8, 9], [0, 4, 6]),
 ([1, 2, 3, 6], [7, 8, 0], [4, 5, 9]), ([1, 2, 3, 6], [7, 8, 4], [0, 5, 9]),
 ([1, 2, 3, 6], [7, 8, 5], [0, 4, 9]), ([1, 2, 3, 6], [7, 8, 9], [0, 4, 5]),
 ([1, 2, 3, 9], [7, 8, 0], [4, 5, 6]), ([1, 2, 3, 9], [7, 8, 4], [0, 5, 6]),
 ([1, 2, 3, 9], [7, 8, 5], [0, 4, 6]), ([1, 2, 3, 9], [7, 8, 6], [0, 4, 5]),
 ([1, 2, 3], [7, 8, 0, 4], [5, 6, 9]), ([1, 2, 3], [7, 8, 0, 5], [4, 6, 9]),
 ([1, 2, 3], [7, 8, 0, 6], [4, 5, 9]), ([1, 2, 3], [7, 8, 0, 9], [4, 5, 6]),
 ([1, 2, 3], [7, 8, 4, 5], [0, 6, 9]), ([1, 2, 3], [7, 8, 4, 6], [0, 5, 9]),
 ([1, 2, 3], [7, 8, 4, 9], [0, 5, 6]), ([1, 2, 3], [7, 8, 5, 6], [0, 4, 9]),
 ([1, 2, 3], [7, 8, 5, 9], [0, 4, 6]), ([1, 2, 3], [7, 8, 6, 9], [0, 4, 5]),
 ([1, 2, 3], [7, 8, 0], [4, 5, 6, 9]), ([1, 2, 3], [7, 8, 4], [0, 5, 6, 9]),
 ([1, 2, 3], [7, 8, 5], [0, 4, 6, 9]), ([1, 2, 3], [7, 8, 6], [0, 4, 5, 9]),
 ([1, 2, 3], [7, 8, 9], [0, 4, 5, 6])]

(manual formatting to ease reading ...)

Answer 2

For comb in combination k=3 in (0,4,5,6,9), remaining a, b:
(g1+a, g2+b, comb)    (g1+b, g2+a, comb)
(g2+a+b, g3, g1)

For comb in combination k=4 in (0,4,5,6,9), remaining a:
(comb, g1, g2+a)

---

from itertools import combinations, permutations

def partition_generator():
  wildcards = (0,4,5,6,9)
  g1, g2 = (1,2,3), (7,8)
  for comb in combinations(wildcards, 3):
    unused = remaining(wildcards, comb)
    for r in permutations(unused):
      yield part(g1, g2, comb, r)
    yield part(g2, g1, comb, unused)
  for comb in combinations(wildcards, 4):
    yield part(comb, g1, g2, remaining(wildcards, comb))

def remaining(a, b):
  return [ x for x in a if x not in b ]

def part(x,y,z,remaining):
  q = list(remaining)
  while len(x) < 4:
    x = x + (q.pop(0),)
  if len(y) < 3:
    y = y + (q.pop(0),)
  if len(z) < 3:
    z = z + (q.pop(0),)
  return (x,y,z)

>>> for partition in partition_generator():
...   print(partition)
...
((1, 2, 3, 6), (7, 8, 9), (0, 4, 5))
((1, 2, 3, 9), (7, 8, 6), (0, 4, 5))
((7, 8, 6, 9), (1, 2, 3), (0, 4, 5))
((1, 2, 3, 5), (7, 8, 9), (0, 4, 6))
((1, 2, 3, 9), (7, 8, 5), (0, 4, 6))
((7, 8, 5, 9), (1, 2, 3), (0, 4, 6))
((1, 2, 3, 5), (7, 8, 6), (0, 4, 9))
((1, 2, 3, 6), (7, 8, 5), (0, 4, 9))
((7, 8, 5, 6), (1, 2, 3), (0, 4, 9))
((1, 2, 3, 4), (7, 8, 9), (0, 5, 6))
((1, 2, 3, 9), (7, 8, 4), (0, 5, 6))
((7, 8, 4, 9), (1, 2, 3), (0, 5, 6))
((1, 2, 3, 4), (7, 8, 6), (0, 5, 9))
((1, 2, 3, 6), (7, 8, 4), (0, 5, 9))
((7, 8, 4, 6), (1, 2, 3), (0, 5, 9))
((1, 2, 3, 4), (7, 8, 5), (0, 6, 9))
((1, 2, 3, 5), (7, 8, 4), (0, 6, 9))
((7, 8, 4, 5), (1, 2, 3), (0, 6, 9))
((1, 2, 3, 0), (7, 8, 9), (4, 5, 6))
((1, 2, 3, 9), (7, 8, 0), (4, 5, 6))
((7, 8, 0, 9), (1, 2, 3), (4, 5, 6))
((1, 2, 3, 0), (7, 8, 6), (4, 5, 9))
((1, 2, 3, 6), (7, 8, 0), (4, 5, 9))
((7, 8, 0, 6), (1, 2, 3), (4, 5, 9))
((1, 2, 3, 0), (7, 8, 5), (4, 6, 9))
((1, 2, 3, 5), (7, 8, 0), (4, 6, 9))
((7, 8, 0, 5), (1, 2, 3), (4, 6, 9))
((1, 2, 3, 0), (7, 8, 4), (5, 6, 9))
((1, 2, 3, 4), (7, 8, 0), (5, 6, 9))
((7, 8, 0, 4), (1, 2, 3), (5, 6, 9))
((0, 4, 5, 6), (1, 2, 3), (7, 8, 9))
((0, 4, 5, 9), (1, 2, 3), (7, 8, 6))
((0, 4, 6, 9), (1, 2, 3), (7, 8, 5))
((0, 5, 6, 9), (1, 2, 3), (7, 8, 4))
((4, 5, 6, 9), (1, 2, 3), (7, 8, 0))