#!/usr/bin/env python
# encoding=utf-8 (pep 0263)
from linked_lists import LinkedList, Cons, Nil
def del1_anyX(ys):
if ys == Nil:
return
yield (ys.head, ys.tail)
for (z, zs) in del1_anyX(ys.tail):
yield (z, Cons(ys.head, zs))
def insert(x, ys):
yield Cons(x, ys)
if not ys == Nil:
for zs in insert(x, ys.tail):
yield Cons(ys.head, zs)
def append(xs, ys):
if xs == Nil:
return ys
else:
return Cons(xs.head, append(xs.tail, ys))
def append_anyXsYs(zs):
yield ([], zs)
if zs != Nil:
for xs, ys in append_anyXsYs(zs.tail):
yield (Cons(zs.head, xs), ys)
def perm1(xs):
if xs == Nil:
yield Nil
else:
for ys in perm1(xs.tail):
for zs in insert(xs.head, ys):
yield zs
def perm2(xs):
if xs == Nil:
yield Nil
else:
for y, ys in del1_anyX(xs):
for zs in perm2(ys):
yield Cons(y, zs)
def perm3(xs):
if xs == Nil:
yield Nil
else:
for ys, zs in append_anyXsYs(xs):
if zs == Nil:
continue
qs = append(ys, zs.tail)
for ws in perm3(qs):
yield Cons(zs.head, ws)
# demonstracni vypis
if __name__ == "__main__":
print("Prace se seznamy - permutace")
print("-------------------------------\n")
print("perm1 napsany pomoci insert")
print("Vysledek volani perm1(LinkedList([1, 2, 3])): \n\t%s\n" % \
list(perm1(LinkedList([1, 2, 3]))))
print("perm2 napsany pomoci del1_anyX")
print("Vysledek volani perm2(LinkedList([1, 2, 3])): \n\t%s\n" % \
list(perm2(LinkedList([1, 2, 3]))))
print("perm3 napsany pomoci deleni a spojovani seznamu")
print("Vysledek volani perm3(LinkedList([1, 2, 3])): \n\t%s\n" % \
list(perm3(LinkedList([1, 2, 3]))))
Prace se seznamy - permutace
-------------------------------
perm1 napsany pomoci insert
Vysledek volani perm1(LinkedList([1, 2, 3])):
[[1, 2, 3], [2, 1, 3], [2, 3, 1], [1, 3, 2], [3, 1, 2], [3, 2, 1]]
perm2 napsany pomoci del1_anyX
Vysledek volani perm2(LinkedList([1, 2, 3])):
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
perm3 napsany pomoci deleni a spojovani seznamu
Vysledek volani perm3(LinkedList([1, 2, 3])):
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
|