Erstellen Sie eine ausgeglichene BST aus einer sortierten Liste von Ganzzahlen

15

Erstellen Sie anhand einer eindeutigen, sortierten Liste von Ganzzahlen einen ausgeglichenen Binärsuchbaum, der als Array ohne Verwendung von Rekursion dargestellt wird.

Beispielsweise:

func( [1,2,3,5,8,13,21] ) => [5,2,13,1,3,8,21]

Bevor wir anfangen, ein Hinweis: Wir können dieses Problem um ein Vielfaches vereinfachen, damit wir nicht über die Eingabe-Ganzzahlen (oder ein vergleichbares Objekt) nachdenken müssen.

Wenn wir wissen, dass die Eingabeliste bereits sortiert ist, ist der Inhalt irrelevant. Wir können es uns einfach in Form von Indizes in das ursprüngliche Array überlegen.

Eine interne Darstellung des Eingabearrays wird dann:

func( [0,1,2,3,4,5,6] ) => [3,1,5,0,2,4,6]

Das heißt, anstatt etwas zu schreiben, das mit vergleichbaren Objekten zu tun hat, müssen wir wirklich nur eine Funktion schreiben, die aus dem Bereich [0, n) auf das resultierende Array abgebildet wird. Sobald wir die neue Reihenfolge haben, können wir die Zuordnung einfach wieder auf die Werte in der Eingabe anwenden, um das Rückgabearray zu erstellen.

Gültige Lösungen müssen:

  • Akzeptieren Sie ein Array mit null Elementen und geben Sie ein leeres Array zurück.
  • Akzeptieren Sie ein Integer-Array der Länge n und geben Sie ein Integer-Array zurück
    • Mit einer Länge zwischen n und der nächsthöheren Potenz von 2 minus 1. (z. B. bei Eingangsgröße 13 irgendwo zwischen 13 und 15 zurückgeben).
    • Array, das eine BST darstellt, bei der sich der Stammknoten an Position 0 befindet und die Höhe log (n) entspricht, wobei 0 einen fehlenden Knoten darstellt (oder einen nullähnlichen Wert, wenn Ihre Sprache dies zulässt). Leere Knoten, falls vorhanden, dürfen nur am Ende des Baumes existieren (zB [2,1,0])

Das ganzzahlige Eingabearray hat die folgenden Garantien:

  • Werte sind 32-Bit-Ganzzahlen mit Vorzeichen, die größer als Null sind.
  • Werte sind einzigartig.
  • Die Werte sind ab Position Null aufsteigend sortiert.
  • Werte können spärlich sein (dh nicht nebeneinander liegen).

Der knappste Code nach Anzahl der ASCII-Zeichen gewinnt, aber ich bin auch daran interessiert, elegante Lösungen für eine bestimmte Sprache zu finden.

Testfälle

Die Ausgaben für einfache Arrays enthalten 1bis nfür verschiedene n. Wie oben beschrieben, sind die nachfolgenden 0s optional.

[]
[1]
[2,1,0]
[2,1,3]
[3,2,4,1,0,0,0]
[4,2,5,1,3,0,0]
[4,2,6,1,3,5,0]
[4,2,6,1,3,5,7]
[5,3,7,2,4,6,8,1,0,0,0,0,0,0,0]
[6,4,8,2,5,7,9,1,3,0,0,0,0,0,0]
[7,4,9,2,6,8,10,1,3,5,0,0,0,0,0]
[8,4,10,2,6,9,11,1,3,5,7,0,0,0,0]
[8,4,11,2,6,10,12,1,3,5,7,9,0,0,0]
[8,4,12,2,6,10,13,1,3,5,7,9,11,0,0]
[8,4,12,2,6,10,14,1,3,5,7,9,11,13,0]
[8,4,12,2,6,10,14,1,3,5,7,9,11,13,15]
Jake Wharton
quelle
Alle Fragen auf dieser Site, ob Programmierpuzzle oder Codegolf, sollten ein objektives Hauptgewinnkriterium haben, damit unbestreitbar entschieden werden kann, welcher Eintrag gewinnen soll.
Howard
@ Howard Danke. Aktualisiert mit endgültigen Kriterien für den Gewinner.
Jake Wharton
1
Es wäre sehr nützlich, einige Testfälle zu haben, die die schwierigen Fälle abdecken, und nicht (wie derzeit) nur die einfachsten.
Peter Taylor
Gibt es einen Grund, eine Rekursion auszuschließen? Nicht, dass ich eine rekursive Lösung suche, aber das scheint sowohl künstlich als auch unnötig.
dmckee
1
Kann jemand erklären, wie die Liste eine BST darstellt?
JustinPC

