StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>You second constraint means you want maximal combinations, i.e. all the combinations with the length equal to the largest combination.</p> <p>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.</p> <p>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.</p> <p>For example, your "c" structure, will look like:</p> <pre><code>c[i][j] = [b_k0, ...] --> means c_i has b_k0, ... as branches that connect to root r_j) </code></pre> <p>For the example you provided:</p> <pre><code>c[0][0] = [0] c[0][1] = [] c[1][0] = [1] c[1][1] = [2] c[2][0] = [] c[2][1] = [3, 4] </code></pre> <p>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".</p> <p>Here is the code (I entered your sample data at the top for testing sake):</p> <pre><code>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 </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload