/**
 * 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_07_PermSort {

    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 isSorted(l: [Int]) -> Bool {
        zip(Array(l.dropLast()), Array(l.dropFirst())).filter({ (x, y) -> Bool in x > y }).count == 0
    }

    enum SortError: Error {
        case CannotSort
    }

    static func PermSort(l: [Int]) throws -> [Int] {
        for p in Perm(l: l) {
            if (isSorted(l: p)) {
                return p
            }
        }
        throw SortError.CannotSort
    }


    static func run() {
        let lst = [-1,5,3,6,7,-7]
        do {
            try print(PermSort(l: lst))
        } catch {
            print("Failed")
        }
    }
}