/**
 * Beispiel aus
 *
 * - Algorithmen und Datenstrukturen für Dummies
 *   - von Andreas Gogol-Döring und Thomas Letschert
 *   - Verlag Wiley-VCH; Oktober 2019
 *  - Kapitel 11, Probleme totschlagen
 *
 * @author A. Gogol-Döring, Th. Letschert
 */

import Foundation

struct AuD_11_11_VertexCoverNonDeterministicSearch {

    /*
     * Ein Algorithmus ist nichtdeterministisch, wenn sein Verhalten nicht komplett von der Eingabe bestimmt
     * wird und noch andere nicht vorhersehbare, externe, oder auch zufällige Informationen oder Ereignisse den
     * Ablauf bestimmen.
     *
     * Was genau ist nun an VertexCoverNonDet nichtdeterministisch und wie implementiert man das?
     * Diese Frage kann leicht zu Verwirrung und Konfusion führen, die aber vermieden werden kann, wenn sich zwei
     * Dinge klar macht:
     *
     *   - Der Nichtdeterminismus, um den es bei der Problemklasse NP geht, hat nichts mit
     *     Zufall oder zu tun. Randomisierte Algoruthmen überlassen manche Entscheidungen dem Zufall.
     *     Das ist aber ein komplett anderes Thema.
     *
     *   - Das Konstrukt nichtdeterministischer Algorithmus wird zur Definition der Komplexitätsklasse
     *     NP verwendet, also zur Abgrenzunge einer Klasse von Problemen(!).
     *     Ein nichtdetermisticher Algorithmus ist eine Erweiterung (!) des Begriffs von Algorithmus.
     *     Ein Algorithmus ist auch einen nichtdeterministischer Algorithmus. Umgekehrt ist ein
     *     nichtdeterministischer Algorithmus unter Umständen kein Algorithmus. (Algorithmen müssen
     *     determiniert sein.)
     *
     * Angenommen wir haben ein Entscheidungs-Problem D und für jede Eingabe x, für die D(x) wahr ist,
     * können wir mit einem exponentiellen Algorithmus Check prüfen, ob die Antwort korrekt ist,
     * dann haben wir es mit einem Problem in NP zu tun.
     *
     * Natürlich brauchen wir x nicht mehr zu prüfen, wenn wir wissen, dass D(x) gilt.
     * Wir können aber irgendein x Check prüfen, und wenn D(x) gilt, dann wird Check in polynomieller Zeit
     * die Prüfung mit einer positiven Bewertung abschließen.
     *
     * Diese Idee bringt der nicht-deterministische Algorithmus VertexCoverNonDet zum Ausdruck.
     * Das - nicht weniger, aber auch nicht mehr.
     *
     * Ein solcher nichtdeterministischer Algorithmus kann darüber hinaus (!) auch auf unterschiedliche Arten als
     * (richtiger, deterministischer) Algorithmus (zur Berechnung) eines x mit D(x) gedeutet (!) werden. Etwa so:
     *
     *  Berechne ein x für das D(x) gilt:
     *
     *   - Schritt 1: Rate (irgendein) ein x
     *   - Schritt 2: Prüfe das x und wenn es die Prüfung besteht (die in diesem Fall polynomiell ist),
     *     liefere es aus.
     *
     *  Dieser ``Algorithmus'' liefert das gewünschte Ergebnis nur dann, wenn zufällig ein richtiges x geraten wird.
     *
     * Eine andere Interpretation ist:
     *
     * Berechne ein x für das D(x) gilt:
     *
     *   - Schritt 1: Rate ein x für das Dx gilt (also rate gleich etwas richtiges)
     *   - Schritt 2: Prüfe das x (in polynomieller Zeit) und liefere es aus.
     *
     * Dieser ``Algorithmus'' beruht auf der magischen Fähigkeit ein richtiges x zu raten.
     *
     * Ein nichtdeterministischer Algorithmus ist aber kein Algorithmus, der würfelt, in der Hoffnung das Richtige
     * zu würfeln. Er ist auch kein Algorithmus, der er magische Fähigkeit hat.
     * Algorithmen haben grundsätzlich keine magische Fähigkeiten.
     *
     * Eingabe bei VertexCoverNonDet ist der Graph in Form seiner Knoten und Kanten und k.
     * S ist das richtig geratene x, ein Beleg oder Zeuge dafür, dass eine Abdeckung existiert.
     * Wenn dieser Zeuge in polynomieller Zeit geprüft werden kann, dann muss sein Größe polynomiell in der Größe der
     * Eingabe beschränkt sein. Das ist hier zweifellos der Fall. Eine Auswahl an Knoten ist linear abhängig v
     * on der Größe des Graphen.
     *
     * Wenn wir das umgekehrte Entscheidungsproblem betrachten: `` Es gibt keine Abdeckung mit k Knoten´´,
     * dann hätten wir es mit Zeugen von ganz anderem Kaliber zu tun. Wir müssten alle (!) Teilmengen mit k Knoten
     * bringen und zeigen, dass  jede von ihnen keine Abdeckung darstellt.
     *
     * Eine Menge M mit n Elementen hat (n über k) Teilmengen mit k Elementen, also exponentiell viele!
     * Also: Nix mehr mit Prüfung in polynomieller Zeit.
     *
     * Ein nichtdeterministische Algorithmus dient der exakten Definition der Klasse von Problemen deren Lösungen
     * polynomiell in der Größe des Problems beschränkt sind und die in polynomieller
     * Zeit geprüft werden können. Das sind schwierige Probleme mit vergleichsweise einfachen Lösungen.
     *
     * Auch wenn ein nichtdeterministische Algorithmus kein Algorithmus ist, so kann er doch mit einem
     * Algorithmus für eine sehr spezielle Art von hypothetischem Computer in Verbindung gebracht werden.
     * Das ist ein Computer der an Entscheidungstellen wahlweise entweder
     *
     *   - durch eine magische äußere Eingebung die richtige Wahl treffen, oder
     *   - alle Verzweigungen gleichzeitig ausführen kann.
     *
     * Beides kann durch ein ``richtigen Algorithmus'' emuliert werden. Die magische Eingebung kann durch eine Suche
     * nach der richtigen Entscheidung ersetzt werden.
     * Das gleichzeitig alle Verzweigungen ausführen kann durch Parallelverarbeitung nachgebildet werden.
     *
     * Die Suche und die Parallelverarbeitung kommen mit Zusatzkosten. Sie sind darum keine Implementierungen des
     * nichtdeterministischen Algorithmus sondern nur Emulationen.
     *
     * Betrachten wir die Suchvariante. Dazu müssen alle Teilmengen einer Menge untersucht werden
     * In Kapitel 8 haben wir diese Problemstellung bei Lösung des Rucksackproblems mit roher Kraft schon einmal
     * betrachtet.
     *
     * Eine Lösung mit Iteratoren forderet nicht ummäßig viel Speicherplatz:
     */