Antworten:

4

Rubin , 143

s=ARGV.size;r,q=[],[[0,s]];s.times{b,e=q.shift;k=Math::log2(e-b).to_i-1;m=(e-b+2)>(3<<k)?b+(2<<k)-1:e-(1<<k);r<<ARGV[m];q<<[b,m]<<[m+1,e]};p r

Es ist eine (lose) komprimierte Version des folgenden Codes, die im Grunde ein BFS für den Baum ausführt.

def l(n)
    k = Math::log2(n).to_i-1
    if n+2 > (3<<k) then
        (2<<k)-1
    else
        n-(1<<k) 
    end
end

def bfs(tab)
  result = []
  queue = [[0,tab.size]]
  until queue.empty? do
    b,e = queue.shift
    m = b+l(e-b)
    result << tab[m]
    queue << [b,m] if b < m
    queue << [m+1,e] if m+1 < e
  end
  result
end

p bfs(ARGV)

Da es sich um BFS und nicht um DFS handelt, ist die Anforderung einer nicht rekursiven Lösung nicht wesentlich, und es werden einige Sprachen benachteiligt.

Edit: Behobene Lösung, danke an @PeterTaylor für seinen Kommentar!

dtldarek
quelle
@PeterTaylor Es wurde beabsichtigt, 3 vor 4 zu setzen, aber es gibt keine Leerzeichen, also ist es falsch. Vielen Dank für den Hinweis!
Dtldarek
@PeterTaylor Während des Mittagessens repariert, sollte es jetzt funktionieren.
Dtldarek
4

Java , 252

Ok, hier ist mein Versuch. Ich habe mit Bitoperationen herumgespielt und mir diese direkte Methode ausgedacht, um den Index eines Elements in der BST aus dem Index im ursprünglichen Array zu berechnen.

Komprimierte Version

public int[]b(int[]a){int i,n=1,t;long x,I,s=a.length,p=s;int[]r=new int[(int)s];while((p>>=1)>0)n++;p=2*s-(1l<<n)+1;for(i=0;i<s;i++){x=(i<p)?(i+1):(p+2*(i-p)+1);t=1;while((x&1<<(t-1))==0)t++;I=(1<<(n-t));I|=((I-1)<<t&x)>>t;r[(int)I-1]=a[i];}return r;}

Die lange Version folgt weiter unten.

public static int[] makeBst(int[] array) {
  long size = array.length;
  int[] bst = new int[array.length];

  int nbits = 0;
  for (int i=0; i<32; i++) 
    if ((size & 1<<i)!=0) nbits=i+1;

  long padding = 2*size - (1l<<nbits) + 1;

  for (int i=0; i<size; i++) {
    long index2n = (i<padding)?(i+1):(padding + 2*(i-padding) + 1);

    int tail=1;
    while ((index2n & 1<<(tail-1))==0) tail++;
    long bstIndex = (1<<(nbits-tail));
    bstIndex = bstIndex | ((bstIndex-1)<<tail & index2n)>>tail;

    bst[(int)(bstIndex-1)] = array[i];
  }
 return bst;
}
Mikail Sheikh
quelle
Sie benötigen eine Anzahl von Zeichen, und dies ist derzeit nicht Golf.
dmckee
@dmckee Ich habe den Beitrag so bearbeitet, dass er eine komprimierte Version und eine Anzahl von Zeichen enthält
Mikail Sheikh
Gute Show. Ich wette, dass einige dieser Räume unnötig sind. In c int[] b(int[] a)ist genauso gut ausgedrückt wie int[]b(int[]a).
dmckee
Sie haben a.lengthin der Array-Zuordnung. Ändern Sie es zu s. Entfernen Sie den Abstand zwischen for (mehreren Malen. Jede for-Schleife erzeugt ein int i=0und auch int t=0. Erstellen Sie mit n( int n=0,i,t;) und dann nur i=0in den Schleifen und t=1innen. Deklarieren Sie das innere long xund long Imit sund initialisieren Sie es einfach in der Schleife ( long s=a.length,I,x;und x=../ I=..). Sie sollten keine Leerzeichen um das binäre UND benötigen &.
Jake Wharton
Auch I=I|..kann geschrieben werdenI|=..
Jake Wharton
3
def fn(input):
    import math
    n = len(input)
    if n == 0:
        return []
    h = int(math.floor(math.log(n, 2)))
    out = []
    last = (2**h) - 2**(h+1) + n

    def num_children(level, sibling, lr):
        if level == 0:
            return 0
        half = 2**(level-1)
        ll_base = sibling * 2**level + lr * (half)
        ll_children = max(0, min(last, ll_base + half - 1) - ll_base + 1)
        return 2**(level-1) - 1 + ll_children

    for level in range(h, -1, -1):
        for sibling in range(0, 2**(h-level)):
            if level == 0 and sibling > last:
                break
            if sibling == 0:
                last_sibling_val = num_children(level, sibling, 0)
            else:
                last_sibling_val += 2 + num_children(level, sibling - 1, 1) \
                    + num_children(level, sibling, 0)
            out.append(input[last_sibling_val])
    return out
aarkay
quelle
2

Ich bin mir nicht ganz sicher, ob dies genau zu Ihrer Anforderung passt, dass leere Knoten am Ende des Baums sind, und es wird sicherlich keine Preise für die Kürze gewinnen, aber ich denke, es ist richtig und es hat Testfälle :)

