Řazení slov na styl slovního fotbalu – Python – Fórum – Programujte.com

Dobrý den
Mám takový problém byl by tu někdo, kdo by poradil algoritmus pro nejrychlejší seřazení slov na stylu slovního fotbalu? Mám soubor se 100 slovy délkou od 2-1000 znaků a furt nemůžu přijít na nejrychlejší řešení. Zatím to je tak že vezmu všechna slova a následně procházím zbylá a koukám jestli by se daly přidat před nebo za text(již seřazená slova). Jde mi jen o to zda jdou tato slova seřadit nebo ne.
Předem děkuji za odpovědi.

Podle toho, co s tím chceš dělat. Můžeš si to třeba rozhodit do mapy:

slovnik = {
    "ak": ["akat", "akvarium", ...],
    "ba": ["babicka", "babovka", ...],
    ...
}

import random
import urllib.request


def main():
    with urllib.request.urlopen("https://pastebin.com/raw/7uPetKWh") as f:
        slova = f.read().decode().splitlines()

    # >>>
    slovnik = {}
    for slovo in slova:
        slovnik.setdefault(slovo[:2], []).append(slovo)
    # <<<

    def dalsi(slovo=None):
        key = random.choice(list(slovnik.keys())) if not slovo else slovo[-2:]
        moznosti = slovnik.get(key)
        return moznosti.pop() if moznosti else None

    for _ in range(10):
        slovo = dalsi()
        while slovo:
            print(slovo, end=" ")
            slovo = dalsi(slovo)
        print("<konec>")


if __name__ == "__main__":
    main()

#2 gna
jo chci s tím dělat to že dostanu seznam slov a následně mám zjistit zda je možné tato slova seřadit na způsob slovního fotbalu, tak aby to byl co nejrychlejší algoritmus Přičemž můžu dostat až 100 000 slov

#2 gna
a tento slovní fotbal zajímá pouze jestli je první písmeno následujícího slova stejné jako poslední písmeno předchozího slova. tedy mě ve finále nezajímá co je to za slovo jelikož mě zajímá jen první a poslední písmeno od každého slova.

Já v tom vidím cyklický graf a takové úlohy nejde řešit rychle. 100 000 slov nestihneš před vyhynutím lidstva.

Nejsou tam ještě nějaká "optimalizující" omezení?

Ja myslim, ze gna ti hned prvni reakci rekl vse, co potrebujes vedet a tys to doresil v prispevku #4, ze te zajima jen prvni a posledni pismeno.
- Vemes seznam slov.
- Roztridis je do skupin/slovniku prvni pismeno. "s": ["Strom", "Sanitka", ...],
- A pak pouzivas agoritmus vsech kombinaci. Vyhledavas ve slovniku skupinu zacinajici poslednim pismenem slova. A vyzkousis vsechna slova.

Bohuzel, protoze pouzivas algoritmus vsech moznosti, hledani nejkratsi cesty, tak na 100.000 slov muzes zapomenout :)

Ale, mozna by se to dalo jeste urychlis, ze si do toho slovniku ulozis skupinku [slovo, posledni pismenko], at to nemusis stale zjistovat
"s": [ ["Strom","m"], ["Sanitka","a"], ...],

#5 - "100 000 slov nestihneš před vyhynutím lidstva."
Ve skutecnosti tato veta radu let uz neplati. Existuji viceprocesorova jadra a superpocitace. Pokud se kazde z miliardy jader zameri na jednu cestu... A ted nove existuji kvantove procesory, ktere se zameruji prave na takove ulohy. Je velmi pravdepodobne, ze lidstno par let jeste nevyhyne a dokaze postavit pocitace, ktere tu ulohu vyresi behem par sekund :)

to co hledáš se menuje vícedimenzionální RedBlackTree struktura ... ale odhaduju že to je nad tvoje současné možnosti.... takže to nemá smysl řešit

