Generieren Sie die SUDSI-Sequenz

15

Die SUDSI-Sequenz ( su m, d ifference, s wap, i increment) ist eine merkwürdige Ganzzahlsequenz, die ein ziemlich chaotisches Verhalten zu zeigen scheint. Es kann wie folgt generiert werden:

Lassen S eine unendliche Liste der natürlichen Zahlen sein: 1 2 3 4 5 6 .... Lassen S i die eine indizierte bezeichnen i - te Element von S . Also ist S 1 anfangs 1, S 2 ist 2 usw. (es gibt kein S 0 ).

Beginnend mit S 1 und S 2 ...

  • Berechnen Sie ihre Summe: sum = S1 + S2
  • Berechnen Sie ihre absolute Differenz (die größere minus die kleinere): diff = |S1 - S2|
  • Vertausche die beiden Werte in S mit den Indizes von Summe und Differenz:swap(Ssum, Sdiff)

  • Erhöhen Sie die Indizes von S, mit denen Sie arbeiten. Das nächste Mal werden Sie also die Summe und Differenz von S 2 und S 3 berechnen , und die Zeit danach wird S 3 und S 4 usw. sein.

  • Wiederholen Sie diesen Vorgang auf unbestimmte Zeit.

Hier sind die ersten Stufen von S, wie dieser Prozess angewendet wird. Die Klammern []umschließen die beiden Werte, die summiert und differenziert werden sollen.

Original S :

[1 2] 3 4 5 6 7 8 9 10 11 12 ...

Nachdem S 3 ( 3 = 1 + 2) und S 1 ( 1 = |1 - 2|) getauscht wurden:

3 [2 1] 4 5 6 7 8 9 10 11 12 ...

Nachdem S 3 und S 1 getauscht wurden:

1 2 [3 4] 5 6 7 8 9 10 11 12 ...

Nachdem S 7 und S 1 getauscht wurden:

7 2 3 [4 5] 6 1 8 9 10 11 12 ...

Nachdem S 9 und S 1 getauscht wurden:

9 2 3 4 [5 6] 1 8 7 10 11 12 ...

Nachdem S 11 und S 1 getauscht wurden:

11 2 3 4 5 [6 1] 8 7 10 9 12 ...

Nachdem S 7 und S 5 getauscht wurden:

11 2 3 4 1 6 [5 8] 7 10 9 12 ...

etc.

Die SUDSI-Sequenz ist definiert als die Sequenz der ersten Elemente in jeder dieser Listen. Die ersten Begriffe der SUDSI-Sequenz sind also 1 3 1 7 9 11 11.

Hier sind die ersten 200 Terme der SUDSI-Sequenz (20 pro Zeile):

1 3 1 7 9 11 11 11 15 15 19 19 19 19 19 19 19 19 19 19 
19 19 19 19 19 19 19 19 57 59 59 59 59 59 59 59 59 59 77 79 
81 83 85 87 89 91 91 91 91 91 91 91 91 91 91 91 91 91 115 115 
121 123 125 127 127 127 127 127 137 139 141 143 145 147 147 147 147 147 147 147 
147 147 147 147 167 167 167 167 167 167 167 167 167 167 167 167 167 167 167 167 
167 167 167 167 209 211 211 211 211 211 221 223 223 223 223 223 223 223 223 223 
223 223 243 243 243 243 243 243 257 259 261 263 263 263 263 263 263 263 263 263 
263 263 263 263 263 263 263 263 263 263 263 263 263 263 263 263 263 263 263 263 
263 263 325 327 329 331 331 331 331 331 331 331 331 331 349 351 351 351 351 351 
361 363 363 363 363 363 363 363 363 363 363 363 363 363 363 363 363 363 363 363

Es ist (zumindest für mich) unklar, wie man zukünftige Bedingungen vorhersagen könnte. Man kann nur mit Sicherheit sagen, dass die Ausdrücke immer ungerade und nicht abnehmend sind (nach dem zweiten Ausdruck) und dass einige Zahlen oft wiederholt werden.

Herausforderung

