Dotaz: Python, program na variace

[Milan Horacek]

Dobry den,

nevi prosim nekdo kde bych nasel, anebo je nekdo schopny napsat v pythonu nasledujici program:

1) Program bude generovat 8-miste retezce (co radek to retezec)

2) Retezce budou obsahovat pouze znaky a-z (mala pismena) a 0-9 (cisla)

3) V kazdem retezci se bude vyskytovat prave jedno cislo, zbytek budou male znaky

4) Program v libovolnem poradi vygeneruje VSECHNY mozne retezce splnujici body 1-3

Napadlo me to nejdriv resit tak, ze si vytvorim program na generovani permutaci bez opakovani s tim, ze budu generovat osmice z prvku a-z a 0-9 a kazdy vygenerovany retezec pote otestuji na podminku 3 a v pripade uspechu ho vypisu.

Myslite, ze takto by to slo udelat?

Potreboval bych tento problem vyresit v Pythonu, ale me programatorske schopnosti jsou nedostatecne. Nasla by se nejaka dobra duse, ktera by v ramci procviceni se v pythonu dany problem vyresila? Byl bych velice vdecny.

Jeste poznamka, nejedna se o zadani zadneho skolniho projektu, pouze se s kamaradem nemuzeme shodnout kolik takovych retezcu existuje a timto zpusobem si to chceme programove overit.

Odpovědi

[chrono]

Spočítať to je oveľa jednoduchšie, ako urobiť program. :)

[Milan Horacek]

Na to jsem prave taky prisel, proto pisu sem:) Ten program bych potreboval jak pro overeni vysledku tak pro inspiraci a dalsi upravy.

[Milan Horacek]

Zapomnel jsem tam jeste napsat jednu podstatnou podminku. Znaky se v ramci retezce nesmi opakovat.

[Petr Drlik]

V pythonu nedelam, ale umysl generovat neco a potom kontrolovat zdali, je scestny. Ja bych to pojal tak, ze bych generoval osmice znaku postupne. Prvni znak napr. cislo 0 a dalsi a, potom b atd. V podmince generovani kontrola na vyskyt pismena, ktere ale uz dopredu znam. Nedovedu si ale predstavit tu radu retezcu(jsem uz hodne, hodne dlouho ze skoly). Jen nevim, jak by to splnovalo podminku o libovolnem poradi. Potom se ale domnivam, ze zadavatel musel vedet, ze najiti vsech retezcu timto zpusobem by byla sysifovska prace. Ke konci generovani by trvalo nekonecne dlouho, nez by narazil na retezec, ktery jeste vygenerovan neni.

[NdrU]

Není potřeba nic kontrolovat. Můžeme vzít množinu písmen a-z (python má přímo datový typ set) a v sedmi zanořených for cyklech vždy vzít jedno písmeno z množiny, přidat ho do slova, a vytvořit novou množinu, která bude menší o to konkrétní písmeno. Přes tuto novou množinu bude iterovat další for a tak dále (případně by se to dalo samozřejmě udělat rekurzí, takhle je zřejmější, jak to funguje).
V těle posledního foru by se potom na všechna možná místa vzniklého slova vložila čísla 0-9 (což si vyžádá nejspíš další dva fory).

[chrono]

Nechce sa mi to skúšať, ale podľa mňa by takéto generovanie tých reťazcov trvalo strašne dlho.

[l4m4]

To je jedno. Bude to trvat věčnost, protože možností je 9 (vyberu číslo) * 8 (vyberu polohu čísla) * 26^7 (do zbytku umístím libovolně a-z), což je něco přes půl bilionu.

[chrono]

Tých reťazcov bude o niečo menej. Síce je tých čísel 10 a nie len 9, ale asi si si nevšimol tú doplňujúcu informáciu, že sa znaky nesmú opakovať (ale aj tak bude tých možností veľmi veľa).

[l4m4]

Teda, ať to čtu, jak to čtu, v

1) Program bude generovat 8-miste retezce (co radek to retezec)

2) Retezce budou obsahovat pouze znaky a-z (mala pismena) a 0-9 (cisla)

3) V kazdem retezci se bude vyskytovat prave jedno cislo, zbytek budou male znaky

žádnou podmínku o neopakování nevidím.

[chrono]

http://www.abclinuxu.cz/poradna/programovani/show/316065#2

[l4m4]

Aha. V tom případě je jich 10 * 8 * 26!/19!, což je něco přes čtvrt bilionu...

[detto]

A čo itertools ? Konkrétne permutations() a combinations().