Kombinator

Zastanawiliście się kiedyś, jak w miarę szybko wygenerować wszystkie możliwe n-elementowe kombinacje m-elementowej tablicy? Głupie, co nie? Ale ja to zrobiłem 😉


/*
* Wszystkie mozliwe kombinacje n elementow z m-elementowej tablicy :)
*/

#include
#include
#include

#ifndef true
#define true 1
#endif

/*
* Ciag tekstowy, z ktorego bedziemy produkowac nasze dane. Nic nie stoi na
* przeszkodzie, aby podawal to user 😀
*/
char zestaw[] = „0123456789”;

int main(void)
{
unsigned int m, n;
unsigned int *i, j;
int k1, k2;
int we_have_repetitions;
int we_have_overflow;

m = strlen(zestaw);
n = m + 1;

while(n > m){
printf(„Podaj n (<= %u): „, m);
scanf(„%u”, &n);
}

i = malloc(n * sizeof(unsigned int));

for(j = 0; j < n; j++)
i[j] = 0;

/* Prawie nieskończona pętla */
while(true){
/* Zwiekszamy tablice z indeksami */
we_have_repetitions = 1;
while(we_have_repetitions){
we_have_overflow = 1;
j = n – 1;
while(we_have_overflow){
i[j]++;

if(i[j] 0){
j–;
} else {
free(i);
return 0;
}
}
} /* we_have_oferlow */

/* Sprawdzamy, czy nie ma przypadkiem zdublowanych indeksow */
/* Musimy zwrocic tez uwage na to, ze 123456 i 654321 to to samo */
we_have_repetitions = 0;
for(k1 = 0; k1 < n – 1; k1++)
for(k2 = k1 + 1; k2 = i[k2]) /* jezeli 123456 i 654321 sa rozne, daj tu == */
we_have_repetitions = 1;

} /* there_are_repetitions */

/* Mamy niezdublowane indeksy 🙂 */
for(j = 0; j < n; j++)
fputc(zestaw[i[j]], stderr);
fputc(‚\n’, stderr);

} /* true */

free(i);
return 0;
}

~ - autor: zipoking w dniu 27 stycznia 2008.