Найти все возможные комбинации определенного размера для набора чисел

Я ищу решение следующей проблемы:

Даны два целых числа n и k, вернуть все возможные комбинации k чисел из 1 2 3 ... n.

Убедитесь, что комбинации отсортированы.

Чтобы уточнить,

  1. Внутри каждой записи элементы должны быть отсортированы. [1, 4] — допустимая запись, а [4, 1] — нет.
  2. Записи должны быть отсортированы внутри себя.

Пример: если n = 4 и k = 2, решение:

[
[1,2],
[1,3],
[1,4],
[2,3],
[2,4],
[ 3,4],
]

Это решение, которое я придумал:

public ArrayList<ArrayList<Integer>> combine(int n, int k) {

    //variable where the resultant sets of of numbers are to be stored
    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();

    //finding all the subsets from 1-n of size k and storing them in result
    subset(n,result,k);

    //sorting the resultant set of subsets lexicographically
    Collections.sort(result,new Comparator<ArrayList<Integer>>(){

        @Override
        public int compare(ArrayList<Integer> a,ArrayList<Integer> b){

            int aSize = a.size();
            int bSize = b.size();

            for(int i=0;i<(int)Math.min(aSize,bSize);i++){

                int comparison = Integer.compare(a.get(i),b.get(i));
                if(comparison!=0) return comparison;
            }
               return Integer.compare(aSize,bSize);
        }
    });

    return result;
}


void subset(int n,ArrayList<ArrayList<Integer>> result,int size){
    for(int i=0;i<(1<<n);++i){

        //the arraylist to be added to the result
        ArrayList<Integer> element = new ArrayList<Integer>();

        //iterating 2^n times since those are the total number of possible subsets
        for(int j=0;j<n;++j)
            if((i&(1<<j))>0)
                element.add(j+1);


        //only adding the resultant subset to the result if it matches the size criteria
        if(element.size() == size)
            result.add(element);
    }
}

Я смотрю на этот ответ и не могу не думать, что должен быть более оптимальный способ сделать это.

Судя по всему, эта программа имеет временную сложность O(nlogn * 2^n). Что совсем плохо. Я пытаюсь рассчитать каждое подмножество, прежде чем проверять, соответствуют ли они критериям размера. Любой способ найти количество подмножеств, повторяя только nCk раз?

nCk — количество комбинаций, которые мы можем надеяться найти. Где nCk = n!/(k!*(n-k)!)


java performance subset combinatorics lexicographic
person Aditya Satyavada    schedule 04.09.2016    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Вы можете сгенерировать их напрямую в правильном порядке (псевдокод):

for(i1 =  0 + 1; i1 <= n-k+1; ++i1)
for(i2 = i1 + 1; i2 <= n-k+2; ++i2)
for(i3 = i2 + 1; i3 <= n-k+3; ++i3)
for(i4 = i3 + 1; i4 <= n-k+4; ++i4)
....
for(ik = i? + 1; ik <= n-k+k; ++ik){
    output = [i1, i2, i3, ..., ik];
}

Поскольку вы не создаете код на лету, вы можете реализовать это с помощью рекурсии следующим образом:

private static void Iterate(int[] outp, int n, int k, int actIndex, int lastVal)
{
    if (actIndex > k)
    {
        System.out.println(Arrays.toString(outp));
        return;
    }

    for (int i = lastVal + 1; i <= n - k + actIndex; ++i)
    {
        outp[actIndex - 1] = i;
        Iterate(outp, n, k, actIndex + 1, i);
    }
}

и назовите это:

int n = 4;
int k = 2;
Iterate(new int[k], n, k, 1, 0);

выход:

[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]
person Antonín Lejsek    schedule 04.09.2016
comment
Из того, что я могу понять, вы, по сути, устанавливаете крайний левый элемент при каждом рекурсивном вызове. Как только вы достигаете предела размера, вы добавляете набор в некоторую структуру данных хранения и возвращаетесь вверх по дереву рекурсии. Это правильно ? - person Aditya Satyavada; 04.09.2016
comment
@AdityaSatyavada Я не уверен, правильно ли я вас понимаю. Я добавил реализацию, если у Вас возникнут проблемы, это должно помочь. - person Antonín Lejsek; 05.09.2016