public class BstArray {
    public static final int[] EMPTY = new int[] { };
    public static final int[] L1 = new int[] { 1 };
    public static final int[] L2 = new int[] { 1, 2 };
    public static final int[] L3 = new int[] { 1, 2, 3 };
    public static final int[] L4 = new int[] { 1, 2, 3, 5 };
    public static final int[] L5 = new int[] { 1, 2, 3, 5, 8 };
    public static final int[] L6 = new int[] { 1, 2, 3, 5, 8, 13 };
    public static final int[] L7 = new int[] { 1, 2, 3, 5, 8, 13, 21 };
    public static final int[] L8 = new int[] { 1, 2, 3, 5, 8, 13, 21, 35 };
    public static final int[] L9 = new int[] { 1, 2, 3, 5, 8, 13, 21, 35, 56 };
    public static final int[] L10 = new int[] { 1, 2, 3, 5, 8, 13, 21, 35, 56, 91 };

    public static void main(String[] args) {
        for (int[] list : Arrays.asList(EMPTY, L1, L2, L3, L4, L5, L6, L7, L8, L9, L10)) {
            System.out.println(Arrays.toString(list) + " => " + Arrays.toString(bstListFromList(list)));
        }
    }

    private static int[] bstListFromList(int[] orig) {
        int[] bst = new int[nextHighestPowerOfTwo(orig.length + 1) - 1];

        if (orig.length == 0) {
            return bst;
        }

        LinkedList<int[]> queue = new LinkedList<int[]>();
        queue.push(orig);

        int counter = 0;
        while (!queue.isEmpty()) {
            int[] list = queue.pop();
            int len = list.length;

            if (len == 1) {
                bst[counter] = list[0];
            } else if (len == 2) {
                bst[counter] = list[1];
                queue.add(getSubArray(list, 0, 1));
                queue.add(new int[] { 0 });
            } else if (len == 3) {
                bst[counter] = list[1];
                queue.add(getSubArray(list, 0, 1));
                queue.add(getSubArray(list, 2, 1));
            } else {
                int divide = len / 2;
                bst[counter] = list[divide];
                queue.add(getSubArray(list, 0, divide));
                queue.add(getSubArray(list, divide + 1, len - (divide + 1)));
            }
            counter++;
        }

        return bst;
    }

    private static int nextHighestPowerOfTwo(int n) {
        n--;
        n |= n >> 1;
        n |= n >> 2;
        n |= n >> 4;
        n |= n >> 8;
        n |= n >> 16;
        n++;

        return n;
    }

    private static int[] getSubArray(int[] orig, int origStart, int length) {
        int[] list = new int[length];
        System.arraycopy(orig, origStart, list, 0, length);
        return list;
    }
}
Andrew Flynn
quelle
2

Golfscript ( 99 89)

~]:b[]:^;{b}{{:|.,.2base,(2\?:&[-)&2/]{}$0=&(2/+:o[=]^\+:^;|o<.!{;}*|o)>.!{;}*}%:b}while^p

