Generating combinations of edges under a certain condition
I have edges of a graph represented as (node_from, node_to).
I want to efficiently generate all combinations of 2 edges of the form (0,x), where 0 is node 0 in my graph - in combination with all combinations of 2 edges of the form (x,n), where n is the "final node" (arbitrary i know) in my graph. I already have all the edges sitting around in a set, or also it is the case that every node contains an edge to every other node (so you could directly iterate through the range to generate combinations, for example).
A valid combination could be
And, just to make it clear, I want combinations not permutations. I don't want to re-use the same group.
I am generally pretty good at figuring this stuff out, but I am having a bit of trouble with this one.
EDIT : updated to acommodate the requirements of "only two start/end edges"
I'm not sure what interface you have in mind, but from what I understood it looks like you can use filter() to select a subset of edges that "start in 0 " or "end in n ".
>>> edges = [(0,1), (0,5), (0,2), (5,3), (2,9), (4,6), (6,9), (3,9), (0,9)]
>>> edges_start = filter(lambda e: e[0] == 0, edges)
>>> edges_end = filter(lambda e: e[1] == 9, edges)
>>> edges_end
[(2, 9), (6, 9), (3, 9), (0, 9)]
>>> edges_start
[(0, 1), (0, 5), (0, 2), (0, 9)]
Now you can use itertools.combinations() to generate all possible pairs from each of the lists. Here's an example:
>>> import itertools
>>> list(itertools.combinations(edges_start, 2))
[((0, 1), (0, 5)), ((0, 1), (0, 2)), ((0, 1), (0, 9)), ((0, 5), (0, 2)), ((0, 5), (0, 9)), ((0, 2), (0, 9))]
Now you can plug in itertools.product() to generate all combinations of "pair from one list" and "pair from other list":
>>> edges_start_pairs = list(itertools.combinations(edges_start, 2))
>>> edges_end_pairs = list(itertools.combinations(edges_end, 2))
>>> pairs = list(itertools.product(edges_start_pairs, edges_end_pairs))
That's it! You can "flatten" the data structure if you like, but this is optional:
>>> flat_pairs = [list(p[0]+p[1]) for p in pairs]
Now let's pretty-print the results:
>>> from pprint import pprint
>>> pprint(flat_pairs)
[[(0, 1), (0, 5), (2, 9), (6, 9)],
[(0, 1), (0, 5), (2, 9), (3, 9)],
[(0, 1), (0, 5), (2, 9), (0, 9)],
[(0, 1), (0, 5), (6, 9), (3, 9)],
[(0, 1), (0, 5), (6, 9), (0, 9)],
[(0, 1), (0, 5), (3, 9), (0, 9)],
[(0, 1), (0, 2), (2, 9), (6, 9)],
[(0, 1), (0, 2), (2, 9), (3, 9)],
[(0, 1), (0, 2), (2, 9), (0, 9)],
[(0, 1), (0, 2), (6, 9), (3, 9)],
[(0, 1), (0, 2), (6, 9), (0, 9)],
[(0, 1), (0, 2), (3, 9), (0, 9)],
[(0, 1), (0, 9), (2, 9), (6, 9)],
[(0, 1), (0, 9), (2, 9), (3, 9)],
[(0, 1), (0, 9), (2, 9), (0, 9)],
[(0, 1), (0, 9), (6, 9), (3, 9)],
[(0, 1), (0, 9), (6, 9), (0, 9)],
[(0, 1), (0, 9), (3, 9), (0, 9)],
[(0, 5), (0, 2), (2, 9), (6, 9)],
[(0, 5), (0, 2), (2, 9), (3, 9)],
[(0, 5), (0, 2), (2, 9), (0, 9)],
[(0, 5), (0, 2), (6, 9), (3, 9)],
[(0, 5), (0, 2), (6, 9), (0, 9)],
[(0, 5), (0, 2), (3, 9), (0, 9)],
[(0, 5), (0, 9), (2, 9), (6, 9)],
[(0, 5), (0, 9), (2, 9), (3, 9)],
[(0, 5), (0, 9), (2, 9), (0, 9)],
[(0, 5), (0, 9), (6, 9), (3, 9)],
[(0, 5), (0, 9), (6, 9), (0, 9)],
[(0, 5), (0, 9), (3, 9), (0, 9)],
[(0, 2), (0, 9), (2, 9), (6, 9)],
[(0, 2), (0, 9), (2, 9), (3, 9)],
[(0, 2), (0, 9), (2, 9), (0, 9)],
[(0, 2), (0, 9), (6, 9), (3, 9)],
[(0, 2), (0, 9), (6, 9), (0, 9)],
[(0, 2), (0, 9), (3, 9), (0, 9)]]
上一篇: 忽略使用Automapper映射一个属性
下一篇: 在特定条件下生成边的组合