program wypisujacy kombinacje

Ehm mam maly problemik. Musze napisac porgram ktory z n elementowej tablicy wypisuje wszystkie n/2 elementowe kombinacje.

Generalnie dla ustalonych parametrow np n=40, kombinacje 3 elementowe nie mialbym problemu bo napisalbym cos takiego

for i:=1 to 40 do
for j:=i+1 to 40 do
for k:=j+1 to 40 do
pritnf(tab[i], tab[j], tab[k])

hm no ale jak zrobic to z tym n/2 elementowymi kombinacjami

uloz wszystkie elementy w uporzadkowany ciag indeksowalny numerami 0...(n-1), stworz ciag binarny (ciag zer-i-jedynek) postaci 00000....0011...1111 o n/2 zerach i n/2 jedynek, nastepnie zamieniaj zera i jedynki miejscami (z glowa!) az do otrzymania 11111...1100..00000 i za kazdym przestawieniem wypisz elementy z ciagu o pozycjach na ktorych ustawiona jest jedynka

majac [ABCD]
0011 -> CD
0101 -> BD
0110 -> BC
1001 -> AD
1010 -> AC
1100 -> AB

sposob przestawiania zer i jedynek jest banalny, zostawiam Tobie

warto tez zapoznac sie http://www.cplusplus.com/reference/algorithm/next_permutation.html

Trzymasz indeksy w tablicy, a następnie w każdym kroku odpowiednio ją modyfikujesz.
Następną kombinację uzyskujesz przez funkcję:

int nextCombination( int* indexes, int count, int n )
// @param indexes - tablica z indeksami do zmodyfikowania
// @param count - liczba indeksów/wielkość podzbioru
// @param n - liczba dostępnych elementów/wielkość zbioru
// @return - czy wygenerowano następną kombinację indeksów
{
    int maxFirst = n - count;
    for( int i = count-1; i>=0; --i )
         if( indexes[ i ] < maxFirst + i )
         {
             int k = ++indexes[ i ];
             for( int j = i; j<count; ++j )
                  indexes[ j ] = ++k;
             return 1;
         }
    return 0;
}

A jeszcze pytanie C czy C++?

zdecydowanie C

Kiedyś napisałem takie funkcje (lepsza złożoność bo liniowa):

void InicjujKombinacje(unsigned* tablica, int k, int n) 
{
   k--;
   tablica[k] = k - 1;
   while(k-- > 0) tablica[k] = k;
}

int NastepnaKombinacja(unsigned* tablica, int k, int n) 
{
   int i = k - 1;
   ++tablica[i];
   while((i > 0) && ((int)tablica[i] >= n - k + 1 + i)) ++tablica[--i];
   if((int)tablica[0] > n - k) return 0;
   for (i = i + 1; i < k; ++i) tablica[i] = tablica[i - 1] + 1;
   return 1;
}

//przyklad uzycia
#define n 4
#define k 2
int i;
unsigned tablica_indeksow[n];
const char *tablica_elementow = "ABCD";
InicjujKombinacje(tablica_indeksow, k, n);
while(NastepnaKombinacja(tablica_indeksow, k, n))
{
   for(i = 0; i < k; i++) printf("%c", tablica_elementow[tablica_indeksow[i]]);
   printf("\n");
}