Java - сгенерируйте набор питания для данного списка

Question

Я пытаюсь создать коллекцию из всех возможных возможных комбинаций из 2-х возможных вариантов списка N. Длина коллекции будет отображать количество элементов в комбинации к упорядоченному списку комбинаций, содержащих комбинации определенной длины. Например, для списка:

[A, B, C, D] 

Я хочу, чтобы создать карту:

{ 
    1 -> [{A}, {B}, {C}, {D}] 
    2 -> [{A, B}, {A, C}, {A, D}, {B, C}, {B, D}, {C, D}] 
    3 -> [{A, B, C}, {A, B, D}, {A, C, D}, {B, C, D}] 
    4 -> [{A, B, C, D}] 
} 

Сформированная база данных должна поддерживать первоначальный порядок (где [] представляет собой упорядоченный ряд (List), и {} представляет неупорядоченная группа (Set)) и выполняться как можно быстрее.

Я боролся с каким-то рекурсивным кодом весь день (я знаю, что реализация должна быть рекурсивной), но не могла добраться до нее.

Есть ли ссылка, которую я могу использовать/готовую реализацию такого алгоритма?

UPDATE:

Благодаря предыдущим ответам, я придумал следующую реализацию:

public class OrderedPowerSet<E> { 
    private static final int ELEMENT_LIMIT = 12; 
    private List<E> inputList; 
    public int N; 
    private Map<Integer, List<LinkedHashSet<E>>> map = 
      new HashMap<Integer, List<LinkedHashSet<E>>>(); 

    public OrderedPowerSet(List<E> list) { 
     inputList = list; 
     N = list.size(); 
     if (N > ELEMENT_LIMIT) { 
      throw new RuntimeException(
        "List with more then " + ELEMENT_LIMIT + " elements is too long..."); 
     } 
    } 

    public List<LinkedHashSet<E>> getPermutationsList(int elementCount) { 
     if (elementCount < 1 || elementCount > N) { 
      throw new IndexOutOfBoundsException(
        "Can only generate permutations for a count between 1 to " + N); 
     } 
     if (map.containsKey(elementCount)) { 
      return map.get(elementCount); 
     } 

     ArrayList<LinkedHashSet<E>> list = new ArrayList<LinkedHashSet<E>>(); 

     if (elementCount == N) { 
      list.add(new LinkedHashSet<E>(inputList)); 
     } else if (elementCount == 1) { 
      for (int i = 0 ; i < N ; i++) { 
       LinkedHashSet<E> set = new LinkedHashSet<E>(); 
       set.add(inputList.get(i)); 
       list.add(set); 
      } 
     } else { 
      list = new ArrayList<LinkedHashSet<E>>(); 
      for (int i = 0 ; i <= N - elementCount ; i++) { 
       @SuppressWarnings("unchecked") 
       ArrayList<E> subList = (ArrayList<E>)((ArrayList<E>)inputList).clone(); 
       for (int j = i ; j >= 0 ; j--) { 
        subList.remove(j); 
       } 
       OrderedPowerSet<E> subPowerSet = 
         new OrderedPowerSet<E>(subList); 

       List<LinkedHashSet<E>> pList = 
         subPowerSet.getPermutationsList(elementCount-1); 
       for (LinkedHashSet<E> s : pList) { 
        LinkedHashSet<E> set = new LinkedHashSet<E>(); 
        set.add(inputList.get(i)); 
        set.addAll(s); 
        list.add(set); 
       }    
      } 
     } 

     map.put(elementCount, list); 

     return map.get(elementCount); 
    } 
} 

Я был бы рад получить обратную связь для способов, чтобы улучшить это.

UPDATE 2:

Я установил несколько вопросов в коде и тестировал.

Answer 1

Что вы ищете, это по существу power set (минус, возможно, пустой набор). У Guava есть метод для этого: Sets.powerSet(). Вы можете просмотреть source of the Sets class, чтобы узнать, как реализован метод, если вы хотите написать его самостоятельно; вам может потребоваться изменить его, чтобы вернуть List вместо Set, так как вы хотите сохранить заказ, хотя это изменение не должно быть слишком резким. После того, как у вас установлен уровень мощности, для него нужно тривиально перебирать и строить нужную карту.

Answer 2

То, что вы просите, порождает все возможные подмножества множества. Вы можете думать о нем, как Перебор всех возможных двоичных массивов размером N (размер вашего списка):

000000...000 
000000...001 
000000...010 
000000...011 
etc. 

Почему? Ответ прост: 1 указывает, что элемент существует в подмножестве, а 0 указывает, что он отсутствует.

Итак, основной алгоритм очевиден:

s = [A, B, C, D] 

for i=0 to 2^N-1: 
    b = convert_number_to_bin_array(i) 
    ss = calculate_subset_based_on_bin_array(s, b) 
    print ss 

Где calculate_subset_based_on_bin_array перебирает на b и s и выбирает элементы из s[current] где b[current] = 1.

