Алгоритм обратного слежения для генерации всех комбинаций

Question

У меня есть небольшая проблема с этим. Я хочу сгенерировать каждую возможную комбинацию. Числа, расположенные в массиве 1D, и считываются из файла. Теперь я не знаю проблемы: я знаю, что каждая комбинация, которая будет напечатана для мониторинга, находится в порядке возрастания. Задача состоит в том, что если она заканчивается наименьшим числом, она не поднимается до следующего числа.

Пример: файл массива 1D с 1,2,3,4,5 и n = 5 и p = 3; Возможные комбинации:

1 2 3, 1 2 4, 1 2 5, 1 3 4, 1 3 5, 1 4 5, 2 3 4, 2 3 5, и т.д. ..

Вот что я сделал до сих пор:

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

void print(int*,int); 
void combination(int*,int,int,int); 
int main() 
{ 
    FILE *fin = fopen("bemenet.txt","r"); 
    if(!fin){printf("Error opening file @!!!");return 0;} 
    int *a,i,n,p = 3; 
    fscanf(fin,"%i ",&n); 
    a = (int*)malloc(n*sizeof(int)); 
    for(i = 0; i < n; ++i){ 
     fscanf(fin,"%i ",&a[i]); 
    } 
    combination(a,n,p,0); 

    return 0; 
} 

void combination(int *a,int n,int p,int k) 
{ 
    int i; 
    if(k == p){ 
     print(a,k); 
    } 
    else{ 
     for(a[k + 1] = a[k] + 1 ; a[k+1] < n; ++a[k+1]){ 
      combination(a,n,p,k+1); 
     } 
    } 
} 
void print(int *a,int k) 
{ 
    int i; 
    for(i = 0; i < k; ++i){ 
     printf("%i ",a[i]); 
    } 
    printf("\n"); 
} 

Answer 1

причины, почему число только увеличивающееся в том, что вы никогда не уменьшаете их. Также условие a[k+1] < n не имеет для меня никакого смысла, почему бы вам сравнить размер поля с элементом массива (который может быть, например, 1000)? Также вы не должны изменять элементы массива как ++a[k+1], так как нет причин для этого.

См., Например, Algorithm to generate all possible permutations of a list? для получения дополнительной помощи.