W dniu 2013-09-23 22:35, Wojciech Muła pisze:

> No dobra, a dlaczego nie możesz posługiwać się piątką liczb 1..52
> i potraktować je jako cyfry dla systemu liczenia o podstawie 52?
> Wtedy miałbyś od razu indeks do tablicy, kosztem 5 mnożeń i 4 dodawań.

Przypuszczam, z powodem jest 52^5 = 380204032, większe od 2,5 miliona.


> Jeśli to jednak nie przejdzie, to może lepiej rozważ użycie drzew
> trie.



Napisałem funkcję c2num, która wykonuje przekształcenie, o które pytał
autor wątku. W funkcji używane są współczynniki dwumianowe, które
oczywiście można stablicować zamiast liczyć za każdym razem.

Przykład (C) pokazuje przypadek dla n=6, k=2.





long long int bin2int(char *s)
{
long long int res = 0;
while(*s)
{ res = 2 * res + (*s=='1');
s++;
}
return res;
}

/* Współczynnik dwumianowy */
int binom(int n, int k)
{ if ((k==0) || (k==n)) return 1; else return binom(n-1,k-1)+binom(n-1,k); }


/* Wyznaczenie numeru kombinacji zapisanej w C jako ciąg zero-jedynkowy */
int c2num(int n, int k, long long int C)
{
int res;
long long int mask;
mask = 1;
res = 0;
while (k>0 && n>0)
{
n--;
if ((C & mask)==0) res += binom(n,k-1); else k--;
mask <<= 1;
}
return res;
}


int main()
{
printf ("%d\n",c2num(6,2,bin2int("000011")));
printf ("%d\n",c2num(6,2,bin2int("000101")));
printf ("%d\n",c2num(6,2,bin2int("001001")));
printf ("%d\n",c2num(6,2,bin2int("010001")));
printf ("%d\n",c2num(6,2,bin2int("100001")));
printf ("%d\n",c2num(6,2,bin2int("000110")));
printf ("%d\n",c2num(6,2,bin2int("001010")));
printf ("%d\n",c2num(6,2,bin2int("010010")));
printf ("%d\n",c2num(6,2,bin2int("100010")));
printf ("%d\n",c2num(6,2,bin2int("001100")));
printf ("%d\n",c2num(6,2,bin2int("010100")));
printf ("%d\n",c2num(6,2,bin2int("100100")));
printf ("%d\n",c2num(6,2,bin2int("011000")));
printf ("%d\n",c2num(6,2,bin2int("101000")));
printf ("%d\n",c2num(6,2,bin2int("110000")));
return 0;

}


Wynik:
0
1
2
3
4
5
...
14



P.