Dotaz: náhrada rekurze v Pythonu ?

[Ivon]

Ahoj,

narazil jsem na problém a nevím jak se pohnout z místa :-/

K jedné úloze z teorie sítí potřebuju napsat funkci, která vrátí permutaci všech prvků seznamu, kterej se jí předá jako parametr. Ať jsem nad tím koumal jak chtěl, řešení vždycky vedlo k rekurzi. Problém nastane, pokud je seznam relativně velký. Program spadne na výjimku "RuntimeError: maximum recursion depth exceeded in cmp"

def permute(lst):
    if lst == []:
        return [[]]
    else:
        return [[el]+chunk for el in lst for chunk in permute([ x for x in lst if x != el])]

Dá se tý rekurzi nějak vyhnout nebo dá se spustit python s větším zásobníkem ?

Odpovědi

[Ivon]

Zapomněl jsem doplnit, že v seznamu nejsou duplicity. Z tý ukázky to je ale vidět.

[Dr. Eddy]

Ahoj,

muzes nejak vysvetlit, jak generujes permutaci nebo presne zadani? Python neumim, ale ten problem me zajima, a zajima me vic i kvuli tomu, ze by se to melo dat prepsat do cyklu...

[12345]

itertools.permutations?

[Ivon]

Díky. Vidím že se to obchází přes iterátory.

Na druhou stranu ten kód už nevypadá tak elegantně, resp. zatím se mi nepodařilo přesně vyčíst ten algoritmus. Nebyla by nějaká jednodušší verze ? Já vím, to už chci moc

[12345]

Obchází? To je elegantní koncept, ne obcházení . Ale každopádně jde o built-in modul v C, nic efektivnějšího už v Pythonu nenajdeš.

[Ivon]

Sry, mě jako neprogramátorovi to přišlo jako obcházení

Jo a můžu si za to sám, že si neprolezu standardní knihovny. Z toho itertools.permutations to leze opravdu fofrem.?

[l4m4]

Tvůj problém není přetečení zásobníku. Tvůj problém je, že generuješ seznam všech permutací, jehož velikost roste s počtem prvků jako nⁿ.

Nejjednodušší je použít itertools, jak radí kolega. Pokud si to chceš psát sám, tak si najdi, jak se permutace vygeneruje z jejího pořadového čísla (google, wikipedia, je to všude, a jde to i snadno vymyslet), takže můžeš generovat permutace po jedné, stejně jako to dělají itertools.

[Ivon]

Pokud odhlédnu od implementace, tak tahle úloha přece vede obecně k řešení n^n prvků ?

Ok, na to generování podle pořadového čísla se juknu. Díky.

[Ivon]

resp. n!/(n-k)!, což by v tomhle případě bylo n!/0! = n!

[l4m4]

Ano, pokud chceš projít všechny permutace z n prvků, tak jich bude n!.

Nicméně je dost rozdíl, zda přitom zaplácneš O(n) nebo O(n*n!) paměti.

[Filip Jirsák]

Rekurzi vždycky můžete nahradit tak, že si ten cyklus a zásobník napíšete sám. Ona to tedy technicky vzato pořád bude rekurze, ale už nebude omezená velikostí zásobníku volání, ale pouze velikostí vašeho zásobníku – a ten může zabrat celou paměť, můžete si ho klidně uložit na disk atd. Není to tedy jiný způsob řešení, pouze si pro rekurzi výrazně zvýšíte limity.

[lofcek]

Neviem, co sa Ti na iteratoroch nepaci - jedina zmena v tvojom programe je, ze namiesto zoznamu zoznamov vratim proste vzdy len zoznam. A je na iteratore aby si zapamatal, kde skoncil a pri nasledujucej iteracii vratil to, co ma.

A najma uspokojivo riesi pamatove naroky - povodny zoznam bude uz pre 6. mozno 7 unikatnych prvkov dost velky a iteratory funguju aj dalej bez vyrazneho spomalenia.

def permute(lst):
    if not lst:
        yield []
    else:
        for item in lst:
            for chunk in permute([x for x in lst if x != item]):
                yield [item] + chunk

Ak by som mal tento program vylepsovat, tak by som ho prepisal tak, aby nevratil iterovany zoznam zoznamov, ale iterovany zoznam toho co dostal na vstupe (cize ak agrumentom bude string - vratil by zoznam stringov, ak tuple, zoznam tuplov...)

[Ivon]

Nice, diky.

[Fuky]

$ cat permutations.py
#! /usr/bin/env python3                             

import sys
import itertools

for item in itertools.permutations(sys.argv[1:]):
    print("".join(item))
$ ./permutations.py A B C
ABC
ACB
BAC
BCA
CAB
CBA