Pořadí kombinace v poli

Přímý výpočet mě nenapadá (to neznamená, že není). Tak tedy hledat: Je-li pole seřazeno, je jediný nejrychlejší algoritmus "Půlení intervalů". Podíváš se na prostřední prvek pole Je-li hledané číslo menší, dále půlíš dolní polovinu, je-li větší půlíš horní díl. Je-li shodné, končíš. Rekursivně atd.

Jo tenhle postup me taky napadl, nicmene i tak bych radsi rychlejsi. Ale i tak jsi me privedl na zajimavou myslenku, dik Jestli z toho neco bude, tak to sem placnu.

rychlejší než pulení intervalu jsou pak hešovací tabulky apod. Tedy:
klíč do tabulky je těch 365 a výsledek je to pořadové číslo, v poli něco takovehlo:
cislo_pozice=Pole_Hash[365];

a pamatova narocnost? Predstav si ze mas kombinacie o 15 prvkoch a hladas kombinaciu napr. 123456789012345 tak potom Pole_Hash[123456789012345] ? Takze tabulka Pole_Hash musi mat aspon 1000000000000000 zaznamov? (min 1000 terabytes RAM?)
Pocet kombinacii nie je az tak velky, napr. pocet kombinacii 15 z 20 je len 20!/(15!*5!) = 15504 kombinacii. A k tomu by si potreboval 1000TB hash tabulku

pametova narocnost?
lze použít rozptylovací funkce tedy jen počet prvku +/- (java má vlastní funci, doproučuje se 80% zaplnění).

S polem to byl pouze příklad a naznačení - pokud použiješ třeba v jave k tomu určenou HashTable - bude vhodne alokovat pouze 20k zaznamu. Nikoliv silene cislo co jsi uvedl. Pouze jsem naznacil, ze jde o prim pristup (v idealnim pripade). A ukazal implementaci v poli (ktera by se treba pro jeho kombinaci 3 cisel hodila, kterou uvedl)

a kdyz uz jsme u toho chytani za slovo - Pole[365] nerika nic o tom jak je velke a jak bude, napriklad mohu tvrdit, ze staci overloading "[]" v C++ pole a muze to pak po prepsani []treba znamenat neco jako : poradi=Pole[rozptylovaci_funkce_vyseledkem_ktere_j e_pristup_doOpravdovehoPole(365)];

Ano hash funkcia sa da pouzit na zjednodusenie vyhladavania, ale nie je to take easy ako si to napisal predtym. Napr. nedostanes jeden konkretny index - u hash funkcie sa moze stat ze dva rozne vstupy daju rovnaky hash, a teda musel by si mat nejaku dynamicku hash tabulku ktora moze mat viac hodnot pre jeden hash, t.j. napr. Hash_Table[123] ti moze vratit sadu indexov (ak by napr. 123 a 456 davali rovnaky hash, tak ti Hash_Table[123] vrati index pre 123 a aj index pre 456, t.j. 2 indexy) a ty si musis najst ze ktory z nich je ten spravny.
Je to relativne komplikovana vec na naprogramovanie (pouziva sa v realnych DB enginoch na databazy, nie na jedno pole ktore si ktosi programuje v C), ale ano, mohol by tym zrychlit hladanie (nechapem ale potom preco nepouzije rovno nejaky DB engine, ak uz ma pouzivat taketo DB techniky).

nevim proc jsi se do me takto oprel, nikdy jsem nerikal ze to je jedoduche (a ze v jave treba fakt je, kde ma na to specialni tridy). Kdyz si prectest muj prispevek, tak tam narazis na "prim pristup (v idealnim pripade). " -> ta zavorka naznacuje, ze mam poneti o tom co to kolize je. Netvrdil jsem ze tam nejsou. Pokud pouzije javu a HashTable, tak to ovsem neni jeho starost ale starost teto tridy -> a hadam, ze v jinych jazycich je take mozne sehnat tridy s hotovou implementaci hash tablulky (mozna u jinejch trosku prohlem, ze java ma lepsi pristup a info o objektech v tabulce a ma moznost chyrejsi rozptylovaci funkce)

A kazdopadne rce radil "binarnim pulenim" se složitostí "log n" a tazatel rikal, ze pomale - idealni hash funkce se priblizuje k "omikrom(1)", pokud je "log n" pomale pak uz moc moznosti neni.

v reakci na tento prispevek, nejlepsi bude kdyz si to spocita nejakou funkci, pripadne navrhne jinak ten program.

Ja som sa do nikoho neoprel, len to uvadzam na pravu mieru. Nemozes to napisat ako

cislo_pozice=Pole_Hash[365];

ptz tak to nefunguje. Funguje to tak ze
zoznam_moznych_pozicii = DajIndexyPodlaHashu(Hashuj("365"));
a potom
index = PrehladajZoznamPoziciiANajdiTuSpravnu(zoznam_mozny ch_pozicii, "365")
Narocne na tom (aj casovo) je napr. vytvorenie hash tabulky (kedze napr. pre jeden hash bude 20indexov, pre iny hash budu 3indexy, a pri vytvarani hash tabulky to bude treba nejak umiestnovat do pamate a pri viac indexoch na jednom hashi si bud robit spojky alebo rezervovat si pre kazdy hash viac miesta nielen pre jeden index atd.).
A musel by si mat ku kazdemu indexu uvedeny aj vstup t.j. to "365" aby si potom vedel najst ten spravny, to tiez moc nesetri RAM...

