Найти подмножества размера K в N набор


Вопрос: есть набор Anи она состоит из чисел от 1 для n.

An={1, 2, 3, ..., n}

Напечатать все подмножества размера K в An. Он должен быть сформирован в порядке, как в примере ниже.

Так, например, n=5 k=3

{1, 2, 3} {1, 2, 4} {1, 2, 5} {1, 3, 4} {1, 3, 5} {1, 4, 5} {2, 3, 4} ... {3, 4, 5}

Я не уверен, если есть другой способ, не использовать рекурсию. Я сделал это с помощью рекурсии, но проблема в том, что все тесты должны быть сделано в течение 1 сек. Когда N и K как 5, 3 и 12, 6 это нормально, но когда дело доходит до как 50, 48 или 100, 95это занимает слишком много времени. Я реальной борьбы с этой проблемой.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void subset(int n, int k, int arr[], int pos[], int index, int start){
    int i, j;

    if(index == k){
        for(j=0; j<k; j++){
            if(j==k-1)
                printf("%d\n", pos[j]);
            else{
                printf("%d ", pos[j]);
            }
        }
        return;
    }

    for(i=start; i<n; i++){
        pos[index] = arr[i]; 
        subset(n, k, arr, pos, index+1, i+1);
    }
}

int main(){
    int n, k, arr[100], index=0, start=0;

    scanf("%d %d", &n, &k);

    // 1<=n<=100 ; 1<=k<=n
    if(n>100||n<1 && k>n||k<1)
        return 0;

    int i;
    for(i=0; i<n; i++)
        arr[i]=i+1;

    int *pos = (int*)malloc(sizeof(int)*k);

    time_t clockstart=0, clockend=0;
    float gap;
    clockstart = clock();
    subset(n, k, arr, pos, index, start);
    clockend = clock();
    gap = (float)(clockend-clockstart)/(CLOCKS_PER_SEC);

    printf("%f\n", gap);

    return 0;
}

Я думаю, что я должен использовать что-то вроде хвостовую рекурсию или вектора в C++, но я не могу понять, как работать с теми.



Комментарии
2 ответа

Как вы, наверное, заметили, замедление происходит, когда n большой и k близко к n. Если это медленнее, чем следует, вполне вероятно, потому что он делает ненужную работу. Давайте рассмотрим случай, когда n=5 и k=3и идите к точке в выполнении вашей программы, где arr[0] = 1 и index = 1. В for-петли в subset()вы смотрите на все возможные значения от start = 2 для n = 5. Однако, не все значения приведет к действительным решениям. Здесь представлен список всех {1, i} вы проверяете, и какие подмножества можно:

{1, 2} -> {1, 2, 3} {1, 2, 4} {1, 2, 5}
{1, 3} -> {1, 3, 4} {1, 3, 5}
{1, 4} -> {1, 4, 5}
{1, 5} -> no solutions

Как вы можете видеть, {1, 5} не имеет каких-либо возможных подмножеств. Или, говоря иначе, 5 слишком большие числа pos[1] чтобы дать каких-либо решений.

Вместо перебора всех чисел от start для nпопробуйте выяснить, что фактический максимум, что будет по-прежнему дают решений.

1
ответ дан 29 марта 2018 в 09:03 Источник Поделиться


        for(j=0; j<k; j++){
if(j==k-1)
printf("%d\n", pos[j]);
else{
printf("%d ", pos[j]);
}
}

Поцелуй:

        for(j=0; j<k; j++){
printf("%d ", pos[j]);
}
printf("\n");



Я не уверен, если есть другой способ, не использовать рекурсию.

Есть. Если я дам тебе подмножество, как вы находите следующий?


Если последний элемент подмножества является не последним элементом в An затем увеличивать его и вернуть. В противном случае, если элемент слева не предпоследний элемент Anшага, что одна и распространяется на право. В противном случае ...

1
ответ дан 29 марта 2018 в 10:03 Источник Поделиться