JerryM :) Ja treba vyhledavani nejkratsi trasy provadim pres 1 dimenzionalni pole. Cili, cely strom zapisuji velice jednoduse. Ale, mam jine zadani, takze se to neda pouzit presne na tohle a mam to v javascriptu. Takze, bych ho neplasil s nejakymi terminologiemi.
https://mlich.zam.slu.cz/js-ff/ff4b.htm

A taky se to neda pouzit pro 100.000 slov :)

RBTree se dá napsat i v JavaScriptu to je fuk ... ale koukám že máš docela chaos v tom co děláš :)

jinak další možnost je samozřejmě tabulka 256x26 s odkazem na náhodný prvek do skupiny List<String> po p9smenech a ... z, A..Z atd.

*tabulka 256x256

*písmenech

Jasně, způsob uložení těch slov je to, v čem je tady problém...

mužeš to udělat i jako hashovací tabulku na tisíc způsobů... přímé hashování, perfektní hashování atd .. atd. ..

jak říkám tohle je zatím nad tvoje schopnosti .. jinak by ses neptal ale udělal by si to .. .chápeš jo ? když se chceš jít vyčůrat tak taky nevoláš o pomoc ale zajdeš nahajzlík a rozepneš si poklopec a vyčůráš se ... chápeš jo ? :)

samozřejmě před tim čůráním musíš vystrčit bimbase z gatí :) :) :) :)  to dá rozum :)

#16 JerryM
Tady jde o to, ře se řešení dá najít jen vyzkoušením všech navazujících kombinací (v nejhorším případě) bez možnosti optimalizace. To v jaké struktuře bude mít ta slova je úplně šumák.

Tak si zastrč bimbase a běž zazimovat zahradu nebo něco jiného užitečného.

Jenom 100.000 ? Proč by to mělo trvat celý život? Zrovna dělám věci kde mám například 370.000.000 vět :-) s mnohem složitějšími kombinacemi než je tohle.

Protože téma není již aktuální tak se nebudu dlouze rozepisovat. Jen pro ostatní že 100.000 kombinací se da zvládnou jen za pomocí for, in, is, not, while, if a není třeba vymýšlet složitosti.

Faktem je že i mi trvalo asi 11 měsíců než jsem přišel na to, že žádný složitý kód nepotřebuji ale to je jíná pohádka...

Důležité je se zamyslet nad problémem proč je těch 100.000 kombinací složité a proč být vůbec nemusí.

Vždyť abeceda má jen pár písmen a například po písmenu "z" nelze napsat písmeno "z" nebo "g" nebo "w"

a každé písmeno má svá pravidla tím se hned možnosti a počet kombinací scvrkne :-)

Takže nějaká forma grafu, kde jen mezi některými uzly budou spoje? To co tady v nějaké formě napsal úplně každý? A není to 100k kombinací, ale 100k slov, což je mrtěmegamoc kombinací.

Tady jde o to najít v podstatě nejrychlejší algoritmus pro hledání nejdelší cesty grafem, tedy takové ve které se každý vrchol (slovo) vyskytuje právě jednou s návazností jako ve slovním fotbale tedy poslední písmeno aktuálního slova je schodné s prvním písmenem slova následujícího.

např.:   jana evangelium ahoj anastazie

rešení: ahoj jana anastazie evangelium

akorát na vstupu můžeš mít mnohem více slov my jsme měli 100k slov která se nadala takto sestavit a program my běžel do aleluja

Pokud je to reálný ukol z nějakého cvičeni, tak se dá předpokládat, že to teda asi bude řešitelné v rozumném čase i bez účasti na tajném čínském sympóziu o algoritmech minulý týden.

Možná česká slova opravdu mají takové parametry, že to nebude taková hrůzna, nebo je ten seznam pečlivě vybraný, nebo něco.

Zkus pogooglit a opsat nějaký z existujících algoritmů a uvidíš.