# Java – 生成给定列表的幂集

``[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}] }` `

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

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

` `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` `

` `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]]` `

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

` `/** * 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 } }` `

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