Finding all possible combinations - BFS
https://www.linkedin.com/pulse/finding-all-possible-combinations-bfs-kunal-saxena/
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> combList = new ArrayList<>(); //list of list as result
public static void findAllCombinations(int[] arr, int r) {
// Queue for storing all paths
Queue> paths = new LinkedList<>(); //store partial path
// Initialize queue with array elements
//e.g [1,2,3], starts with [1], [2], [3]
for (int i : arr) {
List list = new LinkedList<>();
list.add(i);
paths.add(list);
list = null;
}
while (!paths.isEmpty()) {
// dequeue a path
List 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 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 arrEle : combList) {
System.out.println(arrEle);
}
}
}
posted by iamjerryyeung at
3:51 PM
|
0 comments
