Inspiriert von dieser früheren Stack-Overflow-Frage habe ich darüber nachgedacht, wie Zufällige Verschachtelung von Iterablen in Python unter Beibehaltung der Reihenfolge der Elemente in jedem Iterablen. Zum Beispiel:
%Vor%Die ursprüngliche Frage, die zur zufälligen Verschachtelung von zwei Listen, a und b, und der akzeptierten Lösung gestellt wurde, lautet:
%Vor% Diese Lösung funktioniert jedoch nur für zwei Listen (obwohl sie leicht erweitert werden kann) und beruht auf der Tatsache, dass a und b Listen sind, so dass pop() und len() für sie aufgerufen werden können, was bedeutet, dass es nicht sein kann verwendet mit iterables. Es hat auch den unglücklichen Nebeneffekt, die Quelllisten a und b zu leeren.
Alternative Antworten, die für die ursprüngliche Frage gegeben werden, nehmen Kopien der Quellenlisten, um zu vermeiden, sie zu ändern, aber das scheint mir ineffizient, besonders wenn die Quellenlisten groß sind. Die alternativen Antworten verwenden auch len() und können daher nicht auf einfache iterables angewendet werden.
Ich habe meine eigene Lösung geschrieben, die für beliebig viele Eingabelisten funktioniert und sie nicht verändert:
%Vor% Diese Lösung basiert jedoch auch auf den Quellargumenten als Listen, sodass len() für sie verwendet werden kann.
Gibt es also eine effiziente Möglichkeit, Iterables in Python zufällig zu verschachteln, wobei die ursprüngliche Reihenfolge der Elemente erhalten bleibt, die keine Kenntnis der Länge der Iterables im Voraus erfordert und keine Kopien der Iterables erstellt?
Bearbeiten: Bitte beachten Sie, dass, wie bei der ursprünglichen Frage, die Randomisierung nicht fair sein muss.
Nicht, wenn Sie fit sein wollen, um "fair" zu sein.
Stellen Sie sich vor, Sie haben eine Liste mit einer Million Artikeln und eine andere mit nur zwei Artikeln. Bei einer "fairen" Randomisierung würde das erste Element aus der kurzen Liste etwa bei 300000 oder so erscheinen.
%Vor%Aber es gibt keine Möglichkeit, im Voraus zu wissen, bis Sie die Länge der Listen kennen.
Wenn Sie nur aus jeder Liste mit 50% (1 / n) Wahrscheinlichkeit nehmen, dann kann es getan werden, ohne die Längen der Listen zu kennen, aber Sie werden etwas mehr wie folgt erhalten:
%Vor%Ich bin überzeugt, dass die von aix bereitgestellte Lösung den Anforderungen der Frage entspricht. Nach dem Lesen der Kommentare von Mark Byers wollte ich jedoch sehen, wie "unfair" die Lösung war.
Außerdem, irgendwann nachdem ich diese Frage geschrieben habe, hat der Stack-Überlauf-Benutzer EOL eine andere Lösung an die original Frage , die ein "faires" Ergebnis ergibt. Die Lösung von EOL ist:
%Vor% Ich habe auch meine eigene Lösung weiter verbessert, so dass sie nicht auf ihren Argumenten basiert, die len() unterstützen, sondern Kopien der Quellen-Iterablen erstellt:
oder, anders geschrieben:
%Vor%Ich testete dann die akzeptierte Lösung der ursprünglichen Frage, geschrieben von F.J und reproduziert in meiner Frage oben, zu den Lösungen von aix, EOL und meiner eigenen. Der Test beinhaltete das Verschachteln einer Liste von 30000 Elementen mit einer einzelnen Elementliste (dem Sentinel). Ich habe den Test 1000 Mal wiederholt und die folgende Tabelle zeigt für jeden Algorithmus den minimalen, maximalen und mittleren Index des Sentinels nach dem Interleaving zusammen mit der Gesamtzeit. Wir erwarten von einem "fairen" Algorithmus einen Mittelwert von ca. 15.000:
%Vor%Wie aus den Ergebnissen ersichtlich ist, liefert jeder der Algorithmen von F.J, EOL und Srgerg scheinbar "faire" Ergebnisse (zumindest unter den gegebenen Testbedingungen). Allerdings hat der Algorithmus von aix den Sentinel immer innerhalb der ersten 10 Elemente des Ergebnisses platziert. Ich wiederholte das Experiment mehrmals mit ähnlichen Ergebnissen.
Also, Mark Byers hat sich als richtig erwiesen. Wenn eine wirklich zufällige Verschachtelung erwünscht ist, muss die Länge der Quellen-Iterablen im Voraus bekannt sein, oder es müssen Kopien erstellt werden, so dass die Länge bestimmt werden kann.
Tags und Links python