Вышеприведенное будет распечатывать все существующие подмножества. Вы можете адаптировать этот алгоритм, чтобы получить карту, о которой вы просили в своем вопросе.

Answer 3

Я тестирую код, предложенный Элистом, и я обнаружил ошибки.

Вот предлагаемая поправка: (в последнем ELSE функции getPermutation(), я сделал два изменения)

public class OrderedPowerSet<E> { 
private ArrayList<E> inputList; 
public int N; 
private Map<Integer, List<Set<E>>> map = 
     new HashMap<Integer, List<Set<E>>>(); 

public OrderedPowerSet(ArrayList<E> list) { 
    inputList = list; 
    N = list.size(); 
} 

public List<Set<E>> getPermutationsList(int elementCount) { 
    if (elementCount < 1 || elementCount > N) { 
     throw new IndexOutOfBoundsException(
       "Can only generate permutations for a count between 1 to " + N); 
    } 
    if (map.containsKey(elementCount)) { 
     return map.get(elementCount); 
    } 

    ArrayList<Set<E>> list = new ArrayList<Set<E>>(); 

    if (elementCount == N) { 
     list.add(new HashSet<E>(inputList)); 
    } else if (elementCount == 1) { 
     for (int i = 0 ; i < N ; i++) { 
      Set<E> set = new HashSet<E>(); 
      set.add(inputList.get(i)); 
      list.add(set); 
     } 
    } else { 
     for (int i = 0 ; i < N-elementCount ; i++) { 
      @SuppressWarnings("unchecked") 
      ArrayList<E> subList = (ArrayList<E>)inputList.clone(); // one change 
      subList.remove(0); 
      OrderedPowerSet<E> subPowerSet = 
        new OrderedPowerSet<E>(subList); 
      for (Set<E> s : subPowerSet.getPermutationsList(elementCount-1)) { 
       Set<E> set = new HashSet<E>(); 
       set.add(inputList.get(i)); 
       set.addAll(s); 
       list.add(set); // second change 
      } 

     } 
    } 

    map.put(elementCount, list); 

    return map.get(elementCount); 
} 

}

Answer 4

Вот код, я испытал, чтобы генерировать все возможные комбинации из данного массива:

enter code here 
import java.util.Arrays; 

public class PasswordGen { 
static String[] options = { "a", "b", "c", "d" }; 
static String[] places = new String[options.length]; 
static int count; 

public static void main(String[] args) { 
    // Starting with initial position of a i.e. 0 
    sequence(0, places.clone()); 
} 

private static void sequence(int level, String[] holder) { 
    if (level >= options.length) { 
     // combination complete 
     System.out.println("" + (++count) + " Combination " 
       + Arrays.toString(holder)); 
     return; 
    } 

    String val = options[level]; 
    String[] inrHolder = null; 
    for (int c = 0; c < holder.length; c++) { 
     inrHolder = holder.clone(); 
     if (inrHolder[c] == null) { 
      inrHolder[c] = val; 
      sequence(level + 1, inrHolder.clone()); 
     } 
    } 
    return; 
} 
} 

Answer 5

static Map<Integer, List<LinkedList<Integer>>> powerset = new HashMap<>(); 

public static void main(String[] args) throws IOException { 
    powerset(Arrays.asList(1, 2, 3)); 
    for (Integer key : powerset.keySet()) { 
     System.out.print(key + " -> "); 
     System.out.println(Arrays.toString(powerset.get(key).toArray())); 
    } 
} 

static void powerset(List<Integer> src) { 
    powerset(new LinkedList<>(), src); 
} 

private static void powerset(LinkedList<Integer> prefix, List<Integer> src) { 
    if (src.size() > 0) { 
     prefix = new LinkedList<>(prefix); //create a copy to not modify the orig 
     src = new LinkedList<>(src); //copy 
     Integer curr = src.remove(0); 
     collectResult(prefix, curr); 
     powerset(prefix, src); 
     prefix.add(curr); 
     powerset(prefix, src); 
    } 
} 

private static void collectResult(LinkedList<Integer> prefix, Integer curr) { 
    prefix = new LinkedList<>(prefix); //copy 
    prefix.add(curr); 
    List<LinkedList<Integer>> addTo; 
    if (powerset.get(prefix.size()) == null) { 
     List<LinkedList<Integer>> newList = new LinkedList<>(); 
     addTo = newList; 
    } else { 
     addTo = powerset.get(prefix.size()); 
    } 
    addTo.add(prefix); 
    powerset.put(prefix.size(), addTo); 
} 

ВЫХОД

1 -> [[1], [2], [3]] 
2 -> [[2, 3], [1, 2], [1, 3]] 
3 -> [[1, 2, 3]] 

Answer 6

public static List<String> getCombinationsLists(List<String> elements) 
{ 

    //return list with empty String 
    if(elements.size() == 0){ 
     List<String> allLists = new ArrayList<String>(); 
     allLists.add(""); 
     return allLists ; 
    } 

    String first_ele = elements.remove(0); 
    List<String> rest = getCobminationLists(elements); 
    int restsize = rest.size(); 
    //Mapping the first_ele with each of the rest of the elements. 
    for (int i = 0; i < restsize; i++) { 
     String ele = first_ele + rest.get(i); 
     rest.add(ele); 
    } 

    return rest; 
} 

