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

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

1 2 3 4 12 13 14 23 24 34 123 134 124 1234 

Чтобы быть более ясным: если входной номер равен 4, я хочу использовать цифры 1-4 и создавать все возможные комбинации цифр (от 1-значных комбинаций до 4-значных комбинаций) без повторения цифр.

Я попробовал следующий код:

 #include  /* Prints out a combination like {1, 2} */ void printc(int comb[], int k) { printf("{"); int i; for (i = 0; i = 0) && (comb[i] >= n - k + 1 + i)) { --i; ++comb[i]; } if (comb[0] > n - k) /* Combination (nk, n-k+1, ..., n) reached */ return 0; /* No more combinations can be generated */ /* comb now looks like (..., x, n, n, n, ..., n). Turn it into (..., x, x + 1, x + 2, ...) */ for (i = i + 1; i < k; ++i) comb[i] = comb[i - 1] + 1; return 1; } int main(int argc, char *argv[]) { int n = 5; /* The size of the set; for {1, 2, 3, 4} it's 4 */ int k = 3; /* The size of the subsets; for {1, 2}, {1, 3}, ... it's 2 */ int comb[16]; /* comb[i] is the index of the i-th element in the combination */ /* Setup comb for the initial combination */ int i; for (i = 0; i < k; ++i) comb[i] = i; /* Print the first combination */ printc(comb, k); /* Generate and print all the other combinations */ while (next_comb(comb, k, n)) printc(comb, k); return 0; } 

Вышеприведенная программа выводит результат. Я хочу получить результат как-то .. но я не могу, потому что вышеприведенный код печатает результат странным образом.

Мы используем int для представления множества. Для i-го бита, если он равен 1, i находится в наборе и наоборот.

Пример: 1010 (2) = {4,2} 1111 (2) = {4,3,2,1}

Для каждого элемента, который будет рассмотрен, есть два варианта: в или нет в наборе.

Итак, всего 2 ^ n разных наборов. И в моем коде я просто перечисляю все возможные int, которые соответствуют набору, и выводят соответствующий набор.

Итак, мы получаем этот код:

 for(int i=1;i<(1< 

при n = 4, выход:

 1 2 12 3 13 23 123 4 14 24 124 34 134 234 1234 

Если вы хотите вывести ответ как порядок подачи, просто сделайте их строкой и поместите эту строку в вектор и сортируйте.

Если n велико, вы можете использовать битсет. Но когда n> 30, оно может не заканчиваться в часах. Таким образом, int эффективен.

Вот программа, которая генерирует комбинации чисел. Он написан на C. Но он может быть переписан на любом другом языке. Пока просто скомпилируйте его и попробуйте!

 #include  #include  int v[100], stack[100]; int sp,i,n,g; int main() { printf("Dimension of V:"); scanf( "%d",&n); //Input numbers for (i=0 ; i=0) sp=sp-1; // if Bottom of stack is reached then stop if (sp<0) break; // set top of stack from one to zero stack[sp]=0; } return 0; } 

для n = 4:

 [oldache@localhost fin]$ ./comb Dimension of V:4 V[0]=10 V[1]=20 V[2]=30 V[3]=40 running... v[0]=10 v[0]=10 v[1]=20 v[0]=10 v[1]=20 v[2]=30 v[0]=10 v[1]=20 v[2]=30 v[3]=40 v[0]=10 v[1]=20 v[3]=40 v[0]=10 v[2]=30 v[0]=10 v[2]=30 v[3]=40 v[0]=10 v[3]=40 v[1]=20 v[1]=20 v[2]=30 v[1]=20 v[2]=30 v[3]=40 v[1]=20 v[3]=40 v[2]=30 v[2]=30 v[3]=40 v[3]=40