Schreiben Sie ein Programm oder eine Funktion, die eine positive Ganzzahl n aufnimmt und den n- ten Term der SUDSI-Sequenz ausgibt oder zurückgibt . Wenn zum Beispiel n 1 ist, ist die Ausgabe 1, wenn n 2 ist, ist die Ausgabe 3, wenn n 200 ist, ist die Ausgabe 363.

Nehmen Sie die Eingabe wie gewohnt vor (stdin / command line / function arg).
Die kürzeste Antwort in Bytes gewinnt.
(Diese Site codiert Dinge in UTF-8, aber Sie können jede beliebige vorhandene Codierung verwenden.)

Mathy-Bonus: (potenziell prämienberechtigt)

  • Erzähl mir mehr über die SUDSI-Sequenz. Was ist das zugrunde liegende Muster für welche Zahlen und wie viele davon gibt es (und ähnliches)? (SUDSI konnte ich übrigens auf OEIS nicht finden .)
Calvins Hobbys
quelle
Wie schon wieder. Besser nicht verknüpfen als Verwirrung über die Kodierung zu stiften.
Optimierer
@Optimizer Ich habe für mit der gleichen Formulierung zu diesem Bytezähler Verknüpfung Alter . Warum würde es plötzlich mehr Verwirrung stiften als jemals zuvor?
Calvins Hobbys
1
@orlp Ich denke, das wäre eine nette zusätzliche Funktion, aber ich persönlich bin darauf angewiesen, dass ich kopieren und einfügen kann, da ich selten Quelldateien für meine Einreichungen habe.
Martin Ender
1
@orlp Aber wer braucht das schon? Sie können die Größe direkt sehen, wenn sie die Datei hatten. Und es ist bei manchen Betriebssystemen nicht so einfach, den Zeilenumbruch am Ende zu entfernen.
Jimmy23013
2
@ MartinBüttner Mir war langweilig: meta.codegolf.stackexchange.com/questions/4944/…
orlp

Antworten:

5

Pyth, 45 41 40 38 Bytes

MXGH_HhugGm@Gtd,s<>GH2.a-@GH@GhHtQr1yQ

Mir ist (wie auch Martin Büttner) aufgefallen, dass die maximal betroffene Anzahl eines Permutationsschrittes bei kliegt 2k + 1. Da wir aber nur n - 1Schritte haben, brauchen wir nur eine Liste der Zahlen bis zu 2n - 1.

Probieren Sie es online aus: Demonstration

M                       define a function g(G, H): return
                        (G is the list of numbers, H is a tuple)
 XGH_H                     a translation of G
                           (replaces the elements in H with the elements in reversed H)
                           in this application it swaps two values in the list G


                        implicit: Q = input()
 u     tQr1yQ           reduce, G = [1, 2, ..., 2*Q-1]
                        for each H in [0, 1, ..., Q - 2]:
                           G = 
  gG...                        g(G, ...)
h                       print the first element of the resulting list

And the second argument ... of the function call g is:

     ,                  create the tuple (
      s<>GH2               sum(G[H:][:2]), 
            .a-@GH@GhH     abs(G[H],G[H+1])
                        )
m@Gtd                   and map each value d to G[d - 1]
Jakube
quelle
Gibt es ein Bußgeld für die Verwendung von Pyth außerhalb einer Bibliothek?
Alex A.
1
@ Alex A. Haha, nein. Aber es gibt eine, die Bücher nicht zurückgibt.
Jakube
18

Mathematica, 88 Bytes

