0

I have a path through a complete directed acyclic graph stored as a List(of nodes). Part of an algorithm I am implementing for propagating evidence through the graph requires that I sum all the contributions from all combinations of the path where nodes in the path between the first and and last may or may not contribute.

As an example, consider the path {r1, r2, ¬r3, r4, r5} where ¬ denotes that the node (r3) is not in the path. Therefore the nodes between the first and last nodes that are in the path are r2 and r4. The set of all combinations of r2 and r4 are:

{[r2,r4], [r2,¬r4], [¬r2,r4], [¬r2,¬r4]}

So, given an original List(of Nodes)

{r2, r4}

I would like to return a List(of List(of nodes))

{[r2,r4], [r2], [r4]}

I'm completely stumped as to how to implement this part of the algorithm, so any help would be gatefully received.

The algorithm can be found in this paper: http://arxiv.org/ftp/cs/papers/0305/0305014.pdf

hivert
  • 10,579
  • 3
  • 31
  • 56
MLD
  • 25
  • 9
  • If I understand correctly, you have a set which is listed in a specific order `[r2, r4]` and you want to enumerate all non empty subsets, listing them in the same order. Am I right ? If it's the case then they are plenty of description of such a algorithm out there (eg: http://stackoverflow.com/questions/4640034/calculating-all-of-the-subsets-of-a-set-of-numbers). – hivert Mar 21 '14 at 14:37
  • You're absolutely right. I've been so focused on looking at the problem from one direction I missed the obvious thing which is that I just need to find the power set. As you say, there are many algorithms for that. Thanks – MLD Mar 21 '14 at 15:26
  • Then I'll vote your question to be removed as a duplicate. – hivert Mar 21 '14 at 15:29

0 Answers0