Finding All Possible Combinations with Graph

 

Recently I came across a puzzle where finding all possible combination was sub-problem, an important piece. In that puzzle, I need to find all combinations and then reject combinations which do not fit puzzle conditions.

 

Use case

Many a time you come across a scenario where all possibilities are required and then you eliminate possibilities one by one. In the end, you left with few choices which can probably be answers to your problem.

Graph and BFS helped me find all possible combinations, a real use case. Let’s see how:-

I have input array arr = { 1, 2, 3, 4 } and you want to find all combinations of 3 elements like {1,2,3}, {1,3,2}, {2,3,1}… etc. It is like “n choose k” problem.

Using Breadth First Search we can solve it like:-

  • Insert {1}, {2}, {3}, {4} as graph nodes.
  • Create next level appending one more element from remaining below each of them, as shown in the diagram below. Example will be 12, 13 and 14… etc
  • Create next level by adding one more element from remaining similar to step 2.
  • Repeat 2 and 3 until you reach desired element count(3 in our case).

This way using BFS, we can generate all possible combinations. Simple and easy.. 🙂

Implementation

[crayon-5bf068dac4224888086384/]

 

Output

All possible combinations of 3 are:-

Complexity

I have analyzed my solution’s complexity as n^c, Polynomial time. In this n is no of elements to choose from and c is constant.

Shortcomings of this solution

As per problem statement, I need to find all possible combinations of 3 elements. But looking at graph image, you will notice that I am also getting the combination of single and double elements for free.

Read Also:  9 Best PPD Pay Per Download Sites With or Without Survey

So is there any way to get combinations of 3 elements directly?

Can this be solved with less complexity?

Please put your views, suggestions, and solutions in comments below.

Cheers 🙂

Leave a Reply

Your email address will not be published. Required fields are marked *