Last[f@n_:=n;(r=f@1;{f@a,f@b}={f[b=+##],f[a=Abs[#-#2]]};r)&@@f/@{#,#+1}&/@Range@Input[]]

Dies ist ein vollständiges Programm, bei dem die Eingabe an einer Eingabeaufforderung gelesen wird. Es ist eine sehr direkte Implementierung der Definition, bei der ich die aktuelle Reihenfolge verfolge f(deren Werte f[n]standardmäßig "" sind)n ).

Hier ist eine etwas besser lesbare Version:

Last[
  f@n_ := n;
  (
    r = f@1;
    {f@a,f@b} = {f[b=+##],f[a=Abs[#-#2]]};
    r
  ) & @@ f /@ {#,#+1} & /@ Range @ Input[]
]

Einige Analysen

Ich habe die ersten 2000 Elemente der Sequenz gezeichnet (später wird es nicht wirklich interessanter):

Bildbeschreibung hier eingeben

Die Sequenz ist also im Wesentlichen linear mit der Steigung 2 und weist immer einige dieser Stufen auf. Es scheint, dass die Schritte sublinear wachsen (wenn sie nicht einmal begrenzt sind), da sie kaum wahrnehmbar werden, wenn Sie die Anzahl der Punkte erhöhen, die Sie zeichnen.

Wir können das lineare Wachstum rechtfertigen ganz leicht (das ist ein bisschen handwavy, aber ich denke , es ist an einen strengen Beweis durch Induktion halten würde): zunächst die maximale Anzahl betroffener eine Permutation Schritt an nist n + (n+1) = 2n + 1. Beachten Sie auch, dass diese Nummern immer nach verschoben werden 1, da |n - (n+1)| = 1. Es ist also nicht verwunderlich, dass wir Zahlen erhalten, die ungefähr 2nin der Reihenfolge liegen. Wir können jedoch auch zu beachten , dass für die Schritte bis n , S n + 1 immer begrenzt ist durch n + 1 , was bedeutet , dass kein Schritt swapping zwei Zahlen wechseln kann , die beide größer sind , als auch die für die Sequenz selbst gebunden ist. n . Daher sind Zahlen, die noch verarbeitet werden müssen, kleiner oder gleich ihrem Anfangswert. Daher,2n + 1

Ich denke, ein Argument für die Länge der Schritte zu finden, ist schwieriger.

Martin Ender
quelle
3
+1 für eine gute Lösung, aber vor allem für die sehr interessante und informative Analyse!
Alex A.
4

CJam, 45 40 39 Bytes

Nur ein naiver Ansatz. Kann weiter golfen werden. Es fehlt zu viel an einer Array-Auslagerungsfunktion.

ri_K*,\{\:L>2<L1$:+:S@:-z:DL=tDSL=t}/1=

Wie es funktioniert:

ri_                             "Read the input, convert to integer and copy it";
   K*,                          "Multiply the copy by 20 and get 0 to 20*input-1 array";
      \{ ... }/1=               "Swap and put input on stack and run the loop that many";
                                "times. After the loop, take the second element as";
                                "we have a 0 based array while series is 1 based";
{\:L>2<L1$:+:S@:-z:DL=tDSL=t}
 \:L                            "Swap to put iteration index behind the array";
                                "and store array in L";
    >2<                         "In each loop, the iteration index will be on stack";
                                "Get the two elements from the array starting at that";
       L1$                      "Put the array on stack and copy the tuple";
          :+:S                  "Get the sum and store it in S";
              @:-z:D            "Get the absolute difference of the tuple and store in D";
                    L=t         "Put the element at S diff at sum index";
                       DSL=t    "Put the element at S sum at diff index";

Probieren Sie es hier online aus

Optimierer
quelle
4

Haskell, 95 Bytes

f#n=let b=f$n+1;l=f n+b;r=abs$f n-b;y x|x==l=f r|x==r=f l|1<2=f x in y
p n=foldl(#)id[1..n-1]$1

Anwendungsbeispiel: p 70->139

Ich speichere die Sequenz nicht in einer Liste oder einem Array. Ich aktualisiere die Identitätsfunktion wiederholt auf eine Funktion, bei der die beiden Elemente des aktuellen Schritts ausgetauscht werden. Nach nSchritten rufe ich die resultierende Funktion mit Parameter auf 1.

nimi
quelle
2

J, 63 Bytes

3 :'{.>((1-~{(+,|@-)]{~1+[)|.@:{`[`]}])&.>/(<"*i.1-y),<>:i.3*y'

Verwendung und Tests:

   f=.3 :'{.>((1-~{(+,|@-)]{~1+[)|.@:{`[`]}])&.>/(<"*i.1-y),<>:i.3*y'

   f 5
9
   f every 1+i.20
1 3 1 7 9 11 11 11 15 15 19 19 19 19 19 19 19 19 19 19

Probieren Sie es hier online aus.

randomra
quelle
1

Pyth, 55 53 51

Kann wahrscheinlich weiter golfen werden. Könnte sehr langsam werden, nda ich faul war, herauszufinden, wie lange ich ein Array brauchte und nur n^neins benutzte .

Vielen Dank an Volatility und Martin Büttner für den Hinweis, dass ich maximal verwenden kann 3n.

KU*3QFNr1QJ@KN=G@tKNAJG,+JG.a-JG=Y@KJ XXKJ@KGGY)@K1

Erläuterung

                   Q = input (implicit)
KU*3Q              K = range(3 * Q)
FNr1Q              for N in range(1, Q):
 J@KN               J = K[N]
 =G@tKN             G = K[1:][N]
 AJG,+JG.a-JG       J, G = J + G, abs(J - G)
 =Y@KJ              Y = K[J]
 XXKJ@KGGY          K[J], K[G] = K[G], Y
)
@K1                print K[1]
PurkkaKoodari
quelle
Ich habe einige Tests durchgeführt, und es scheint, dass die erforderliche Listenlänge 2*nfür große nmit einem Maximum von 3*nfür konvergiert n=1.
Volatility
@Volatility Im Wesentlichen ist das Maximum 2n+1, das, wie Sie sagen, sein Maximum 3für hat n=1und (in gewisser Weise) zu konvergiert 2n. Dies ist nicht allzu überraschend, da dies das Maximum für die nicht durchlässige Sequenz ist und kein Schritt im Prozess eine Zahl erhöhen kann, die noch vor Ihnen liegt. Ich könnte dies zu meiner Antwort hinzufügen.
Martin Ender
Wie ich sehe, setzen Sie meine .aErweiterung bereits für gute Arbeit ein! Es gibt viel mehr Goodies auf dem Weg, aber Isaac schläft gerade: github.com/isaacg1/pyth/pull/32
orlp
@orlp, ich habe tatsächlich die Dokumente gelesen, während ich den Code geschrieben habe (normalerweise verwende ich das doc.txtauf GitHub für ein Handbuch) und das Update gesehen. Zum Glück, da ich es einfach hätte überspringen und eine benutzerdefinierte Implementierung schreiben können ...
PurkkaKoodari
1

Python 2, 117 106 101

j=input();a=range(3*j)
for i in range(1,j):b,c=a[i:i+2];d=abs(b-c);a[b+c],a[d]=a[d],a[b+c]
print a[1]

Verwendet a dict(map), um die Werte zu speichern und beliebige Indizes zu verwenden. g(n)ist eine Funktion, die den nArtikel zurückgibt. Dann iteriert man einfach input-1mal und gibt das erste Item aus.

Es stellt sich heraus, dass es mit den Methoden aus meiner Pyth-Antwort kürzer ist.

Danke an xnor für das Speichern von 5 Bytes.

PurkkaKoodari
quelle
Sie können die Liste verwenden Auspacken: b,c=a[i:i+2]. Außerdem b+cist es kurz genug, dass das Speichern in einer Variablen sZeichen verliert, wenn Sie es nur zweimal schreiben.
Xnor
1

Geh 150

func f(j int){a:=make([]int,j*2);for i:=range a{a[i]=i};for i:=1;i<j;i++{b,c:=a[i],a[i+1];v:=b-c;if v<0{v*=-1};a[b+c],a[v]=a[v],a[b+c]};println(a[1])}

Ungolfed, nichts heikles, meistens von @ Pietu1998 gestohlen

func f(j int) {
    a := make([]int, j*2) // Build the array we will be working on
    for i := range a {
        a[i] = i
    }
    for i := 1; i < j; i++ {
        b, c := a[i], a[i+1]
        v := b - c
        if v < 0 {
            v *= -1
        }
        a[b+c], a[v] = a[v], a[b+c]
    }
    println(a[1])
}

http://play.golang.org/p/IWkT0c4Ev5

Kristoffer Sall-Storgaard
quelle
1

Java, 162

int f(int n){int a[]=new int[2*n],s,d,x,t;for(x=0;x<2*n;)a[x]=++x;for(x=0;++x<n;){s=a[x]+a[x-1]-1;d=Math.abs(a[x]-a[x-1])-1;t=a[s];a[s]=a[d];a[d]=t;}return a[0];}

Erläuterung

int f(int n) {
    int a[] = new int[2 * n], sum, diff, x, temp;
    for (x = 0; x < 2 * n;) {
        a[x] = ++x;  // set initial array
    }
    for (x = 0; ++x < n;) {
        sum = a[x] + a[x - 1] - 1;
        diff = Math.abs(a[x] - a[x - 1]) - 1;
        temp = a[sum];
        a[sum] = a[diff];
        a[diff] = temp;
    }
    return a[0];
}
Ypnypn
quelle
Sie können zwei Bytes sparen, indem Sie den zweiten Schleifenkörper in die Inkrement-Klausel der for-Anweisung verschieben. (Trennen Sie die Anweisungen durch Kommata und nicht durch Semikola.)
AJMansfield
1

dc, 134 132 131 Bytes

[_1*]sOdsn2*ddslsSsa[ladd:S1-dsa0<P]dsPx1d0rsN:N[la1+dsad;SdS@r1+;SdS@rL@L@r+Ss-d0>Od;SrLsdSsrLs;Sr:S:S1;SladsN:Nlaln>G]dsGxln1-;Nf

Verwenden Sie echo $n $code | dc, wo $nist n und $codeist ... der Code ( keuchen ). Zitat nach Geschmack.

Bearbeiten: Wenn Sie mich nicht für eine Erklärung belästigen, werde ich nie dazu kommen.

Joe
quelle
Muss ich drei Bytes für das `-e` hinzufügen?
Joe
@ Sir, es stellt sich heraus, dass Sie nicht! [ codegolf.stackexchange.com/questions/25670/…
Joe
War das ein Gespräch mit dir?
NoOneIsHere
@NoOneIsHere: Ja, sicher war. Es war eine Frage, die jedem offen stand, aber ich fand die Antwort.
Joe
0

Perl 5, 131

Eine naive Lösung (dh eine direkte Umsetzung der Definition). Eine Unterroutine, die Eingaben als Liste von 1s der gewünschten Länge annimmt .

{map$a[$_]=$_,1..3*@_;($a[$a[$_-1]+$a[$_]],$a[abs($a[$_-1]-$a[$_])])=($a[abs($a[$_-1]-$a[$_])],$a[$a[$_-1]+$a[$_]])for 2..@_;$a[1]}

Visualisieren Sie die Ausgabe, indem Sie z print sub...->(1,1,1,1,1).

Erläuterung:

map$a[$_]=$_,1..3*@_Erstellt das Array @aund indiziert jede Ganzzahl für sich, und zwar das 1- bis 3-fache der Größe von@_ (der Eingabe).

($a[$a[$_-1]+$a[$_]],$a[abs($a[$_-1]-$a[$_])])=($a[abs($a[$_-1]-$a[$_])],$a[$a[$_-1]+$a[$_]])for 2..@_wiederholt das Umschalten wiederholt (einmal weniger als die Größe von @_) und wechselt $a[$a[$_-1]+$a[$_]]mit $a[abs($a[$_-1]-$a[$_])]as$_ von 2 bis zur Größe von @_.

Und dann kehrt das Unterprogramm zurück $a[1].

msh210
quelle
0

Perl 5 , 90 + 1 (-p) = 91 Bytes

@a=0..3*$_;$_=(map{@a[$d,$s]=@a[$s=$a[$_]+$a[$_-1],$d=abs$a[$_]-$a[$_-1]];$a[1]}1..$_)[-1]

Probieren Sie es online!

Xcali
quelle