Ano vyhladavanie to samozrejme extremne urychli, k tomu nic nenamietam, namietal som len ze to nie je take easy ako si naznacil ... a moze to potrebovat dost RAM. Ale ano za cenu tej RAM to extremne zrychli vyhladavanie.

To by se ti zachvíli nevlezlo do paměti (při více prvcích)...

/edit: pozdě...

Spočítat počet kombinací pro jedno číslo na začátku a pak už by to měla být hračka.
Nejjednodušší příklad: 3 ze 3
pro 1 na začátku jsou dvě kombinace 1-2,3 a 1-3,2
pro 2 a 3 taky po dvou. takže kombinace začínající trojkou může být nejdřív na 1+(2*2)
..na pátém místě.

ale ty pocitas permutacie a nie kombinacie.

// edit: mazem vzorec, nebol uplne spravny...

Povazujem to za nezmysel, mozes objasnit naco ti to je? Skus radsej zmenit ten tvoj program/algoritmus resp. uvazovanie tak, aby si nemusel hladat kombinaciu v poli, ved tu kombinaciu mas ako vstup tak naco ju chces hladat

na které pozici číslo bude je pochopitelně záležitostí algoritmu generujícho tyto čísla. Pochopitelně se pak na to něco odvodit bude dát.

Jinak Rceho puleni intervalu neni pomale - o proti generovani teto posloupnosti, naprosto zanedbatelne

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

inac asi ta bude iritovat ze potrebujes aj riadok tabulky C s indexom 0, ten bude cely vyplneny 1-ckami (pocet kombinacii 0 prvkov z cohokolvek je 1, lebo cokolvek! / cokolvek!*0! = 1, 0!=1 to je tak tusim dohodnute definiciou).
Priklad:
3 z 6 (X=3, Y=6):
123, 124, 125, 126, 134, 135, 136, 145, 146, 156, 234, 235, 236, 245, 246, 256, 345, 346, 356, 456

C(a,b) = b! / (a! * (b-a)!), a<=X, b<=Y:
  b= 1   2   3   4   5   6
a ------------------------
0 | 1   1   1   1   1   1
1 | 1   2   3   4   5   6
2 | -   1   3   6  10  15
3 | -   -   1   4  10  20
polia oznacene "-" nepocitat nemaju zmysel, mozu byt inicializovane na 0, C pocitat len pre polia ak a<=b

123: offset 0, 0 + 0 + 0 = 0
124: offset 1, 0 + 0 + C(X-3, Y-1 - 2.cislo) = C(0, 3) = 1
125: offset 2, 0 + 0 + C(X-3, Y-1 - 2.cislo) + C(X-3, Y-2 - 2.cislo) = C(0, 3)+C(0, 2) = 2
... skus si overit ci sedia vsetky, negarantujem ze je to 100% spravne...
a napr. zoberiem len tak nieco zo stredu:
246: offset C(X-1, Y-1) + C(X-2, Y-1 - 1.cislo) + C(X-3, Y-1 - 2.cislo) = C(2,5)+C(1,3)+C(0,1) = 10+3+1 = 14 - suhlasi, 246 je na offsete 14 (vid vyssie). offsety sa pocitaju od 0 (prve cislo je offset 0).

P.S. inac predtym ako tento algoritmus zavolas, si overit ze vstup je spravny, t.j. ze kazda cifra je vacsia ako jej predchadzajuca cifra, ak nie tak tu kombinaciu zorad pred zavolanim tohoto algoritmu.
A pred zavolanim algoritmu si overit aj ze ziadna z cifier neprekracuje max.povolenu (t.j. ze kazda cifra <= Y a ze ziadna cifra nie je <=0).
P.S.2. a ak budes pracovat s indexami prvkov (0...Y-1) a nie s ciframi (1..Y) tak potom jednoducho vsade kde sa v indexe pola C vyskytuje cifra, pridaj este +1)

este doplnim: najvacsi problem ti asi u tohoto postupu bude robit vyratanie tej tabulky C, ak sa jedna o vacsi pocet prvokv, kedze faktorial bude potom extremne velky (napr. uz 13! sa nevojde do 32bitoveho integeru). Plavajucu ciarku nepouzit, mohlo by to sposobit chybu vypoctu a tym nespravny index.

Nic ale nie je stratene, kombinacne cisla sa daju ratat postupne vyplnanim tabulky po riadkoch, podla predchadzajucich prvkov tabulky:
C(a,b) = C(a, b-1) + C(a-1, b-1)
lebo
C(a, b-1) + C(a-1, b-1) = (b-1)!/a!(b-1-a)! + (b-1)!/(a-1)!(b-a)! = (b-a)*(b-1)!/a!(b-a)! + a*(b-1)!/a!(b-a)! = ((b-a)*(b-1)! + a*(b-1)!) / a!(b-a)! = (b-1)!*((b-a) + a) / a!(b-a)! = b! / a!(b-a)! = C(a,b)

Takze vyplnis nulty riadok a prvok C(1,1) jednickami, a ostatne prvky tabulky C vyratas scitavanim prvku suseda vlavo, a suseda vlavo hore. Nepouzivaj na vypocet faktorial.

a stale nechapem naco ti to je. Podla mna je to nezmysel a vobec to nepotrebujes resp. verim ze sa ten program da urobit uplne inac efektivnejsie, bez potreby takehoto vypoctu.

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