Schwalbenschwanz-Iteration über unendliche Listen in Haskell

Es gibt eine Monade dafür, Omega .

Mit seinen anwendungsspezifischen Funktionen können Sie zu beliebigen Tupeln verallgemeinern:

Aber : Das allein eliminiert natürlich nicht die Duplizierung. Es gibt Ihnen nur die richtige Diagonalisierung. Vielleicht könnten Sie monad comprehensions zusammen mit ein Ansatz wie Thomas, oder nur ein anderer mfilter pass (in diesem Fall auf b /= c beschränkt).

List comprehensions sind großartige (und prägnante) Wege, um solche Probleme zu lösen. Zuerst wissen Sie, dass Sie alle Kombinationen von (a,b,c) möchten, die a^2 + b^2 = c^2 erfüllen könnten - eine hilfreiche Beobachtung ist, dass (unter Berücksichtigung nur positiver Zahlen) immer a <= c && b <= c gilt.

Um unsere Kandidatenliste zu erstellen, können wir c range von 1 bis unendlich angeben, während a und b von 1 bis c reichen.

Um zu der Lösung zu kommen, müssen wir nur Ihre gewünschte Gleichung als Wächter hinzufügen:

Dies ist ineffizient, aber die Ausgabe ist korrekt:

Es gibt mehr prinzipielle Methoden als blinde Tests, die dieses Problem lösen können.

{- Es kommt darauf an, was "klein" ist. Aber hier ist eine Lösung für ein Konzept von "kleinsten", wenn Tupel zuerst durch ihre max verglichen wurden. Nummer und dann nach ihrer Gesamtsumme. (Sie können einfach meine ganze Antwort in eine Datei kopieren und einfügen, während ich den Text in Kommentare schreibe.)

Wir werden später nub brauchen. -}

{- Nur zur Veranschaulichung: der einfache Fall mit 2-Tupel. -}

{- Um alle Ergebnisse zu erhalten, müssen Sie den Flip jedes Tupels in den Stream einfügen. Aber machen wir das später und verallgemeinern Sie zuerst.

Das Erstellen von Tupeln beliebiger Länge ist etwas schwierig, daher werden wir an Listen arbeiten. Ich nenne sie "kList's", wenn sie eine Länge "k" haben. -}

{- Der nächste Schritt ist das Rotieren dieser Listen, denn bis jetzt ist die größte Zahl immer an der letzten Stelle. Wir schauen uns also alle Rotationen an, um alle Ergebnisse zu erhalten. Die Verwendung von nub ist hier zwar umständlich, aber Sie können das verbessern. Aber ohne sie werden Listen, in denen alle Elemente gleich sind, k mal wiederholt. -}

{- Es bleibt übrig, diese Listen in Tupel zu konvertieren. Dies ist ein wenig peinlich, da jedes n-Tupel ein separater Typ ist. Aber es ist natürlich geradlinig. -}

{- Einige Tests:

Bearbeiten: Mir wurde klar, dass es einen Bug gibt: Das Drehen der geordneten Listen ist natürlich nicht genug. Die Lösung muss in etwa so aussehen wie

in kLists , aber dann treten einige Probleme mit wiederholten Ausgaben auf. Sie können das herausfinden, denke ich. ;-)  -}

Diese Antwort ist für ein allgemeineres Problem für ein unbekanntes Prädikat. Wenn das Prädikat bekannt ist, sind effizientere Lösungen möglich, wie andere Lösungen basierend auf Wissen aufgelistet haben, die nicht für alle Inten für ein gegebenes c durchlaufen werden müssen.

Wenn Sie mit unendlichen Listen arbeiten, müssen Sie die erste Suche nach Lösung durchführen. Das Listenverständnis bietet nur eine Tiefensuche, weshalb Sie in Ihrem ursprünglichen Code niemals eine Lösung finden.

counters generiert alle möglichen Zähler für Werte aus dem angegebenen Bereich von Ziffern, einschließlich eines unendlichen Bereichs.

Zuerst erhalten wir eine Liste von Generatoren gültiger Kombinationen von Zählern - kombinieren Sie sie für jede erlaubte Zahl mit allen erlaubten Kombinationen für Zähler kleinerer Größe. Dies kann zu einem Generator führen, der eine unendliche Anzahl von Kombinationen erzeugt. Also müssen wir von jedem Generator gleichmäßig borgen.

So gens ist eine Liste von Generatoren. Stellen Sie sich dies als eine Liste aller Zähler vor, die mit einer Ziffer beginnen: gens !! 0 ist eine Liste aller Zähler beginnend mit 1 , gens !! 1 ist eine Liste aller Zähler beginnend mit 2 , etc.

Um von jedem Generator gleichmäßig zu borgen, könnten wir die Liste der Generatoren transponieren - so würden wir eine Liste der ersten Elemente der Generatoren bekommen, gefolgt von einer Liste der zweiten Elemente der Generatoren, usw.

