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

Question

Programming task: Given a set of integers [1, 2, 3, 4, 5] I would like to generate all possible k-combinations in ascending order of size in Java strong>; eg.

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

It's pretty easy to create a recursive solution that generates all the combinations and then sorts them later, but I believe that a more efficient way eliminates the need for additional juice.

Answer 1

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

Answer 2

.

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]

Answer 3

"". " , ". - " ". , , , .

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]

Yes, I know, I'm losing points for not using recursion.

Answer 4

Creating MUCH combinations is longer than sorting, and it doesn't take so long to sort 100,000 numbers based on the sorting time n*log(n). You pre-optimize. This is bad.