/**
 * Beispiel aus
 *
 * - Algorithmen und Datenstrukturen für Dummies
 *   - von Andreas Gogol-Döring und Thomas Letschert
 *   - Verlag Wiley-VCH; Oktober 2019
 *  - Kapitel 4, Listen: Immer einer nach dem anderen
 *
 * @author A. Gogol-Döring, Th. Letschert
 */

import Foundation

struct AuD_04_06_Permutationen {

    static func Perm<T>(l: [T]) -> [[T]] {
        if (l.count == 0) {
            return [[]]
        } else {
            let x = l[0]
            let rest = Array(l.dropFirst())
            return Ins(x: x, L: Perm(l: rest))
        }
    }

    static func Ins<T>(x: T, L: [[T]]) -> [ [T] ] {
        L.flatMap( { ll in InsH(x: x,  l: ll) } )
    }

    static func InsH<T>(x: T, l: [T]) -> [[T]] {
        if (l.count == 0) {
            return [[x]]
        } else {
            let h = l[0]
            let tail = Array(l.dropFirst())
            return [[x] + l] + InsH(x: x, l: tail).map( { l1 in [h] + l1} )
        }
    }

    static func run() {
        let lst = ["a", "b", "c"]
        let perms = Perm(l: lst)
        print(perms.map( {l in l.joined(separator: ", ") }).joined(separator: "\n"))
    }

}