按升序大小顺序的一组整数的k组合
编程挑战：给定一组整数[1,2,3,4,5]，我想在Java中以升序大小顺序生成所有可能的k组合; 例如
[1], [2], [3], [4], [5], [1, 2], [1, 3] ... [1, 2, 3, 4, 5] 生成一个生成所有组合然后对它们进行排序的递归解决方案相当容易，但我想有一种更有效的方法可以消除对额外排序的需求。
只需进行迭代深化搜索 。
void comb(int... items) { Arrays.sort(items); for (int k = 1; k <= items.length; k++) { kcomb(items, 0, k, new int[k]); } } public void kcomb(int[] items, int n, int k, int[] arr) { if (k == 0) { System.out.println(Arrays.toString(arr)); } else { for (int i = n; i <= items.length - k; i++) { arr[arr.length - k] = items[i]; kcomb(items, i + 1, k - 1, arr); } } }
然后打电话给comb(10,20,30) 。 它将打印：
[10] [20] [30] [10, 20] [10, 30] [20, 30] [10, 20, 30]
有两种方法可以解释“提升”要求。 更宽松的解释是“在每个列表中，整数应按升序出现”。 更严格的解释是“需要按顺序列出清单”。 我猜这就是你想要的那个，但我想出了一个简单的迭代方法来满足更宽松的要求。
对于n项，计算所有n位数。 如果与项目对应的位在那里，则它在结果列表中。
public static void displaySubsets(List sortedInts) { int n=sortedInts.size(); long combinations = 1 << n; for (int setNumber=0; setNumber aResult = new ArrayList (); for (int digit=0; digit 0) { aResult.add(sortedInts.get(digit)); } } System.out.println(aResult.toString()+", "); } }
1,2,3,4,5的结果是：[]，[1]，[2]，[1,2]，[3]，[1,3]，[2,3]，[1,2] ，3]，[4]，[1,4]，[2,4]，[1,2,4]，[3,4]，[1,3,4]，[2,3,4]， [1,2,3,4]，[5]，[1,5]，[2,5]，[1,2,5]，[3,5]，[1,3,5]，[2 ，3,5]，[1,2,3,5]，[4,5]，[1,4,5]，[2,4,5]，[1,2,4,5]，[3] ，4,5]，[1,3,4,5]，[2,3,4,5]，[1,2,3,4,5]
是的，我知道，我因为不使用递归而失去了分数。
我正在考虑更多，并意识到可以使用动态编程方法有效地完成它。 下面是我生成的迭代解决方案，它使用Queue来保持状态（尽管可以使用Stack代替）。
我相信这比递归迭代深化搜索更有效，因为它不会涉及在生成期间重新访问现有状态; 它会记住使用队列的先前状态，并使用这些状态生成连续状态。
绩效比较
Algorithm | 5 elems | 10 elems | 20 elems -------------------------------------------------------------------------- Recursive (#recursions) | 62 | 2046 | 2097150 Dynamic (#loop iterations) | 32 | 1024 | 1048576
码
public class Test { private static class Pair { private final List result; private final int index; private Pair(List result, int index) { this.result = result; this.index = index; } public List getResult() { return result; } public int getIndex() { return index; } } public static void main(String[] args) { List items = Arrays.asList(1, 2, 3, 4, 5); foo(items); } private static void foo(List items) { Queue queue = new LinkedList (); queue.add(new Pair(Collections.emptyList(), 0)); while (!queue.isEmpty()) { Pair pair = queue.poll(); System.err.println(pair.getResult()); if (pair.getResult().size() < items.size()) { for (int i=pair.getIndex(); i copy = new LinkedList (pair.getResult()); copy.add(items.get(i)); queue.add(new Pair(copy, i + 1)); } } } } }
生成组合比排序花费的时间长，并且在给定n*log(n)排序时间的情况下对100,000个数字进行排序不需要那么长时间。 你是预先优化的。 这是不好的。