Monday, 1 August 2016

List all possible combinations

First attempt:
      public static <T> List<List<T>> allCombination(List<T> list, int n){  
           List<List<T>> result = new ArrayList<>();  
           if (n > 0){  
                for (int i=0; i<list.size(); i++){  
                     List<T> sublist = list.subList(i+1, list.size());  
                     if (sublist.size() >= n-1){  
                          List<List<T>> subAllCombination = allCombination(sublist, n-1);  
                          if (subAllCombination.size() > 0){  
                               for (List<T> strList : subAllCombination){  
                                    List<T> entry = new ArrayList<>();  
                                    entry.add(list.get(i));  
                                    entry.addAll(strList);  
                                    result.add(entry);  
                               }       
                          }else{  
                               List<T> entry = new ArrayList<>();  
                               entry.add(list.get(i));  
                               result.add(entry);  
                          }       
                     }  
                }  
           }  
           return result;  
      }  

Second attempt:
      public static <T> List<List<T>> allCombo(List<T> list, int n){  
           List<List<T>> result = new ArrayList<>();  
           push(list, n, new ArrayList<T>(), result);  
           return result;  
      }  
      private static <T> void push(List<T> list, int n, List<T> items, List<List<T>> result) {  
           if (n == 0){  
                result.add(new ArrayList<>(items));  
                return;  
           }  
           for (int i=0; i<list.size(); i++){  
                items.add(list.get(i));  
                push(list.subList(i+1, list.size()), n-1, items, result);       
                items.remove(items.size()-1);  
           }       
      }  

Testing code:
      public static void main(String[] args){  
           List<String> list = Arrays.asList("A","B","C","D","E");  
           for (List<String> str : allCombo(list, 3)){  
                System.out.println(str);  
           }  
      }  

Result:

[A, B, C]
[A, B, D]
[A, B, E]
[A, C, D]
[A, C, E]
[A, D, E]
[B, C, D]
[B, C, E]
[B, D, E]
[C, D, E]

No comments:

Post a Comment