Код комбинации C для случайного набора целых чисел - PullRequest
Новая
       17

Код комбинации C для случайного набора целых чисел

0 голосов
/ 19 сентября 2011

У меня есть случайный набор S = {3,12,15,24,33,40}, и мне нужно сгенерировать подмножества размера 3 из этого набора. Большинство примеров и объяснений, касающихся комбинации, включали набор увеличения и упорядоченные значения, такие как S1 = {1,2,3,4, ... n}. Используя формулу комбинации, я обнаружил, что количество возможных комбинаций равно 20, но не могу понять, как создать этот список в C.

Что если набор случайный, как S выше, и как я могу получить возможный список без дубликатов в C?

Спасибо.

Ответы [ 4 ]

2 голосов
/ 19 сентября 2011

Используйте алгоритмы, которые вы видели, которые имеют увеличивающиеся упорядоченные значения, и просто замените их на значения в вашем списке.

Например, комбинации (с 0 индексами) будут: 

0, 1, 2
0, 1, 3
0, 1, 4
...
...

Затем получите массив с вашими номерами 

int array[] = { ...values... };

и измените комбинации на: 

array[0], array[1], array[2]
array[0], array[1], array[3]
...
...
1 голос
/ 19 сентября 2011

Вы можете сгенерировать все комбинации из n элементов рекурсивно. Примерно так должно работать: 

void combos(int[] values, int[] used, int[] selected, int len, int needed, int next) {
    int i;
    if (needed > 0) {
        /* select each available item as the next item and recurse */
        for (i = 0; i < len; i++) {
            if (!used[i]) {
                used[i] = 1;
                selected[next] = values[i];
                combos(values, used, selected, len, needed-1, next+1);
                used[i] = 0;
            }
        }
    } else {
        /* selected[0] .. selected[next-1] contains a combination */
        reportCombination(selected, next);
    }
}

Назовите это с помощью next=0 и needed=3, чтобы перевести мяч, и он должен сгенерировать 20 вызовов на reportCombination, каждый с уникальной комбинацией из 3 значений. (Если вам нужно собрать массив всех комбинаций, тогда вам не нужно reportCombination, но вам понадобятся дополнительные аргументы бухгалтерского учета или некоторые глобальные переменные.)

0 голосов
/ 19 сентября 2011

Используйте декартово произведение того же самого набора снова , удаляя повторения,, попробуйте этот код ,, 

int array[6]={3,12,15,24,33,40};
int combinations[20][3];
int n=0;
for(i=0;i<4;i++)
{                      //loops for 1st num in combination
   for(j=i+1;j<5;j++)
   {                       //loops for 2nd num in combination
     for(k=j+1;k<6;k++)
     {                         //loops for 3rd num in combination
        combinations[n++]={array[i],array[j],array[k]};
     }
   }
}

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

0 голосов
/ 19 сентября 2011

Вы запрашиваете подмножество набора мощности из S , вызываемого по соглашению P (S) , а именно всех трехэлементных наборов вБлок питания P (S) .

Вы можете изменить функцию набора мощности в этом примере кода C , чтобы выводить наборы определенной мощности (количество).

...