Keskustelu: Ohjelmointikysymykset: Python: Listan alkioiden järjestelyä Pythonilla

Kuinka saisin tehtyä ohjelman, joka muodostaa annetun listan alkioista kaikki mahdolliset järjestykset. Alkioiden määrää ei tunneta.
Eli esim.

[a,b,c]
[a,c,b]
[b,a,c]
[b,c,a]
[c,a,b]
[c,b,a]

Rekursio on aina yksi tapa.

Tässä on esimerkki:

def perm(lista, tulos):
    if len(lista) == len(tulos):
        print tulos
        return
    for alkio in lista:
        if alkio not in tulos:
            perm(lista, tulos + [alkio])

perm(['a', 'b', 'c'], [])

Funktio perm valitsee listasta yhden alkion, joka ei ole vielä tuloslistassa. Sitten funktio perm kutsuu itseään uudestaan. Kun tuloslistan pituus on yhtä suuri kuin alkuperäisen listan pituus, yksi permutaatio on valmis.

Aikasta elegantti ratkaisu etten sanoisi.
Kiitän ja kumarran.

Tämä olisi kaksi riviä Haskellilla, mutta minun Python-taitoni eivät riittäneet ihan yhtä eleganttiin ratkaisuun. Ehkä ei pitäisi matkia aivoja jalostavaa Haskell-kieltä, vaan tehdä asiat oikein Python-tavalla. Tässä kuitenkin väärä tapa, joka sentään hoitaa duplikaatit oikein, eikä tukehdu tyhjään listaankaan.

Generaattorien käyttö mahdollistaa isonkin joukon alun katselun. Vielä voisi laajentaa käsittelyä kaikkien osajoukkojen permutaatioihin, mutta sitä ei ole tässä.

#!/usr/bin/env python
# tarvitaan set, eli Python 2.4 tai uudempi
# muuten seuraava voi auttaa

try:
    x = set
except NameError:
    from sets import Set as set
else:
    del x

def nub (list_):
  "Removes duplicates from a list, keeping order."
  seen = set()
  result = []
  for item in list_:
    if item not in seen:
      result.append(item)
      seen.add(item)
  return result

def deleted (list_, item):
  "Return a list with the first occurrence of item deleted."
  copy = list(list_)
  copy.remove(item)
  return copy

def perm_gen(list_):
  "Make a generator over the permutations of a list. Handles duplicates."
  # -- Haskell:
  # perms [] = [[]]
  # perms ls = [a:b | a <- nub ls, b <- perms $ delete a ls]
  #
  if len(list_)==0: return (nothing for nothing in [])
  if len(list_)==1: return ([item] for item in list_)
  return ([a]+b for a in nub(list_)
                for b in perm_gen(deleted(list_,a)))

# testaus

for p in perm_gen(list("ittna")):
  print "".join(p)

print "*"*40

count = 0
for p in perm_gen(list("ohjelmointiputka")):
  if count == 100: break
  count += 1
  print "".join(p)

print "*"*40
print "empty list"
for p in perm_gen([]):
  print p

print "program finished"

# eof

Erityisesti tuo tyhjän generaattorin idiomini on luultavasti ihan typerä (nollan pituisille listoille). Joku oikea Pythonisti kertokoon paremman tavan, jos sellainen on.

Taas esittelin julkisesti tyhmyyttäni. Oikeampi tapa:

def perm_gen(list_):
  "Make a generator over the permutations of a list. Handles duplicates."
  # -- Haskell:
  # perms [] = [[]]
  # perms ls = [a:b | a <- nub ls, b <- perms $ delete a ls]
  #
  if len(list_)==0: return (mt for mt in [[]])
#  if len(list_)==1: return ([item] for item in list_)
  return ([a]+b for a in nub(list_)
                for b in perm_gen(deleted(list_,a)))

Kommentoidun rivin voi poistaa kokonaan ja tyhjän listan permutaatiot voi käsitellä oikein. Johan se on oleellisesti sama ratkaisu molemmissa. Nub-funktiossa myös ei tarvitse käyttää set()-oliota, jos listat ovat lyhyitä. Alkiot voi tarkistaa myös result-listasta.

On se vain niin vaikea tajuta ero tyhjän listan ja listan, joka sisältää tyhjän listan välillä. Toivottavasti lukijaa ei tällainen hämmennys vaivaa.