Da die Liste der Generatoren unendlich sein kann, können wir es uns nicht leisten, die Liste der Generatoren zu transponieren, weil wir nie das zweite Element eines Generators betrachten können (für eine unendliche Anzahl von Ziffern hätten wir eine unendliche Zahl) von Generatoren). Also, wir zählen die Elemente von den Generatoren "diagonal" - nehmen das erste Element vom ersten Generator; nimm dann das zweite Element vom ersten Generator und das erste vom zweiten Generator; dann nimm das dritte Element vom ersten Generator, das zweite vom zweiten Generator und das erste Element vom dritten Generator, etc. Das kann man tun, indem man die Liste der Generatoren mit der Funktion f faltet, die zwei Listen zusammenfügt - eine Liste ist der Generator, die andere ist die bereits gezippten Generatoren - der Anfang von einem von ihnen wird um einen Schritt versetzt, indem []: zum Kopf hinzugefügt wird. Das ist fast zipWith (:) ys ([]:n) - der Unterschied ist, dass, wenn n oder ys kürzer ist als der andere, wir den Rest der anderen Liste nicht löschen. Beachten Sie, dass die Faltung mit zipWith (:) ys n eine Transponierte wäre.

Für diese Antwort werde ich "kleinste" nehmen, um auf die Summe der Zahlen im Tupel zu verweisen.

Um alle möglichen Paare in der Reihenfolge aufzulisten, können Sie zuerst alle Paare mit einer Summe von 2, dann alle Paare mit einer Summe von 3 und so weiter auflisten. In Code

Haskell verfügt nicht über Funktionen zum Umgang mit n-Tupeln, ohne Template Haskell zu verwenden. Um dies zu verallgemeinern, müssen Sie zu Listen wechseln.

Hier ist eine andere Lösung, wahrscheinlich mit einer etwas anderen Idee von "klein". Meine Reihenfolge ist nur "alle Tupel mit Max Element N kommen vor allen Tupeln mit Max Element N + 1". Ich habe die Versionen für Paare und Tripel geschrieben:

Sie können es nicht wirklich auf N-Tupel verallgemeinern. Solange Sie jedoch homogen bleiben, können Sie es möglicherweise verallgemeinern, wenn Sie Arrays verwenden. Aber ich möchte mein Gehirn nicht an diesen Knoten binden.

Es hängt wirklich davon ab, was du mit "klein" meinst, aber ich nehme an, dass du ein Tupel von Zahlen in Bezug auf sein maximales Element finden willst - also (2,2) ist kleiner als (1,3) (während Standard-Haskell-Ordnung lexikographisch ist) ).

Es gibt ein Paket data-ordlist , das genau auf das Arbeiten mit geordneten Listen ausgerichtet ist. Es ist die Funktion mergeAll < Mit / a> (und mergeAllBy ) können Sie eine zweidimensionale Matrix, die in jeder Richtung angeordnet ist, in eine geordnete Liste kombinieren.

Zuerst erstellen wir eine gewünschte Vergleichsfunktion für Tupel:

Dann erstellen wir mit mergeAll eine Funktion, die einen Komparator, eine Kombinationsfunktion (die monoton sein muss) verwendet beide Argumente) und zwei sortierte Listen. Es kombiniert alle möglichen Elemente aus den beiden Listen mit der Funktion und erzeugt eine Ergebnisliste:

Mit dieser Funktion ist es sehr einfach Tupel zu erzeugen, die nach ihrem Maximum geordnet sind:

Die ersten 10 Elemente sind:

und wenn wir (zum Beispiel) nach dem ersten Paar suchen, dessen Quadratsumme gleich 65 ist:

wir erhalten das korrekte Ergebnis (4,7) (im Gegensatz zu (1,8) wenn lexikographische Sortierung verwendet wurde).

Ich denke, das ist die einfachste Lösung, wenn "klein" als x + y + z definiert ist, denn nachdem Sie Ihre erste Lösung im Raum von vollwertigen pythagoräischen Dreiecken gefunden haben, sind Ihre nächsten Lösungen aus der unendlichen Liste größer.

take 1 [(x,y,z) | y <- [1..], x <- [1..y], z <- [1..x], z*z + x*x == y*y] - & gt; [(4,5,3)]

Es hat die nette Eigenschaft, dass es jede symmetrisch einzigartige Lösung nur einmal zurückgibt. x und z sind ebenfalls unendlich, weil y unendlich ist.

Dies funktioniert nicht, weil die Sequenz für x niemals endet und Sie daher nie einen Wert für y erhalten, ganz zu schweigen von z. Der Generator ganz rechts ist die innerste Schleife.

take 1 [(z,y,x)|z <- [1..],y <- [1..],x <- [1..],x*x + y*y == z*z]

Sry, es ist schon eine Weile her, dass ich Haskell gemacht habe, also werde ich es mit Worten beschreiben.

Wie ich in meinem Kommentar darauf hingewiesen habe. Es ist nicht möglich, das kleinste in einer unendlichen Liste zu finden, da es immer ein kleineres geben könnte.

Was Sie tun können, ist ein streambasierter Ansatz, der die Listen übernimmt und eine Liste mit nur 'gültigen' Elementen zurückgibt, d. e. wo die Bedingung erfüllt ist. Rufen wir diese Funktion triangle

Sie können dann die Dreiecksliste einigermaßen mit take n (triangle ...) berechnen und von diesen n elements können Sie das minium finden.