Matematické Fórum

Záleží, zda je kladeno omezení na délku takové posloupnosti. Pokud ne, volme takovou posloupnost, kde za sebe poskládejme číslice binárního zápisu přirozených čísel v jejich přirozeném pořadí, tj. 0,1,10,11,100. Pak je zřejmé, že se v takové posloupnosti vyksytne libovolná konečná podposloupnost tvořená z 0 a 1. A možná i kdyby bylo dáno omezení na délku takové posloupnosti, pak by i tato konstrukce mohla být užitečná. Případně volme jen taková přirozená čísla, jejichž binární kód má nějakou pevnou konstantní délku.

prave me napadlo zacit libobolnym retezcem napriklad jenom 0, pak zkouset postupne vsechny moznosti(0,1,00,01,10,11,000,001,010,011,100,...) a pokud nova moznost nebude nalezena v posloupnosti bude dopsana nakonec

priklad:
[0], dalsi v poradi je 1, ta se nevyskytuje, takze se dopise na konec
[01], dalsi v poradi je 00, ta se nevyskytuje, takze se dopise na konec
[0100], dalsi je 01,  ta se vyskytuje, nedeje se nic
[0100], dalsi je 10, ta se vyskytuje, nedeje se nic
[0100], dalsi je 11, ta se nevyskytuje, priradi se nakonec
[010011]

podle me by bylo mozne takto sestrojit generator pseudonahodnych cisel, z ruznych vstupu by vychazeli ruzne nekonecne retezce cisel

↑ ChazyK:Ahoj, myslím , že týmto si to vyriešil celkom definitívne, prirodzene to generuje od najjednoduchších zostáv až ďalej. Blahoželám.

Mne slo prave o to, vytvorit nekonecnej retezec, o kterem by se dalo rict, ze jeho prvnich napriklad 5 mist obsahuje vsechny mozne podretezce delky 2, prvnich treba 20 mist obsahuje vsechny mozne podretezce delky 3 atd. A potom vysledny algoritmus upravit, aby fungoval i na vice nez jednorozmerne retezce, napriklad na matice.

↑ musixx: pokusim se, v tehle vyrazech nejsem zrovna zbehlej :)
jinak pokusim se podivat po internetu po tech formalnich jazycich, jestli nahodou nenajdu to, o cem mluvil Pavel Brozek

Pokud chceme najít minimální posloupnost která obsahuje všechny řetězce délky (nejvýše) n, tak si sestavíme graf ze všech řetězců délky n-1, hrana vede vždy mezi řetězci bw a wb', kde b,b' jsou bity a w je řetězec délky n-2. Snadno nahlédneme, že graf je Eulerovský a Eulerovský tah v něm nám říká, jak danou posloupnost sestrojit (zapíšeme první řetězec a pak vždy poslední bit z řetězce, na který jsme došli). Toto jsme řešili ve škole na grafech a snad by se dalo dohledat a doklikat se k materiálům o opačném problému (kolik nejvýše různých podřetězců může obsahovat řetězec délky n) -- bohužel google nepomohl.

↑ Lukee: Díky za ChazyKa. "Superstring" bylo to, co se hledalo. A dá se o tom najít spousta zajímavých článků. V plné obecnosti je to NP těžký problém, což zasvěceným ledacos napoví. Dá se různě ustupovat z požadavků na "shortest". Zmíněno v tebou uvedeném odkazu, i s příklady nad obecnější abecedou než {0,1} třeba tady.