Java – 生成给定列表的幂集
我试图生成一个给定长度为N的列表的所有2 ^ N-1个可能组合的集合。该集合将组合元素的数目映射到包含特定长度的组合的有序列表。 例如，对于列表：
[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 ）），并尽可能快地运行。
我一整天都在忙于一些recursion代码（我知道这个实现应该是recursion的），但是却无法实现。
有没有我可以使用/一个准备好的实现这样的algorithm的参考？
更新：
感谢之前的答案，我想出了以下实现：
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); } }
我会很高兴得到一些反馈，以改善这种方式。
更新2：
我在代码中修复了一些问题并对其进行了testing。
你正在寻找的是本质上的权力集合 （减去空集）。 番石榴实际上有一个这样的方法： Sets.powerSet() 。 您可以查看Sets类的源代码，以查看如果要自己编写该方法的方法; 你可能需要修改它来返回一个List而不是一个Set因为你想保持顺序，尽pipe这个改变不应该太激烈。 一旦你有权力设置，它应该是微不足道的迭代它，并构build你想要的地图。
你所要求的是生成一个集合的所有可能的子集。 你可以把它想象成遍历所有可能的大小为N的二进制数组（你的列表的大小）：
000000...000 000000...001 000000...010 000000...011 etc.
这是为什么？ 答案很简单：1表示元素中存在元素，0表示不存在。
所以，基本的algorithm是显而易见的：
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上迭代，并从b[current] = 1 s[current]中select元素。
以上将打印出所有现有的子集。 你可以调整这个algorithm来获得你在问题中要求的地图。
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]]
这里是我已经testing的代码来生成给定数组的所有可能的组合：
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 ie 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; } }
有多种方法来解决这个问题，但恕我直言最简单的方法是使用recursion。 下面我提供了迭代和recursion的方法来解决生成一个集合的所有组合的问题。 这两种方法的总体思路是生成属于您要select的元素的索引集。
对于recursion方法，您需要跟踪三条信息：一个指示项目是否被选中的布尔数组，您在项目列表中的位置以及一个variablesr，用于跟踪剩余的元素数量select。 然后只要r！= 0（意味着你仍然需要selectr个元素来完成这个组合），你回溯select一个你尚未select的元素，并向前移动数组。
下面显示的代码是从我的github回购 。
/** * 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 } }
我testing了Elist提出的代码，发现错误。
这是一个build议的修正：（在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); }
}
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“计算机编程的结构与解释”一书中的练习题之一，每个程序员都应该阅读。
