получить все возможные разделы набора

Question

В java У меня есть набор, где я хочу получить все возможные комбинации подмножеств, которые их объединение делает основной набор. (Разбиение набора) , например: множество = {1,2,3}

результат должен быть:

{ {{1,2,3},{}} , {{1},{2,3}} , {{1,2},{3}} , {{1,3},{2}}, {{1},{2},{3}}} 

код до сих пор:

public static <T> Set<Set<T>> powerSet(Set<T> myset) { 
     Set<Set<T>> pset = new HashSet<Set<T>>(); 
     if (myset.isEmpty()) { 
      pset.add(new HashSet<T>()); 
      return pset; 
     } 
     List<T> list = new ArrayList<T>(myset); 
     T head = list.get(0); 
     Set<T> rest = new HashSet<T>(list.subList(1, list.size())); 
     for (Set<T> set : powerSet(rest)) { 
      Set<T> newSet = new HashSet<T>(); 
      newSet.add(head); 
      newSet.addAll(set); 
      pset.add(newSet); 
      pset.add(set); 
     } 

     return pset; 
    } 

, который выводит Powerset от массива:

[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]] 

Answer 1

Самое простое решение - использование рекурсии о количестве элементов вашего набора: Создайте функцию, которая строит все разделы набора n-элементов. Для n + 1 элементов вы либо добавляете новый элемент к существующим наборам разделов, либо помещаете его в свой собственный набор.