Pořadí kombinace v poli

da sa to robit scitavanim predpripravenych offsetov, ak uvazujem kombinacie X z Y, tak si pripravim tabulku C(a,b) pre vsetky 'a' z rozsahu 1 az X, a pre vsetky 'b' z rozsahu 1 az Y, kde C je kombinacne cislo (pocet kombinacii a z b), C(a,b) = b! / (a! * (b-a)!)
a potom sa posuvam o offsety z tabulky:
ak 1.cislo je:
1: ostanem na zaciatku pola
>=2: posuniem sa o offset C(X-1, Y-1)
>=3: posuniem sa este o offset C(X-1, Y-2)
>=4: posuniem sa este o offset C(X-1, Y-3)
... atd. da sa to robit v cykle znizovanim 1.cisla az po nulu a pripocitavanim prislusnych offsetov z tabulky.

pre 2.cislo:
ak rozdiel 2.cisla a 1.cisla je 1: nic
ak rozdiel 2.cisla a 1.cisla je >=2: posuniem sa o C(X-2, Y-1 - 1.cislo)
ak rozdiel 2.cisla a 1.cisla je >=3: posuniem sa este o C(X-2, Y-2 - 1.cislo)
ak rozdiel 2.cisla a 1.cisla je >=4: posuniem sa este o C(X-2, Y-3 - 1.cislo)
... atd. tiez v cykle znizovanim 2.cisla az po 1.cislo a priratavanie offsetov z tabulky.

pre 3.cislo:
ak rozdiel 3.cisla a 2.cisla je 1: nic
ak rozdiel 3.cisla a 2.cisla je >=2: posuniem sa o C(X-3, Y-1 - 2.cislo)
ak rozdiel 3.cisla a 2.cisla je >=3: posuniem sa este o C(X-3, Y-2 - 2.cislo)
ak rozdiel 3.cisla a 2.cisla je >=4: posuniem sa este o C(X-3, Y-3 - 2.cislo)
... atd. tiez v cykle znizovanim 3.cisla az po 2.cislo a priratavanie offsetov z tabulky.

atd pre dalsie cisla. Nechce sa mi tu overovat teraz presne ci to co som napisal suhlasi, ale v principe sa takto da relativne rychlo (zlozitost takeho algoritmu je snad len O(1) alebo kolko :) urcit offset.

Jo jo, to je presne ten postup, ktery me napadl. Teda v principu, ono to zase tak jednoduchy neni a bude potreba to trochu upravit.

co nie je jednoduche a co treba upravit? Malo by to suhlasit tak ako som pisal, a zalgoritmizovanie toho co som pisal je tak max. na pol hodinu.

Hmm, promin blbe ctu

Ak by si chcel implementaciu v C tak:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

void VyplnTabulkuC(int X, int Y, int* Table_C)
{
	int i, j;

	for(i=0; i<X; i++)
		for(j=i; j<Y; j++)
			if(i==0 || i==j)
			{
				Table_C[i*Y + j] = 1;
			}
			else
			{
				Table_C[i*Y + j] = Table_C[i*Y + j-1] + Table_C[(i-1)*Y + j-1];
			}
}

int DajIndexKombinacie(int* prvky_kombinacie, int X, int Y, int* Table_C)
{
	int i, j, predch_prvok = -1, aktualny_prvok, offset = 0;

	for(i=0; i<X; i++)	// pre kazdy prvok kombinacie:
	{
		aktualny_prvok = prvky_kombinacie[i];
		for(j=predch_prvok+2; j<=aktualny_prvok; j++)
		{
			offset += Table_C[(X-1-i)*Y + Y-j];
		}
		predch_prvok = aktualny_prvok;
	}

	return(offset);
}
         
void main(int argc, char *argv[])
{
	int i, j, k, prvky_kombinacie[3];
	int Table_C[3 * 6];

	VyplnTabulkuC(3, 6, Table_C);
	
	for(i=0; i<6; i++)
		for(j=i+1; j<6; j++)
			for(k=j+1; k<6; k++)
			{
				prvky_kombinacie[0] = i;
				prvky_kombinacie[1] = j;
				prvky_kombinacie[2] = k;

				printf("%d%d%d : index %d\n", i+1, j+1, k+1, DajIndexKombinacie(prvky_kombinacie, 3, 6, Table_C));
			}
}

main je len priklad pre kombinacie 3 z 6, funkcie VyplnTabulkuC a DajIndexKombinacie su univerzalne.
Pozor: pole prvky_kombinacie obsahuje poradove cisla prvkov kombinacie a pocita sa od 0, t.j. ak mam prvky "1","2","3","4","5" tak "1" ma poradove cislo 0, atd.
Kombinacia "123" bude teda ulozena v poli prvky_kombinacie takto:
prvky_kombinacie[0]=0
prvky_kombinacie[1]=1
prvky_kombinacie[2]=2