在Java中,获取多个候选集合中所有元素的组合的最佳途径是什么?
通常情况下,候选集合的数量是未定义的,因此递归解决方案似乎非常适合这个任务。以给定的候选集合为例。
[1,2]
[3,4]
[5,6,7]
应该获得12种组合:
[1,3,5] [2,3,5]
[1,4,5] [2,4,5]
[1,3,6] [2,3,6]
[1,4,6] [2,4,6]
[1,3,7] [2,3,7]
[1,4,7] [2,4,7]
候选集被表示为一个类型为List>的列表。
Wheel 0 values: [1,2]
Wheel 1 values: [3,4]
Wheel 2 values: [5,6,7]
从里程表读数(1,3,5)开始。前进到(1,3,6),(1,3,7)。然后将下一个轮子也转动,到(1,4,5),(1,4,6)和(1,4,7)。继续进行。
里程表轮子作为索引
或者,您可以将轮子表示为相应列表中的索引。
Wheel 0 values: [0,1]
Wheel 1 values: [0,1]
Wheel 2 values: [0,1,2]
从里程表读数(0,0,0)开始。继续到(0,0,1),(0,0,2)。然后转动下一个轮子,到(0,1,0),(0,1,1)和(0,1,2)。继续进行。对于每个读数,请使用里程表轮子读数作为索引来将其翻译到结果列表中。
将里程表轮子表示为迭代器
作为另一种选择,您可以将轮子表示为输入集合的迭代器。这比前面两种方法更通用。即使无法通过索引访问输入集合,它也可以工作。而且它是可扩展的。这是我几年前使用的方法。
感谢大家的回复。
Andy Thomas,您提出的里程表想法非常有趣。稍后我会尝试一下。目前我已经按照ThatOneCloud的建议实现了它。
这是我得到的结果(适用于整数项目;如果需要可以泛化):
public List<List<Integer>> makeCombinations(List<List<Integer>> candidates) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
// calculate result size
int size = 1;
for (List<Integer> candidateSet : candidates)
size *= candidateSet.size();
// make result
for (int i = 0; i < size; i++)
result.add(new ArrayList<Integer>());
// fill result
int pos = 1;
for (List<Integer> candidateSet : candidates)
fillPosition(candidateSet, result, countRepeats(candidates, pos++));
// return
return result;
}
public int countRepeats(List<List<Integer>> candidates, int pos) {
int repeats = 1;
for (int i = pos; i < candidates.size(); i++)
repeats *= candidates.get(i).size();
return repeats;
}
public void fillPosition( List<Integer> candidateSet,
List<List<Integer>> result,
int repeats) {
int idx = 0;
while (idx < result.size()) {
for (int item : candidateSet) {
for (int i = 0; i < repeats; i++) {
result.get(idx++).add(item);
}
}
}
}
这里还有另一个版本(正如Andy Thomas所建议的那样,使用Odometer)
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class Odometer<T> implements Iterable<List<T>> {
private class Wheel {
List<T> values;
int idx = 0;
/**
* Create an odometer wheel from list of values
* @param v
*/
protected Wheel (List<T> v) {
if (v == null) throw new NullPointerException("can't create an instance of Wheel.class with null values");
if (v.isEmpty()) throw new IllegalArgumentException("can't create an instance of Wheel.class with no values");
this.values = v;
}
/**
* Get wheel value
* @return
*/
protected T value() {
return values.get(idx);
}
/**
* switch an odometer wheel one step
* @return TRUE - if a wheel have made full cycle and have switched to first item
*/
protected boolean next() {
if (idx >= values.size() - 1) {
idx = 0;
return true;
} else {
idx++;
return false;
}
}
}
/**
* list of wheels
*/
private List<Wheel> wheels = new ArrayList<Wheel>();
/**
* Create an odometer from several lists of values
* (each List<T> is a list of values for one odometer wheel)
* @param values
*/
public Odometer(List<List<T>> values) {
for (List<T> v : values)
wheels.add(new Wheel(v));
}
/**
* Get odometer value
* @return
*/
public List<T> get() {
List<T> result = new ArrayList<T>();
for (Wheel wheel : wheels) {
result.add(wheel.value());
}
return result;
}
/**
* Switch to next value
* @return TRUE if full cycle is finished
*/
public boolean next() {
for (int i = wheels.size() - 1; i >= 0; i--)
if (!wheels.get(i).next()) return false;
return true;
}
/**
* Reset odometer
*/
public void reset() {
for (Wheel wheel : wheels)
wheel.idx = 0;
}
/**
* Iterator
*/
@Override
public Iterator<List<T>> iterator() {
reset();
Iterator<List<T>> it = new Iterator<List<T>>() {
private boolean last = false;
@Override
public boolean hasNext() {
return !last;
}
@Override
public List<T> next() {
List<T> result = get();
last = Odometer.this.next();
return result;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
};
return it;
}
public static void main(String [] args) {
List<Integer> l1 = new ArrayList<Integer>(); l1.add(1); l1.add(2);
List<Integer> l2 = new ArrayList<Integer>(); l2.add(3); l2.add(4); l2.add(5);
List<Integer> l3 = new ArrayList<Integer>(); l3.add(6); l3.add(7);
List<List<Integer>> list = new ArrayList<List<Integer>>(); list.add(l1); list.add(l2); list.add(l3);
Odometer<Integer> odometer = new Odometer<Integer>(list);
for (List<Integer> value : odometer) {
System.out.println(value);
}
}
}