Комбинации натуральных чисел uniq (порядок не важен)

Question

Комбинации натуральных чисел uniq (порядок не важен)

Итак, я искал хорошее решение для моей проблемы.

Мне нужно сгенерировать (распечатать) всю комбинацию из списка целых чисел, например:
если массив содержит целые числа от 0 до n-1, где n = 5:

int array[] = {0,1,2,3,4};

порядок целых чисел в комбинации НЕ важен, означая, что {1,1,3}, {1,3,1} и {3,1,1} на самом деле являются одной и той же комбинацией, поскольку все они содержат один 3 и два.

поэтому для приведенного выше массива все комбинации длины 3:

0,0,0 -> the 1st combination
0,0,1
0,0,2
0,0,3
0,0,4
0,1,1 -> this combination is 0,1,1, not 0,1,0 because we already have 0,0,1.
0,1,2
0,1,3
0,1,4
0,2,2 -> this combination is 0,2,2, not 0,2,0 because we already have 0,0,2.
0,2,3
.
.
0,4,4
1,1,1 -> this combination is 1,1,1, not 1,0,0 because we already have 0,0,1.
1,1,2
1,1,3
1,1,4
1,2,2 -> this combination is 1,2,2, not 1,2,0 because we already have 0,1,2.
.
.
4,4,4 -> Last combination

Сейчас я написал код для этого, но моя проблема:
если числа в массиве не являются целыми числами от 0 до n-1, скажем, был ли массив таким

int array[] = {1,3,6,7};

мой код не работает в этом случае, любой алгоритм или код для решения этой проблемы,

Вот мой код:

unsigned int next_combination(unsigned int *ar, int n, unsigned int k){
unsigned int finished = 0;
unsigned int changed = 0;
unsigned int i;

for (i = k - 1; !finished && !changed; i--) {
if (ar[i] < n - 1) {
/* Increment this element */
ar[i]++;
if (i < k - 1) {
/* Make the elements after it the same */
unsigned int j;
for (j = i + 1; j < k; j++) {
ar[j] = ar[j - 1];
}
}
changed = 1;
}
finished = i == 0;
}
if (!changed) {
/* Reset to first combination */
for (i = 0; i < k; i++){
ar[i] = 0;
}
}
return changed;
}

И это главное:

int main(){
unsigned int numbers[] = {0, 0, 0, 0, 0};
const unsigned int k = 3;
unsigned int n = 5;

do{
for(int i=0 ; i<k ; ++i)
cout << numbers[i] << " ";
cout << endl;
}while (next_combination(numbers, n, k));

return 0;
}

1

algorithm c++combinations

Решение

Другие решения

Этот код требует, чтобы массив «пул элементов» сортировался от минимального до максимального, без повторяющихся записей.

Функция first_combination инициализирует массив результатов («dist») первой комбинацией. После этого, next_combination вызывается в цикле, пока не вернет false (как в вашем примере). Аргументы «n» и «k» были заменены параметрами шаблона, которые выбирают размеры массивов — поэтому функциям перечисления нужен массив пулов в дополнение к результату.

#include <iostream>

template<typename T, int N, int K>
void first_combination(const T (&pool)[N], T (&dist)[K]) {
for(int ki=0; ki<K; ++ki) {
dist[ki] = pool[0];
}
}

template<typename T, int N, int K>
bool next_combination(const T (&pool)[N], T (&dist)[K]) {
int ni = 0;;
int ki = 0;

for(;;) {
const int prev_ni = ni;
// search the pool for the value in this slot
for(ni=0; pool[ni] != dist[ki]; ++ni) {
if(ni == N) return false; // slot contains a value not found in the pool
}

if(++ni < N) break;

ni = 0;
dist[ki] = pool[0];
if(++ki == K) return false;
}

int v = pool[ni];

dist[ki] = v;

// code below assumes pool[] is sorted
for(--ki; ki>=0; --ki) {
if(dist[ki] < v) {
dist[ki] = v;
}
else {
v = dist[ki];
}
}

return true;
}template<typename T, int COUNT>
void dumparray( T (&dist)1) {
std::cout << '{';
for(int i=0; i<COUNT; ++i) {
if(i) std::cout << ',';
std::cout << dist[i];
}
std::cout << '}' << std::endl;
}

int main(int argc, char* argv[]) {
const int pool[] = {1,3,6,7};
int dist[3] = {0};

first_combination(pool, dist);
do {
dumparray(dist);
} while(next_combination(pool, dist));
return 0;
}

2

Итак, вам нужна программа для генерации комбинация (вики-ссылка).

Здесь у вас есть полное описание и даже готовый к использованию алгоритм: http://compprog.wordpress.com/2007/10/17/generating-combinations-1/

0

Источник

Accepted Answer

Если у вас есть рабочий код для генерации всех комбинаций чисел из 0 в n-1тогда это очень просто. У вас есть ваш массив чисел:

int array[] = {1,3,6,7};

Теперь возьмите n = 4потому что в массиве 4 элемента. Создайте все комбинации от 0 до 3 и используйте их в качестве индексов в вашем массиве. Теперь у вас есть все комбинации значений вашего массива, используя все комбинации индексов в этом массиве.

2