k-combinations of a set of integers in ascending size order

P开发者_如何转开发rogramming challenge: Given a set of integers [1, 2, 3, 4, 5] I would like to generate all possible k-combinations in ascending size order in Java; e.g.

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

It is fairly easy to produce a recursive solution that generates all combinations and then sort them afterwards but I imagine there's a more efficient way that removes the need for the additional sort.

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

Then call, say, comb(10,20,30). It will print:

[10]
[20]
[30]
[10, 20]
[10, 30]
[20, 30]
[10, 20, 30]

There are two ways of interpreting the "ascending" requirement. The looser interpretation is "in every list, the integers should appear in ascending order". The stricter interpretation is "the lists need to be given in order". I guess that's the one you want, but I came up with a simple iterative way to satisfy the looser requirement.

For n items, count through all n-bit numbers. If the bit corresponding to an item is there, then it's in the result list.

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()+", ");
    }
  }

Result for 1,2,3,4,5 is: [], [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]

Yes, I know, I lose points for not using recursion.

I was thinking about this some more and realised it can be efficiently done using a dynamic programming approach. Below is the iterative solution I've produced, which uses a Queue to hold state (although one could use a Stack instead).

I believe this is far more efficient than a recursive iterative deepening search as it will not involve revisiting existing states during the generation; it remembers the previous states using the queue and uses these to generate successive states.

Performance Comparison

Algorithm                    | 5 elems | 10 elems | 20 elems
--------------------------------------------------------------------------
Recursive (#recursions)      | 62      | 2046     | 2097150
Dynamic   (#loop iterations) | 32      | 1024     | 1048576

Code

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

Generating combinations takes MUCH longer than sorting, and it doesn't take that long to sort 100,000 numbers given n*log(n) sorting time. You're pre-optimizing. This is bad.