k-комбинации набора целых чисел в порядке возрастания размера

Question

Задача программирования: Учитывая набор целых чисел [1, 2, 3, 4, 5], я хотел бы сгенерировать все возможные k-комбинации в порядке возрастания размера в Java ; например,

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

Довольно легко создать рекурсивное решение, которое генерирует все комбинации и затем сортирует их, но я думаю, что есть более эффективный способ, который устраняет необходимость в дополнительной сортировке.

Answer 1

Просто выполните итеративный углубленный поиск .

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 2

Существует два способа интерпретации «восходящего» требования.Более слабая интерпретация - «в каждом списке целые числа должны появляться в порядке возрастания».Более строгое толкование заключается в том, что «списки должны быть приведены по порядку».Я думаю, это то, что вам нужно, но я нашел простой итеративный способ удовлетворить более слабые требования.

Для 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]

Да, я знаю, я теряю очки за то, что не использовал рекурсию.

Answer 3

Я подумал еще об этом и понял, что это можно эффективно сделать, используя подход динамического программирования.Ниже приведено итеративное решение, которое я создал, в котором для хранения состояния используется 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 4

Создание комбинаций занимает НАМНОГО дольше, чем сортировка, и не требуется так много времени, чтобы отсортировать 100 000 чисел при n*log(n) времени сортировкиВы предварительно оптимизируетеЭто плохо.