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

package com.techiekunal.examples.datastructure;

import java.util.*;

/**
 * Finding all combinations from array of Numbers say {1,2,3,4} We want to make
 * combination of r numbers, So if r=3 then combinations will be {1,2,3},
 * {1,3,2}, {2,3,1}..etc
 * 
 * @author Kunal.Saxena
 *
 */
public class AllCombinationsFromNumbers {

 private final static List<List<Integer>> combList = new ArrayList<>();

 public static void findAllCombinations(int[] arr, int r) {

  // Queue for storing all paths
  Queue<List<Integer>> paths = new LinkedList<>();

  // Initialize queue with array elements
  for (int i : arr) {
   List<Integer> list = new LinkedList<>();
   list.add(i);
   paths.add(list);
   list = null;
  }

  while (!paths.isEmpty()) {
  
   // dequeue a path 
   List<Integer> path = paths.remove();
   
   // Loop through all array elements
   for (int i : arr) {
    if (!path.contains(i)) {
     if (path.size() == r) {
      combList.add(path);
      continue;
     }
     List<Integer> newPath = new LinkedList<>(path);
     newPath.add(i);
     paths.add(newPath);
     newPath = null;
    }
   }
  }
 }

 public static void main(String[] args) {

  // Input array and r
  int[] arr = { 1, 2, 3, 4 };
  int r = 3;
  
  // Find all combinations of r elements
  findAllCombinations(arr, r);

  // print all combinations
  System.out.println("All possible combinations are :-");
  for (List<Integer> arrEle : combList) {
   System.out.println(arrEle);
  }
 }

}

Output

All possible combinations of 3 are:-

Yeh... you made it.

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.

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 :-)

#Combinatorics #DataStructure #Graph #Tree #BFS #Algorithm #KunalSaxena