Grundsätzlich funktioniert ein gerader Port meiner Python-Lösung auf die gleiche Weise.

Kann wahrscheinlich mit mehr "Golfismen" einiges verbessert werden, bereits verbessert um 10 Zeichen mit @ petertaylors Eingabe :)

Joachim Isaksson
quelle
Ich denke, es sollte in nicht mehr als 70 möglich sein, obwohl ich meine GolfScript-Antwort noch nicht ganz beendet habe. Es gibt jedoch einige einfache Verbesserungen für Sie. !{;}{}ifkann nur !{;}*daran liegen, !garantiert zurückzukehren 0oder 1. Sie können nicht alphabetische Token für Variablen verwenden, wenn Sie also verwenden ^statt r, |statt x, &statt ysie alle , dass Leerzeichen zu beseitigen.
Peter Taylor
@ Peter Taylor Vielen Dank, wusste nicht über nicht alphanumerische Variablen, noch sehr neu in Golfscript :)
Joachim Isaksson
2

Java 192

Ordnet den Index in der Eingabe dem Index in der Ausgabe zu

int[]b(int[]o){int s=o.length,p=0,u=s,i=0,y,r[]=new int[s],c[]=new int[s];while((u>>=1)>0)p++;for(int x:o){y=p;u=i;while(u%2>0){y--;u/=2;}r[(1<<y)-1+c[y]++]=x;i+=i>2*s-(1<<p+1)?2:1;}return r;}

Lange Version:

static int[] bfs(int[] o) {
  int rowCount = 32 - Integer.numberOfLeadingZeros(o.length); // log2
  int slotCount = (1<<rowCount) - 1; // pow(2,rowCount) - 1

  // number of empty slots at the end
  int emptySlots = slotCount - o.length;
  // where we start to be affected by these empty slots
  int startSkippingAbove = slotCount - 2 * emptySlots; // = 2 * o.length - slotCount

  int[] result = new int[o.length];
  int[] rowCounters = new int[rowCount]; // for each row, how many slots in that row are taken
  int i = 0; // index of where we would be if this was a complete tree (no trailing empty slots)
  for (int x : o) {
    // the row (depth) a slot is in is determined by the number of trailing 1s
    int rowIndex = rowCount - Integer.numberOfTrailingZeros(~i) - 1;
    int colIndex = rowCounters[rowIndex]++; // count where we are
    int rowStartIndex = (1 << rowIndex) - 1; // where this row starts in the result array

    result[rowStartIndex + colIndex] = x;

    i++;
    // next one has to jump into a slot that came available by not having slotCount values
    if (i > startSkippingAbove) i++;
  }

  return result;
}
Wouter Coekaerts
quelle
2

Wolfram Mathematica 11, 175 Bytes

