Stellen Sie sich einen geraden Fluss und eine Straße vor, die n- mal durch Brücken über den Fluss führt . Die Straße führt nicht auf sich selbst und ist unendlich lang. Diese Straße würde als offener Mäander angesehen werden. Ein offener Mäander ist eine offene Kurve, die sich nicht selbst schneidet und sich an beiden Enden unendlich erstreckt und eine Linie n- mal schneidet .

Ein gültiger Mäander kann vollständig durch die Reihenfolge der Kreuzungspunkte beschrieben werden, die er besucht.

Die Anzahl der unterschiedlichen Schnittmuster mit n Schnittpunkten, die ein Mäander sein kann, ist die n-te Mäanderzahl . Zum Beispiel ist n = 4:

Die ersten Zahlen dieser Sequenz sind:

1, 1, 1, 2, 3, 8, 14, 42, 81, 262, 538, 1828, 3926, 13820, 30694, 110954...

Dies ist die OEIS-Sequenz A005316 .

Herausforderung

Schreiben Sie ein Programm / eine Funktion , die eine positive ganze Zahl n als Eingabe verwendet und die n-te Mäanderzahl ausgibt .

Spezifikationen

• Es gelten die Standard-E / A-Regeln .
• Standardlücken sind verboten .
• Ihre Lösung kann entweder 0-indiziert oder 1-indiziert sein. Bitte geben Sie an, welche.
• Bei dieser Herausforderung geht es nicht darum, den kürzesten Ansatz in allen Sprachen zu finden, sondern darum, den kürzesten Ansatz in jeder Sprache zu finden .
• Ihr Code wird in Bytes bewertet , normalerweise in der Codierung UTF-8, sofern nicht anders angegeben.
• Eingebaute Funktionen, die diese Sequenz berechnen, sind zulässig jedoch empfohlen, eine Lösung zu verwenden, die nicht auf einer eingebauten basiert.
• Erklärungen, auch für "praktische" Sprachen, sind erwünscht .

Testfälle

Diese sind 0-indiziert. Beachten Sie, dass Sie keine so großen Zahlen verarbeiten müssen, wenn Ihre Sprache standardmäßig nicht unterstützt wird.

Input      Output

1          1
2          1
11         1828
14         30694
21         73424650
24         1649008456
31         5969806669034

In ein paar besseren Formaten:

1 2 11 14 21 24 31
1, 2, 11, 14, 21, 24, 31

Python 3 , 208 188 187 184 180 177 171 Bytes

lambda n:sum(all(i-j&1or(x<a<y)==(x<b<y)for(i,(a,b)),(j,(x,y))in d(enumerate(map(sorted,zip((0,)+p,p+(n,)))),2))for p in d(range(n)))
from itertools import*;d=permutations

Probieren Sie es online!

Jetzt 1-indiziert (war zuvor 0-indiziert, aber 1-indiziert sparte ein Byte aufgrund einer glücklichen Skurrilität in Bezug auf das Verhalten von Mäandern).

Erläuterung

Dies mag derselbe sein wie der von Jenny_mathy gepostete Link , aber ich habe die Zeitung nicht gelesen, also ist dies nur die Logik hinter meiner Methode.

Ich werde die folgende Abbildung in OEIS verwenden, um die Ergebnisse zu visualisieren.

Jeder gültige Mäander kann vollständig durch die Reihenfolge der Kreuzungspunkte beschrieben werden, die er besucht. Dies kann trivial im Bild beobachtet werden; Das Eingangssegment befindet sich immer auf der gleichen Seite (ansonsten wäre die Zahl doppelt). Wir können die Tendenz der Eingangs- und Ausgangssegmente zu ihren jeweiligen Unendlichkeiten darstellen, indem wir einfach zu jeder Reihenfolge einen Punkt auf jeder Seite hinzufügen - das heißt, die Reihenfolge (2, 1, 0)würde sich ändern (-1, 2, 1, 0, 3).

Vor diesem Hintergrund besteht die Aufgabe darin, die Anzahl der Ordnungen oder Permutationen des Bereichs bis zu zu finden n, die sich nicht mit sich selbst überschneiden. Schnittpunkte sind nur ein Problem zwischen Punktpaaren, bei denen das Verbindungssegment auf derselben Seite liegt. Für zwei aufeinanderfolgende Punktpaare in einer Permutation, deren Segmente eine Seite gemeinsam haben, ist es gleichbedeutend damit, ob einer und nur einer der Punkte eines Paares zwischen den beiden Elementen des anderen Paares liegt. Als solches können wir bestimmen, ob eine Reihenfolge gültig ist, indem wir feststellen, ob es keine Paare mit einem Punkt gibt, die in einem anderen Paar mit einem Segment auf derselben Seite enthalten sind.

Nachdem die Gültigkeit jeder Permutation bestimmt wurde, läuft die Ausgabe der Funktion auf die Anzahl der Permutationen hinaus, die als gültig befunden wurden.

Haskell , 199 Bytes

1!x=x
-1!(-1:x)=1:x
n!(i:x)=i:(n-i)!x
0#([],[])=1
0#_=0
n#(a,b)=sum$((n-1)#)<$>(-1:a,-1:b):[(a,-i:b)|i:a<-[a]]++[(-j:a,b)|j:b<-[b]]++[(j!a,i!b)|i:a<-[a],j:b<-[b],i+j>=0]
f n=n#([],[-1,1])+n#([1],[1])

Probieren Sie es online!

Basierend auf einer Erweiterung der Ideen in Iwan Jensen, Aufzählungen von Ebenenmäandern , 1999 auf den Fall offener Mäander. Dies durchläuft n = 1,…, 16 in ungefähr 20 Sekunden auf TIO.

APL (Dyalog Classic) , 127 - 115 Byte

⊃⊃⌽{↓⍉(⊃,/c),∘(+/)⌸(≢¨c←{1↓¨⍳¨⍨0,¨((×2↑¯1⌽⍵)/¯1 1⌽¨⊂⍵),(⊂∊#⍵#),(××/m,≠/m)/⊂1↓¯1↓(⊢-⍵×~)⍵∊m←2↑¯1⌽⍵}¨⊃⍵)/⊃⌽⍵}⍣⎕⌽1,⊂⍳2

Probieren Sie es online!