#!/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]]

% nacteni:
/* ['2.3_5.pl']. */

del1(A,[A|T],T).
del1(A,[H|T1],[H|T2]) :- del1(A,T1,T2).

insert(A,L,[A|L]).
insert(A,[H|T1],[H|T2]):- insert(A,T1,T2).

perm1([],[]).
perm1([H|T],L):- perm1(T,V), insert(H,V,L).

perm2([],[]).
perm2(L,[X|P]) :- del1(X,L,L1),perm2(L1,P).

perm3([],[]).
perm3(L,[H|T]):- append(A,[H|B],L),append(A,B,L1), perm3(L1,T).

% demonstracni vypis

  % abychom se vyhli varovanim "Redefined static procedure ..."
:- dynamic
       write_all_X/3,
       start/0.
       
write_all_X(Goal,X,Name):-
            call(Goal),write('  '),write(Name),write(' = '),write(X),nl,fail.
write_all_X(_,_,_).

start:- 
    write('Prace se seznamy - permutace'),nl,
    write('-------------------------------'),nl,
    write('perm1 napsany pomoci insert, vysledek volani "perm1([1,2,3],L)" :'), 
    nl, write_all_X(perm1([1,2,3],L), L, 'L'),nl,

    write('Pro blizsi porozumneni si vyzkousejte perm1, perm2 (reseny '), nl, 
    write('pomoci del1) a perm3 (s append) s trasovanim, napr. takto:'), nl,
    write('trace, perm1([1,2,3],L).'),nl,
    write('Pozn.: Po vypsani prvniho vysledku si dalsi vyzadate stisnutim ";"').
?-start.

:- retractall(write_all_X/3).
:- retractall(start/0).

Prace se seznamy - permutace
-------------------------------
perm1 napsany pomoci insert, vysledek volani "perm1([1,2,3],L)" :
  L = [1,2,3]
  L = [2,1,3]
  L = [2,3,1]
  L = [1,3,2]
  L = [3,1,2]
  L = [3,2,1]

Pro blizsi porozumneni si vyzkousejte perm1, perm2 (reseny 
pomoci del1) a perm3 (s append) s trasovanim, napr. takto:
trace, perm1([1,2,3],L).
Pozn.: Po vypsani prvniho vysledku si dalsi vyzadate stisnutim ";"