    // Alle Teillisten euner Liste ohne Berücksichtigung der Reihenfolge
    // kann als Generator der als Listen repräsentierten Teilmengen verwendet werden

    struct AllSubListsK<A>: Sequence {
        var sublistIterator: SublistIterator = SublistIterator()

        init(_ lst: [A], _ k: Int) {
            self.sublistIterator = mkIterator(lst, k)
        }

        class SublistIterator: IteratorProtocol {
            func next() -> [A]? {
                return nil
            }
        }

        class EmptyListSublistIterator: SublistIterator {
            var firstCall: Bool = true
            override func next() -> [A]? {
                if firstCall {
                    firstCall = false
                    return []
                } else {
                    return nil
                }
            }
        }

        class ConcatSublistIterator: SublistIterator {
            let first: SublistIterator
            let second: SublistIterator

            init(_ first: SublistIterator, _ second: SublistIterator) {
                self.first = first
                self.second = second
            }

            override func next() -> [A]? {
                return first.next() ?? second.next()
            }
        }

        class MapedSublistIterator : SublistIterator {
            let iter: SublistIterator
            let f: ([A]) -> [A]

            init (_ iter: SublistIterator, _ f: @escaping ([A]) -> [A]) {
                self.iter = iter
                self.f = f
            }

            override func next() -> [A]? {
                if let nextval = iter.next() {
                    return f(nextval)
                } else {
                    return nil
                }
            }
        }

        func mkIterator(_ lst: [A], _ k: Int) -> SublistIterator {
            if k == 0 {
                return EmptyListSublistIterator()
            } else if k > lst.count {
                return SublistIterator()
            } else {
                let head: A = lst.first!
                let tail: [A] = Array(lst.dropFirst())
                let f : ([A]) -> [A] = { (a: [A]) -> [A] in [head] + a }
                return ConcatSublistIterator(
                    mkIterator(tail, k),
                    MapedSublistIterator(mkIterator(tail, k-1), f)
                )
            }
        }

        func makeIterator() -> SublistIterator {
            return self.sublistIterator
        }

    }

    /*
     * Damit haben wir alles beisammen für eine ``Implementierung'' (betonte Anführungsstriche!)
     * des nichtdeterministione Algorithmus VertexCoverNonDet mit erschöpfender Suche:
     */

    static func VertexCoverNonDetSearch<VT: Equatable>(_ V: [VT], _ E: [(VT, VT)], _ k: Int) -> Bool {
        for s in AllSubListsK(V, k) {
            if (E.filter( { (u, v) in (!s.contains(u)) && (!s.contains(v)) } ).count == 0 ) {
                return true
            }
        }
        return false
    }

    static let V = (0 ... 45)

    // Der Irrgarten aus Kapitel 11
    static let E1: [(Int, Int)] = [
        (0,1),
        (1,3), (4,5), (6,7),
        (3, 9), (4, 10), (5,13), (6,14), (7,17),
        (8,9), (10,11), (13,14), (16,17),
        (1,18), (11,22), (14, 25),
        (18, 19), (20,21), (22,24), (25,26),
        (19, 29), (20,30), (22,32), (24,33), (16, 36), (27, 37),
        (28, 29), (29,30), (31,32), (33,34), (35,36), (36,37),
        (28, 38), (31,39), (32,40), (35,43),
        (38, 39), (40, 41), (42,43), (43, 44),
        (44,45),
        // Zykel:
        (8, 19),
        // Abkuerzung:
        (9, 10)]

    // reflexiver Abschluss
    static let E = E1.flatMap ( { (s,d) in [(s, d), (d,s)]} )

    static let start = 0
    static let dest = 45


    static func run() {  // das wird dauern, sehr sehr lange dauern
       for k in 2 ... 46 {
            print("k = \(k) => \(VertexCoverNonDetSearch(Array(V), E1, k))")
        }
    }

}