Java 如何生成给定列表的幂集？

How to generate the power-set of a given List?

提问by Elist

I'm trying to generate a collection of all 2^N - 1 possible combinations of a given List of length N. The collection will map the number of elements in a combination to an ordered list of combinations containing combinations of the specific length. For instance, for the List:

我正在尝试生成给定长度 N 列表的所有 2^N - 1 种可能组合的集合。该集合会将组合中的元素数量映射到包含特定长度组合的有序组合列表。例如，对于列表：

[A, B, C, D]

I want to generate the map:

我想生成地图：

{
    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}]
}

The generated database should maintain the original order (where []represents an ordered series (List), and {}represents an un-ordered group (Set)), and run as fast as possible.

生成的数据库应该保持原来的顺序（其中[]代表有序系列（List），{}代表无序组（Set）），并尽可能快地运行。

I was struggling with some recursive code all day (I know the implementation should be recursive) but couldn't get to the bottom of it.

我整天都在为一些递归代码苦苦挣扎（我知道实现应该是递归的）但无法深入了解它。

Is there a reference I can use/a ready implementation of such algorithm?

是否有我可以使用的参考/此类算法的现成实现？

采纳答案by arshajii

What you're looking for is essentially the power set(minus perhaps the empty set). Guava actually has a method for this: Sets.powerSet(). You can view the source of the Setsclassto see how the method is implemented if you want to write it yourself; you might need to modify it to return a Listinstead of a Setsince you want to preserve order, although this change should not be too drastic. Once you have the power set, it should be trivial to iterate over it and construct the map you want.

您正在寻找的本质上是幂集（可能减去空集）。番石榴实际上有一个方法：Sets.powerSet(). 想自己写的可以查看类的源码，Sets看看方法是怎么实现的；您可能需要修改它以返回 aList而不是 aSet因为您想保留顺序，尽管此更改不应太剧烈。一旦你设置了幂，迭代它并构建你想要的地图应该是微不足道的。

回答by Michael Spector

What you're asking is generating all possible subsets of a set. You can think of it as iterating over all possible binary arrays of size N (the size of your list):

您要问的是生成集合的所有可能子集。您可以将其视为迭代大小为 N（列表的大小）的所有可能的二进制数组：

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

Why is that? The answer is simple: 1 indicates that an element exists in a subset, while 0 indicates that it is absent.

这是为什么？答案很简单：1 表示某个元素存在于子集中，而 0 表示它不存在。

So, the basic algorithm is obvious:

所以，基本算法是显而易见的：

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

Where calculate_subset_based_on_bin_arrayiterates on band sand selects elements from s[current]where b[current] = 1.

Wherecalculate_subset_based_on_bin_array迭代b并s从s[current]where 中选择元素b[current] = 1。

The above will print out all existing subsets. You can adapt this algorithm in order to get the map that you've asked for in your question.

以上将打印出所有现有的子集。您可以调整此算法以获得您在问题中要求的地图。

回答by AntoineP

I test the code proposed by Elist and I found errors.

我测试了 Elist 提出的代码，发现了错误。

Here is a proposed correction : (in the last else of the function getPermutation(), I made two changes)

这是一个建议的更正：（在函数 getPermutation() 的最后一个 else 中，我做了两个更改）

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);
}

}

}

回答by Manjul

Here is a code I have tested to generate all possible combinations out of given array:

这是我测试过的代码，用于从给定数组中生成所有可能的组合：

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;
}
}

回答by alfasin

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);
}

OUTPUT

输出

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

回答by Karthikeyan D

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;
}

This Power set is one of the exercise in the book SICP "Structure and Interpretation of Computer Programming".Every Programmer should read it.

这个Power set是SICP《Structure and Interpretation of Computer Programming》一书中的练习之一，每个程序员都应该读一读。

回答by will.fiset

There are multiple ways to solve this problem, but the easiest way IMHO is to use recursion. Below I have provided the iterativeand recursiveapproaches to solving the problem of generating all the combinations of a set. The general idea for both approaches is to generate the set of indexes which belong to the elements you want to select.

有多种方法可以解决这个问题，但恕我直言，最简单的方法是使用递归。下面我提供了迭代和递归方法来解决生成集合的所有组合的问题。这两种方法的总体思路是生成属于您要选择的元素的索引集。

For the recursive approach, you want to keep track of three pieces of information: A boolean array indicating whether an item was selected or not, the position you're at in your list of items and a variable r tracking the number of elements remaining to select. Then as long as r != 0 (meaning you still need to select r elements to finish this combination) you backtrack selecting an element you have not yet selected and move forward in the array.

对于递归方法，您需要跟踪三条信息：一个布尔数组，指示是否选择了某个项目，您在项目列表中所处的位置，以及一个跟踪剩余元素数量的变量 r选择。然后只要 r != 0（意味着你仍然需要选择 r 个元素来完成这个组合）你回溯选择一个你还没有选择的元素并在数组中向前移动。

The code shown below was taken from my github repo.

下面显示的代码取自我的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    

  }

}

回答by TylerH

OP's solution moved from the question to an answer:

OP 的解决方案从问题变成了答案：

Thanks to previous answers, I came up with the following implementation:

感谢以前的答案，我想出了以下实现：

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);
    }
}