Výber podmnožiny z množiny čísel

[zawin]

Majme 8 čísel zapísaných v binárnej forme:
1) 0000 0001 => 1 dekadicky
2) 0000 0010 => 2 dekadicky
3) 0000 0100 => 4
4) 0000 1000 => 8
5) 0001 0000 => 16
6) 0010 0000 => 32
7) 0100 0000 => 64
1000 0000 => 128

Binárnym zápisom 1001 1100 => 156 dekadicky, vyberieme čísla 3,4,5,8 zo zoznamu. Teda jednoducho pozrieme ktoré bity sú nastavené a podľa toho vieme ktoré čísla zo zoznamu tam spadajú. Avšak na vygenerovanie 8 čísel sme spotrebovali 8 bitov, teda 1 bajt.

Moja otázka znie, či by sa tento problém výberu podmnožiny z množiny čísel nedal riešiť ešte inak, ideálne s menšou dĺžkou prvkov samotnej množiny.
Ďakujem.

[martin knocik]

Taká dosť neurčita otazka.

ak to má byt univerzalne, tzn podmnožina može mať 1 až 8 prvkov, tam je 256 možností výberu,( kombinacie bez opakovania K(0,8), K(1,8) ...K(8,8)) tak asi úspornejšie riešenie neexistuje.

Ak by sa dal problem optimalizovať tak že by sa vyberal iba nejaka pevne dana podmnožina, napr presne 4 lubovolné prvky y 8 prvkovej množiny, tak tam by sa dala spraviť napr vyhladavacia tabulka ktora by mala 70 prvkov. Na index tabulky by stačilo 7bitov. tabulka by nemusela byť uložena v RAM pamati
Pri 8 prvkovej množine by sa nič zasadne neušetrilo 1 bit indexu,pri 16 prvkovej množine by sa ušetrilo 5 bitov indexu, pri 800 prvkovej množine by sa ušetrilo 766 bitov indexu, s 800 bitov dlhym indexom by sa ťažko pracovalo,

Ak by sa to podarilo vyberať len prvky napr 1,2,3,6 alebo 2.3.4.7, alebo 3.4.5.8, tak stačila vyhladavacia tabulka s 2 bitovym indexom.

Ďalším problémom je asi praktická realizacia - je system schopny alokovať/pracovať s menej ako 8 bitmi pamate ?

[zawin]

Aby som to trocha zreálnil, tak množina bude mať cca. 10 000 prvkov a vždy vyberám z nich max. 10 prvkovú podmnožinu (teda 1 až 10).

[martin knocik]

Binárnym zápisom 1001 1100 => 156 dekadicky, vyberieme čísla 3,4,5,8 zo zoznamu.

Musíš vyberať všetky 4 císla súčasne ? Ak bi si vyberal cisla postupne za sebou obyčajny index, tj vyber číslo 3 množina[011], vyber cislo 4, mnozina[100]. Na 10000 prvkovu mnozinu by stacil 14 bitov dlhy index + 10 docasnych pamatovych miest pre cisla.

[_petko_]

Množina má kapacitu 10000, alebo tam máš uložených 10000 prvkov? Na sparse bitove polia sa používa kompresia rle, ale potom sa tažšie robia množinové operácie. Keď tam máš uložených vždy iba 10, tak použi normálne pole. Závisí od entropie alebo sa dajú zneužit nejaké predpoklady o dátach atd. Nejako pocitovo si myslím, že neexistuje lepšie riešenie, ale bez dôkazu (asi nejaké cvičenie s kolmogorovskou zložitosťou).