Этот набор питания является одним из упражнений в книге SICP «Структура и интерпретация компьютерного программирования» .every программист должен читать.

Answer 7

Существует несколько способов решения этой проблемы, но самым простым способом является ИМХО, чтобы использовать рекурсию. Ниже я привел итерационные ошибки и рекурсивный подход к решению проблемы генерации всех комбинаций набора. Общая идея обоих подходов состоит в том, чтобы сгенерировать набор индексов, которые относятся к элементам, которые вы хотите выбрать.

Для рекурсивного подхода вы хотите отслеживать три фрагмента информации: логический массив, указывающий, был ли выбран элемент или нет, позиция, в которой вы находитесь, в своем списке элементов и переменную r, отслеживающую номер элементов, оставшихся для выбора. Затем до тех пор, пока r! = 0 (что означает, что вам еще нужно выбрать r элементов для завершения этой комбинации), вы возвращаетесь к выбору элемента, который вы еще не выбрали, и перемещайтесь вперед в массиве.

Код, показанный ниже, был снят с моего github repo.

/** 
* Here we present two methods (recursive and iterative) of generating all 
* the combinations of a set by choosing only r of n elements. 
* 
* Time Complexity: O(n choose r) 
* 
* @author William Fiset, Micah Stairs 
**/ 

public class Combinations { 

    // This method finds all the combinations of size r in a set 
    public static void combinationsChooseR(int[] set, int r) { 

    if (r < 0) return; 
    if (set == null) return; 

    boolean [] used = new boolean[set.length]; 
    combinations(set, r, 0, used); 

    } 

    // To find all the combinations of size r we need to recurse until we have 
    // selected r elements (aka r = 0), otherwise if r != 0 then we need to select 
    // an element which is found after the position of our last selected element 
    private static void combinations(int[] set, int r, int at, boolean[] used) { 

    final int N = set.length; 

    // If there are more elements left to select than what are available 
    // This is a short circuiting optimization we can take advantage of 
    int elementsLeftToPick = N - at; 
    if (elementsLeftToPick < r) return; 

    // We selected 'r' elements so we found a valid subset! 
    if (r == 0) { 

     System.out.print("{ "); 
     for (int i = 0; i < N; i++) 
     if (used[i]) 
      System.out.print(set[i] + " "); 
     System.out.println("}"); 

    } else { 

     for (int i = at; i < N; i++) { 

     // Try including this element 
     used[i] = true; 
     combinations(set, r - 1, i + 1, used); 

     // Backtrack and try the instance where we did not include this element 
     used[i] = false; 

     } 

    } 

    } 

    // Use this method in combination with a do while loop to generate all the 
    // combinations of a set choose r in a iterative fashion. This method returns 
    // false once the last combination has been generated. 
    // NOTE: Originally the selection needs to be initialized to {0,1,2,3 ... r-1} 
    public static boolean nextCombination(int[] selection, int N, int r) { 
    if (r > N) throw new IllegalArgumentException("r must be <= N"); 
    int i = r - 1; 
    while (selection[i] == N - r + i) 
     if (--i < 0) return false; 
    selection[i]++; 
    for (int j = i + 1; j < r; j++) selection[j] = selection[i] + j - i; 
    return true; 
    } 

    public static void main(String[] args) { 

    // Recursive approach 
    int R = 3; 
    int[] set = {1,2,3,4,5}; 
    combinationsChooseR(set, R); 
    // prints: 
    // { 1 2 3 } 
    // { 1 2 4 } 
    // { 1 2 5 } 
    // { 1 3 4 } 
    // { 1 3 5 } 
    // { 1 4 5 } 
    // { 2 3 4 } 
    // { 2 3 5 } 
    // { 2 4 5 } 
    // { 3 4 5 }  

    // Suppose we want to select all combinations of colors where R = 3 
    String[] colors = {"red", "purple", "green", "yellow", "blue", "pink"}; 
    R = 3; 

    // Initialize the selection to be {0, 1, ... , R-1} 
    int[] selection = { 0, 1, 2 }; 
    do { 

     // Print each combination 
     for (int index : selection) 
     System.out.print(colors[index] + " "); 
     System.out.println(); 

    } while(nextCombination(selection, colors.length, R)); 
    // prints: 
    // red purple green 
    // red purple yellow 
    // red purple blue 
    // red purple pink 
    // red green yellow 
    // red green blue 
    // red green pink 
    // red yellow blue 
    // red yellow pink 
    // red blue pink 
    // purple green yellow 
    // purple green blue 
    // purple green pink 
    // purple yellow blue 
    // purple yellow pink 
    // purple blue pink 
    // green yellow blue 
    // green yellow pink 
    // green blue pink 
    // yellow blue pink  

    } 

}