g[l_]:=(x[a_]:=Floor@Min[i-#/2,#]&@(i=Length[a]+1;2^Ceiling@Log2[i]/2);Join@@Table[Cases[l//.{{}->{},b__List:>(n[Take[b,#-1],b[[#]],Drop[b,#]]&@x[b])},_Integer,{m}],{m,x[l]}])

Die Funktion g[l]nimmt als Eingabe a List(zB l={1,2,3,4,...}) und gibt a Listin der gewünschten Form zurück. Es funktioniert wie folgt:

  • x[a_]:=Floor@Min[i-#/2,#]&@(i=Length[a]+1;2^Ceiling@Log2[i]/2) Nimmt eine Liste und findet die Wurzel des zugehörigen BST.
    • i=Length[a]+1 Abkürzung für die Länge der Liste
    • 2^Ceiling@Log2[i]/2 Obergrenze für den Wert der Wurzel
    • Min[i-#/2,#]&@(...)Minimum der beiden Argumente wo #steht was in der steht(...)
  • l//.{...} Wenden Sie die folgenden Ersetzungsregeln wiederholt an l
  • {}->{} Nichts zu tun (dies ist der Randfall, um eine Endlosschleife zu vermeiden)
  • b__List:>(n[Take[b,#-1],b[[#]],Drop[b,#]]&@x[b])Teilen Sie ein Listin{{lesser}, root, {greater}}
  • Cases[...,_Integer,{m}] Nehmen Sie alle ganzen Zahlen auf Ebene (Tiefe) m
  • Table[...,{m,1,x[l]}]Für alle mbis x[l](was eigentlich mehr als nötig ist).

Es kann durch Laufen getestet werden

Table[g[Range[a]], {a, 0, 15}]//MatrixForm

Diese Implementierung enthält keine nachgestellten Nullen.

MannyC
quelle
1

Python ( 175 171)

Ziemlich komprimiert, immer noch ziemlich lesbar;

def f(a):
 b=[a]
 while b:
  c,t=((s,2**(len(bin(len(s)))-3))for s in b if s),[]
  for x,y in c:
   o=min(len(x)-y+1,y/2)+(y-1)/2
   yield x[o]
   t+=[x[:o],x[o+1:]]
  b=t

Es gibt das Ergebnis zurück, so dass Sie es entweder durchlaufen oder (zu Anzeigezwecken) als Liste ausdrucken können.

>>> for i in range(1,17): print i-1,list(f(range(1,i)))
 0 []
 1 [1]
 2 [2, 1]
 3 [2, 1, 3]
 4 [3, 2, 4, 1]
 5 [4, 2, 5, 1, 3]
 6 [4, 2, 6, 1, 3, 5]
 7 [4, 2, 6, 1, 3, 5, 7]
 8 [5, 3, 7, 2, 4, 6, 8, 1]
 9 [6, 4, 8, 2, 5, 7, 9, 1, 3]
10 [7, 4, 9, 2, 6, 8, 10, 1, 3, 5]
11 [8, 4, 10, 2, 6, 9, 11, 1, 3, 5, 7]
12 [8, 4, 11, 2, 6, 10, 12, 1, 3, 5, 7, 9]
13 [8, 4, 12, 2, 6, 10, 13, 1, 3, 5, 7, 9, 11]
14 [8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13]
15 [8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15]
Joachim Isaksson
quelle
@dtldarek Sein Kommentar scheint entfernt worden zu sein, aber dies scheint die Testfälle jetzt zu bestehen.
Joachim Isaksson
Ich habe meinen Kommentar gelöscht, damit die Leute nicht auf @ dtldareks Antwort verzichten, weil ein Kommentar besagt, dass er fehlerhaft war.
Peter Taylor
@ PeterTaylor Nun, danke für Ihre Überlegung ;-)
dtldarek
1

Java

Dies ist eine direkte Berechnungslösung. Ich denke, es funktioniert, aber es hat einen pragmatisch harmlosen Nebeneffekt. Das von ihm erzeugte Array ist möglicherweise beschädigt, hat jedoch keinerlei Auswirkungen auf die Suche. Anstatt 0 (null) Knoten zu erzeugen, werden nicht erreichbare Knoten erzeugt, dh die Knoten wurden bereits früher im Baum während der Suche gefunden. Es funktioniert, indem das Index-Array einer regulären Potenz von 2 binären Suchbaum-Arrays auf ein unregelmäßig großes binäres Suchbaum-Array abgebildet wird. Zumindest denke ich, dass es funktioniert.

import java.util.Arrays;

public class SortedArrayToBalanceBinarySearchTreeArray
{
    public static void main(String... args)
    {
        System.out.println(Arrays.toString(binarySearchTree(19)));
    }

    public static int[] binarySearchTree(int m)
    {
        int n = powerOf2Ceiling(m + 1);
        int[] array = new int[n - 1];

        for (int k = 1, index = 1; k < n; k *= 2)
        {
            for (int i = 0; i < k; ++i)
            {
                array[index - 1] = (int) (.5 + ((float) (m)) / (n - 1)
                        * (n / (2 * k) * (1 + 2 * index) - n));
                ++index;
            }
        }

        return array;
    }

    public static int powerOf2Ceiling(int n)
    {
        n--;
        n |= n >> 1;
        n |= n >> 2;
        n |= n >> 4;
        n |= n >> 8;
        n |= n >> 16;
        n++;

        return n;
    }

}

Hier ist eine komprimiertere Version (nur die Funktion und die Namen sind aufeinander abgestimmt). Es ist immer noch der weiße Raum, aber ich mache mir keine Sorgen um den Sieg. Auch diese Version nimmt tatsächlich ein Array auf. Der andere hat gerade ein int für den höchsten Index im Array genommen.

public static int[] b(int m[])
{
    int n = m.length;
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    n++;

    int[] a = new int[n - 1];

    for (int k = 1, j = 1, i; k < n; k *= 2)
    {
        for (i = 0; i < k; ++i)
        {
            a[j - 1] = m[(int) (.5 + ((float) m.length) / (n - 1)
                    * (n / (2 * k) * (1 + 2 * j) - n)) - 1];
            ++j;
        }
    }

    return a;
}
Metaphyse
quelle
Da dies Code-Golf ist , kürzen Sie Ihre Methoden / Namen / etc so kurz wie möglich; Entfernen Sie alle Leerzeichen (und unnötige Methoden / Materialien) und fügen Sie die Zeichenanzahl ein. Ansonsten geht es dir super.
Justin
@ Jake Wharton. Ich würde wirklich gerne Ihre direkte Mapping-Lösung sehen. Ich bin nicht zu 100% sicher, dass meine Methode für sehr große Arrays funktioniert, da sie auf einer kontinuierlichen mathematischen Zuordnung beruht, deren Werte gerundet werden. Es scheint sicherlich zu funktionieren, aber ich bin nicht sicher, wie ich es beweisen soll.
Metaphyse
1

GolfScript ( 79 77 70 Zeichen)

Da das Beispiel in der Frage eine Funktion verwendet, habe ich dies zu einer Funktion gemacht. Wenn Sie das entfernen {}:f;, um einen Ausdruck zu hinterlassen, der Eingaben in den Stapel aufnimmt und die BST auf dem Stapel belässt, werden 5 Zeichen gespart.

{[.;][{{.!!{[.,.)[1]*{(\(@++}@(*1=/()\@~]}*}%.{0=}%\{1>~}%.}do][]*}:f;

Online-Demo (Hinweis: Die App kann ein wenig aufwärmen. Für mich ist die Zeit zweimal abgelaufen, bevor sie in 3 Sekunden ausgeführt wird.)

Mit Leerzeichen, um die Struktur anzuzeigen:

{
    # Input is an array: wrap it in an array for the working set
    [.;]
    [{
        # Stack: emitted-values working-set
        # where the working-set is essentially an array of subtrees
        # For each subtree in working-set...
        {
            # ...if it's not the empty array...
            .!!{
                # ...gather into an array...
                [
                    # Get the size of the subtree
                    .,
                    # OEIS A006165, offset by 1
                    .)[1]*{(\(@++}@(*1=
                    # Split into [left-subtree-plus-root right-subtree]
                    /
                    # Rearrange to root left-subtree right-subtree
                    # where left-subtree might be [] and right-subtree might not exist at all
                    ()\@~
                ]
            }*
        }%
        # Extract the leading element of each processed subtree: these will join the emitted-values
        .{0=}%
        # Create a new working-set of the 1, or 2 subtrees of each processed subtree
        \{1>~}%
        # Loop while the working-set is non-empty
        .
    }do]
    # Stack: [[emitted values at level 0][emitted values at level 1]...]
    # Flatten by joining with the empty array
    []*
}:f;
Peter Taylor
quelle
1

J , 52 Bytes

t=:/:(#/:@{.(+:,>:@+:@i.@>:@#)^:(<.@(2&^.)@>:@#`1:))

Funktion nimmt eine sortierte Liste und kehrt in binärer Baumreihenfolge zurück

Beachten Sie, dass die Bäume die gleiche Form haben, die untere Ebene jedoch verkürzt ist

  • `1: Beginnen Sie mit 1
  • <.@(2&^.)@>:@# iteriere nach Stockwerk von log2 (Länge + 1)
  • +: , >:@+:@i.@>:@# Schleife: Fügt das Doppelte des letzten Vektors mit ungeraden Zahlen 1,3 .. 2 * Länge + 1 hinzu
  • # /:@{. Nehmen Sie nur die erforderliche Anzahl von Elementen und erhalten Sie ihre Sortierindizes
  • /: Wenden Sie diese Sortierindizes auf die angegebene Eingabe an

TIO

Jayprich
quelle
0

Python 2 , 107 Bytes

Golf von Joachim Isaksson: Input ist ein Singleton, der die Liste enthält.

def f(a):
 for x in a:
	if x:w=len(x);y=1<<len(bin(w))-3;o=min(w-y+1,y/2)+~-y/2;yield x[o];a+=x[:o],x[o+1:]

Probieren Sie es online!

ovs
quelle