代码之家 › 专栏 › 技术社区 › Adamski

一组整数按升序的k-组合

algorithm java

Adamski · 技术社区 · 14 年前

编程挑战:给定一组整数[1,2,3,4,5],我想在 升序大小顺序 在里面爪哇例如

[1], [2], [3], [4], [5], [1, 2], [1, 3] ... [1, 2, 3, 4, 5]

生成一个递归的解决方案来生成所有的组合并在之后对它们进行排序是相当容易的,但是我认为有一种更有效的方法可以消除对额外排序的需要。

4 回复 | 直到 14 年前

polygenelubricants 14 年前

只要做 iterative deepening search .

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]

John 14 年前

解释“升序”需求有两种方法。更宽松的解释是“在每个列表中,整数应该以升序出现”。更严格的解释是“名单需要按顺序排列”。我想这就是你想要的,但是我想出了一个简单的迭代方法来满足更宽松的需求。

对于n个项目,通过所有n位数字进行计数。如果一个项目对应的位在那里,那么它就在结果列表中。

public static void displaySubsets(List<Integer> sortedInts) {
    int n=sortedInts.size();
    long combinations = 1 << n;
    for (int setNumber=0; setNumber<combinations; setNumber++) {
      List<Integer> aResult = new ArrayList<Integer>();
      for (int digit=0; digit<n; digit++) {
        if ((setNumber & (1<<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]

是的,我知道,我因为不使用递归而失分。

Adamski 14 年前

我在考虑这个问题,并意识到它可以有效地使用动态编程方法。下面是我给出的迭代解,它使用 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<Integer> result;
        private final int index;

        private Pair(List<Integer> result, int index) {
            this.result = result;
            this.index = index;
        }

        public List<Integer> getResult() {
            return result;
        }

        public int getIndex() {
            return index;
        }
    }

    public static void main(String[] args) {
        List<Integer> items = Arrays.asList(1, 2, 3, 4, 5);
        foo(items);
    }

    private static void foo(List<Integer> items) {
        Queue<Pair> queue = new LinkedList<Pair>();
        queue.add(new Pair(Collections.<Integer>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<items.size(); ++i) {
                    List<Integer> copy = new LinkedList<Integer>(pair.getResult());
                    copy.add(items.get(i));
                    queue.add(new Pair(copy, i + 1));
                }
            }
        }
    }
}

Stefan Kendall 14 年前

生成组合比排序花费的时间要长得多,而且对给定的100000个数字进行排序也不需要那么长的时间 n*log(n) 排序时间。你在预先优化。这很糟糕。