我正在尝试生成一个给定长度为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）），并且运行速度应尽可能快。
我一整天都在苦苦挣扎于一些递归代码中（我知道实现应该是递归的），但没能找到根源。
是否有参考资料/已有的此类算法的实现？
Sets.powerSet()。如果您想自己编写代码，请查看 Sets类的源代码 以了解该方法的实现方式；您可能需要修改它以返回 List 而不是 Set，因为您想保留顺序，尽管这种更改不应该太大。一旦您获得了幂集，遍历它并构建所需的映射应该是微不足道的。您所要求的是生成集合的所有可能子集。可以将其视为遍历大小为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的元素。
以上代码将打印出所有现有的子集。您可以调整此算法以获得您在问题中所要求的映射。
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]]
这里是我测试过的一个用于生成给定数组中所有可能组合的代码：
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;
}
}
[a, b] 和 [b, a] 不会同时出现在输出中（因为 a 在输入中在 b 之前，而 [b, a] 不保持原始顺序）。 - Elistpublic 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 = getCombinationsLists(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;
}
这个 Power set 是 SICP（《计算机程序的构造和解释》）书中的一个练习。每个程序员都应该阅读它。
/**
* 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
}
}
我测试了Elist提出的代码，发现了错误。
这里是一个建议的更正：（在函数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);
}
}
楼主的解决方案从问题移动到了答案中：
感谢之前的回答，我想出了以下实现方法：
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);
}
}
i和大小为N-i的列表。考虑将列表分成两个子集，并将每个子集添加到其中一个结果列表中。 - Patricia Shanahan