Program na vygenerovanie kombinacii – C / C++ – Fórum – Programujte.com

Ahojte , potreboval by som program, ktorý vygeneruje všetky možné kombinácie týchto čísel : 00,11,01,10 pre 32 políčok

- bude to asi 4 na 32 druhú - počet možných kombinácií

00,11,01,10 - berú sa ako 4 čísla

opakovanie je dovolené ( je možné že za sebou bude aj napríklad 6x 00,00,00,00,00,00 aj viac krát )

Potreboval by som všetky tieto možné kombinácie vygenerovať a zapisať do txt súboru (ak to bude generovať dlho, nevadí )

Prípadne ak by to java dokázala rýchlejšie možte napísať, je jedno v akom programe to bude

Bol by som vdačný ak by mi s tým niekto pomohol

#1 Lisiak46
to bude trvat pekne dlouho. A bude to chtit 1627389952 Terabajtu mista (64 znaku na bity + 32 carek + odradkovani) * 2^64. Respektive 1552 exabajtu. A pokud pocitam spravne, tak i pri rychlosti generovani 200MB/s to zabere pres 270tisic let. S javou by to mohlo byt i za 10 milionu let, jelikoz nezna pojem cislo bez znamenka a muselo by se to resit sloziteji :D

Nicmene staci pouzit uint64_t a pricitat porad 1. Pak z toho akorat vytahas jednotlive dvojice bitu. Trochu hure se bude delat konecna podminka. Bude potreba nejaka dalsi promenna, abys prestal pri pruchodu nulou (ale ne hned na zacatku).

#2 KIIV
Ahoj, dakujem za odpoved, s tym pouzitim  uint64_t by to trvalo tiez roky?

ono je to v podstate tak , ze mam 2bitovy  obrazok, ktorému chýbaju pixely ,ktorých je 32  

tie cisla 01,00,11,10 sú v podstate farby pixelov ,ktoré potrebujem vygenerovať inak dala by sa ešte pridať podmienka , že viac ako 7 rovnakých pixelov za sebou nepojde ,to by tam nepasovalo

Připojen obrázek.

#3 Lisiak46
To bych si radeji pohral s nejakym algoritmem, ktery vezme pixely nahore a dole a vypocita pravdepodobnou barvu.

Zalezi hlavne na tom, ceho chces dosahnout. Jestli je obrazek jeste vetsi, tak uz detekovat hrany a doplnit to podle nich.

#4 KIIV
áno obrázok je väčší, (smerom hore) ten riadok pixelov dole je posledný no ja potrebujem trafiť tú pôvodnú 100% kombináciu (aj keby bola v milione kombinácií ,stačí že tam bude) , kolko by to zabralo teda použitím uint64_t?

prípadne zistiť podľa ostatných ,ale to neviem či sa trafím

#5 Lisiak46
s uint64_t je to tech 270tisic let rychlosti 200MB/s. Si asi neumis moc predstavit, kolik je 2^64 kombinaci. Je to 18446744073709551616 tj 18,45 trilionu moznosti. A to jeste musis nejak verifikovat

#5 Lisiak46
Pokud existuje jediná vyhovující kombinace a ty ji dokážeš identifikovat, tak se k ní dost pravděpodobně půjde dostat bez toho, že bys zkoušel všechny kombinace. Pokud je to skutečně obrázek s vizuálním obsahem, tak je to celé nesmysl a prostě chybějící data jen nějak odhadni, jak už psal KIIV.

#5 Lisiak46
to vypadá jako oprava starých fotografií, chtělo by to více řádků okolo pokud chybí řádek dole tak 3-5 nad a pokud není úplně dole tak pár 1-3 pod. Pak by se dala provést nějaká analýza po blocích XxX pixelů s různými úrovněmi překrývání a tím najít v rozumném čase několik nejpravděpodobnějších kombinací.

caute, a keby sme vedeli nastavit pravidla , ze kolko x moze byt jeden pixel v riadku atd, vedelo by to zmenit ten obrovsky pocet moznych kombinacií? 

Mohli by sme pridať tieto podmienky pre vygenerovaný riadok  :

-máme 4 rôzne pixely (farby)

1. pixelov musí byť 32

2. maximálny počet pixelov jednej farby je 12 pixelov 

3. za sebou možu ísť najviac 4 rovnaké pixely jednej farby

4. ak za sebou idú 4 rovnaké pixely, viacej krát vo vygenerovanom riadku už za sebou ísť nemožu 4 pixely rovnakej farby

5. vo vygenerovanom riadku , možu ísť za sebou 3 rovnaké pixely, no najviac 2x v riadku ( na farbe nezaleží) napríklad :  3xčierna, 3xbiela 

- pomohli by tieto pravidlá drasticky znížiť počet možných kombinacií? 

#10 Lisiak46
ahoj.

Počet kombinací ty podmínky sníží hodně, ale stále je tu časová otázka generování kombinací a jejich testování. 

Rychlost by hodně záležela od způsobu generování kombinací. Jde o to, že pokud bys šel sekvenčně kombinace po kombinaci, lze některé vyřadit rychle, ale u jiných pak musíš analyzovat celý řádek.

Např pokud by sis generování 2x32b => 64b rozložil ,a generování 8B (8x 8b), celkem rychle vyřadíš kombinace, kdy se 1B skládá ze 4 stejných párů 00000000, 01010101, 10101010, 11111111 a B před končí  nebo B za začíná stejným párem, navíc se v tomto případě dá přeskočit relativně velká část kombinací v závislosti na pozici výskytu. U dalších bys pak musel porovnávat konce a začátky sousedících B., kolik stejných je na konci jednoho a na začátku druhého

Podle ceho poznas, ktera kombinace je ta spravna? Pokud je jen jedna ta spravna, pak by to melo jit vypocitat. Troufam si strelit na slepo, mozna i kosinovou transformaci, tu pouzivaji jpegy, takze by slo o ms pro 1 radek.

Ten seznam by sel ulozit do ram nebo ssd, to by asi nebyl problem s rychlosti. Tam ze lze bavit o rychlostech 3MB/s - 10G/s. Slo by teda o bezny HW nebo ve stovkach milionu :)