Python Combinatorics, part 2

Question

This is a follow-up question to Combinatorics in Python

I have a tree or directed acyclic graph if you will with a structure as:

Where r are root nodes, p are parent nodes, c are child nodes and b are hypothetical branches. The root nodes are not directly linked to the parent nodes, it is only a reference.

I am intressted in finding all the combinations of branches under the constraints:

1. A child can be shared by any number of parent nodes given that these parent nodes do not share root node.
2. A valid combination should not be a subset of another combination

In this example only two valid combinations are possible under the constraints:

combo[0] = [b[0], b[1], b[2], b[3]]
combo[1] = [b[0], b[1], b[2], b[4]]

The data structure is such as b is a list of branch objects, which have properties r, c and p, e.g.:

b[3].r = 1
b[3].p = 3
b[3].c = 2

Answer 1

This problem can be solved in Python easily and elegantly, because there is a module called "itertools".

Lets say we have objects of type HypotheticalBranch, which have attributes r, p and c. Just as you described it in your post:

class HypotheticalBranch(object):
  def __init__(self, r, p, c):
    self.r=r
    self.p=p
    self.c=c
  def __repr__(self):
    return "HypotheticalBranch(%d,%d,%d)" % (self.r,self.p,self.c)

Your set of hypothetical branches is thus

b=[ HypotheticalBranch(0,0,0),
  HypotheticalBranch(0,1,1),
  HypotheticalBranch(1,2,1),
  HypotheticalBranch(1,3,2),
  HypotheticalBranch(1,4,2) ]

The magical function that returns a list of all possible branch combos could be written like so:

import collections, itertools

def get_combos(branches):
  rc=collections.defaultdict(list)
  for b in branches:
    rc[b.r,b.c].append(b)
  return itertools.product(*rc.values())

To be precise, this function returns an iterator. Get the list by iterating over it. These four lines of code will print out all possible combos:

for combo in get_combos(b):
  print "Combo:"
  for branch in combo:
    print "  %r" % (branch,)

The output of this programme is:

Combo:
  HypotheticalBranch(0,1,1)
  HypotheticalBranch(1,3,2)
  HypotheticalBranch(0,0,0)
  HypotheticalBranch(1,2,1)
Combo:
  HypotheticalBranch(0,1,1)
  HypotheticalBranch(1,4,2)
  HypotheticalBranch(0,0,0)
  HypotheticalBranch(1,2,1)

...which is just what you wanted.

So what does the script do? It creates a list of all hypothetical branches for each combination (root node, child node). And then it yields the product of these lists, i.e. all possible combinations of one item from each of the lists.

I hope I got what you actually wanted.

Answer 2

You second constraint means you want maximal combinations, i.e. all the combinations with the length equal to the largest combination.

I would approach this by first traversing the "b" structure and creating a structure, named "c", to store all branches coming to each child node and categorized by the root node that comes to it.

Then to construct combinations for output, for each child you can include one entry from each root set that is not empty. The order (execution time) of the algorithm will be the order of the output, which is the best you can get.

For example, your "c" structure, will look like:

c[i][j] = [b_k0, ...]  
--> means c_i has b_k0, ... as branches that connect to root r_j)

For the example you provided:

c[0][0] = [0]
c[0][1] = []
c[1][0] = [1]
c[1][1] = [2]
c[2][0] = []
c[2][1] = [3, 4]

It should be fairly easy to code it using this approach. You just need to iterate over all branches "b" and fill the data structure for "c". Then write a small recursive function that goes through all items inside "c".

Here is the code (I entered your sample data at the top for testing sake):

class Branch:
  def __init__(self, r, p, c):
    self.r = r
    self.p = p
    self.c = c

b = [
    Branch(0, 0, 0),
    Branch(0, 1, 1),
    Branch(1, 2, 1),
    Branch(1, 3, 2),
    Branch(1, 4, 2)
    ]

total_b = 5   # Number of branches
total_c = 3   # Number of child nodes
total_r = 2   # Number of roots

c = []
for i in range(total_c):
  c.append([])
  for j in range(total_r):
    c[i].append([])

for k in range(total_b):
  c[b[k].c][b[k].r].append(k)

combos = []
def list_combos(n_c, n_r, curr):
  if n_c == total_c:
    combos.append(curr)
  elif n_r == total_r:
    list_combos(n_c+1, 0, curr)
  elif c[n_c][n_r]:
      for k in c[n_c][n_r]:
        list_combos(n_c, n_r+1, curr + [b[k]])
  else:
    list_combos(n_c, n_r+1, curr)

list_combos(0, 0, [])

print combos