如何使用Java递归获取所有组合？

Question

在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>的列表。

- kami

Answer 1

我几年前遇到了这个问题。我通过使用一个“里程表”来迭代结果列表来解决它。

里程表中的轮子数是输入集的数量。每个轮子上的数字是相应集合的成员。要获取下一个排列，请滚动最右边的里程表轮子。如果它已经完全转过一圈，请向左滚动一个轮子，以此类推。

例如：

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

Answer 2

你不需要使用递归。只需使用集合列表的大小以及每个集合的大小即可。您可以保持结果开放以添加更多元素，以防将来需要混合更多集合。

- user4933750

Answer 3

总组合数等于各候选集大小的乘积。每个结果集的大小等于候选集的数量。

解决方案不需要递归，只需遍历每个候选集。在此示例中，第一个集合有两个值，1和2。前6个结果集（其中一半）将第一个值设为1。下一个一半设置为6。

进行下一个候选集时，有两个值，3和4。但是这次，要交替以3个为一组分配它们，而不是6。因此，前3个结果集获取3，下一个3个结果集获得4，下一个3个结果集获得3，以此类推。

下一个候选集有三个值：5、6和7。现在要轮换为每个结果集分配哪个值（每个1个分配轮换）。如果有更多的候选集或其中的值量不同，则在旋转到下一个值之前分配的数量会改变。但您可以通过编程找到这个量。

- ThatOneCloud

Answer 4

感谢大家的回复。

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

- kami

Answer 5

这里还有另一个版本（正如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);
        }
    }
}

- kami