Herausforderung
Geben Sie bei einer Ganzzahl n ≥ 4 eine Permutation der Ganzzahlen [0, n-1] mit der Eigenschaft aus, dass keine zwei aufeinander folgenden Ganzzahlen (Ganzzahlen mit absoluter Differenz 1) nebeneinander liegen.
Beispiele
- 4 → [1, 3, 0, 2]
- 5 → [0, 2, 4, 1, 3]
- 6 → [0, 2, 4, 1, 3, 5]
- 7 → [0, 2, 4, 1, 5, 3, 6]
Sie können stattdessen die 1-Indizierung verwenden (unter Verwendung von Ganzzahlen [1, n] anstelle von [0, n-1] ).
Ihr Code muss in n in Polynomialzeit ausgeführt werden , daher können Sie nicht alle Permutationen testen und testen.
[[1,3],[0,2]]
ein akzeptables Ausgabeformat?Antworten:
Gelee ,
32 BytesSortiert die Ganzzahlen in [1, ..., n] nach ihrem LSB.
Probieren Sie es online!
quelle
Þ
stabile Sortierung, da die Implementierung mit der Python-sorted
Funktion erfolgt, die garantiert stabil ist .Python 2 , 32 Bytes
Probieren Sie es online!
quelle
Python 3 ,
40, 38 BytesProbieren Sie es online!
Das läuft
O(n)
pünktlich.Danke an Dennis für das Speichern von 2 Bytes!
quelle
Python 2 , 34 Bytes
Probieren Sie es online!
Python 2 , 40 Bytes
Probieren Sie es online!
quelle
Haskell, 22 Bytes
f ist eine Funktion von n, die eine entsprechend geordnete Liste zurückgibt. Ich verwende die Option 1-Indizierung.
quelle
Oktave , 17 Bytes
Probieren Sie es online!
Dies verwendet den gleichen Ansatz wie viele andere. Verketten Sie zwei Vektoren, einen mit der geraden Zahl im Inklusivbereich 2 ... x und alle ungeraden Zahlen im Inklusivbereich 1 ... x . Die Syntax sollte ziemlich offensichtlich sein, deshalb werde ich das nicht erklären.
quelle
3
und2
nebeneinander inf(4)
?JavaScript (ES6), 40 Byte
Bearbeiten: 1 Byte dank @Arnauld gespeichert.
quelle
Gaia , 2 Bytes
Probieren Sie es online!
Dies einfach (stable) ∫ ORT die ganzen Zahlen im Bereich [1, Eingang] durch ihre pa r ity.
quelle
R ,
393635 BytesProbieren Sie es online!
quelle
05AB1E , 3 Bytes
Port von DJMcMayhem's Python Antwort und Dennis's Jelly Antwort
Probieren Sie es online!
Wie?
quelle
Japt, 4 Bytes
Sie können auch ersetzen
u
mitv
einer anderen Ordnung zu bringen.Versuch es
Oder, wenn wir ein Array von 2 Arrays ausgeben können:
Versuch es
quelle
4
leider fehl ; Sie können die ersten beheben , indem Sieu
aufv
odero
zuõ
.Mathematica, 50 -> 47 -> 42 Bytes
Probieren Sie es online!
Vielen Dank an user202729 für den Hinweis auf das zweifache Optimierungspotenzial Join [] insteaed von Flatten [] und die Verwendung reiner Funktionen.
Ich möchte zwei Bemerkungen hinzufügen.
1) Es ist ziemlich einfach, eine spezifische Permutation ohne abfallende oder ansteigende Folge für n> = 4 zu konstruieren, wie im OP angefordert.
Es besteht aus zwei aufeinander folgenden Listen.
Für gerade n sind dies:
list1 = (2,4, ..., n / 2)
list2 = (1,3, ..., n / 2-1)
Für ungerade n gilt:
Liste1 = (2,4, ..., Etage [n / 2])
Liste2 = (1,3, ..., Etage [n / 2])
Für diesen "Algorithmus" muss nur eine Entscheidung getroffen werden (n gerade oder ungerade), der Rest schreibt nur n Zahlen auf.
Eine mögliche Mathematica-Lösung finden Sie oben.
2) Eine verwandte Frage ist, wie viele solche Permuationen als Funktion von n existieren.
Mathematica, 124 Bytes
Probieren Sie es online!
Beispiel:
Die Anzahl solcher Permutationen zu zählen, ist ein Standardproblem.
Für n = 4 gibt es 2: {{2,4,1,3}, {3,1,4,2}}
Für n = 5 gibt es 14: {{1,3,5,2,4}, {1,4,2,5,3}, {2,4,1,3,5}, {2,4, 1,5,3}, {2,5,3,1,4}, {3,1,4,2,5}, {3,1,5,2,4}, {3,5,1, 4,2}, {3,5,2,4,1}, {4,1,3,5,2}, {4,2,5,1,3}, {4,2,5,3} 1}, {5,2,4,1,3}, {5,3,1,4,2}}
Die Anzahl a (n) dieser Permutationen steigt schnell an: 2, 14, 90, 646, 5242, 47622, 479306, 5296790, 63779034, ...
Für großes n gilt das Verhältnis a (n) / n! scheint sich der Grenze 1 / e ^ 2 = 0.135335 zu nähern ... Ich habe keinen strengen Beweis, aber es ist nur eine Vermutung aus numerischen Beweisen. Sie können dies testen, indem Sie versuchen, das Programm online auszuführen.
Das obige Programm (basierend auf der unten angegebenen Referenz) berechnet diese Zahlen.
Weitere Informationen finden Sie in der entsprechenden Reihenfolge unter OEIS: A002464 . Hertzsprungs Problem: Möglichkeiten, n nicht angreifende Könige auf einem n x n-Brett anzuordnen, mit 1 in jeder Zeile und Spalte. Auch Anzahl der Permutationen der Länge n ohne steigende oder fallende Folgen.
quelle
[some text](the_link)
. Insbesondere für den Link "Online testen" enthält die Website https://tio.run/ , die von unserem eigenen @Dennis gehostet wird, Links zu allen Arten von Programmiersprachen. Wolfram Language (Mathematica) ist einer von ihnen. Oben können Sie dann auf die Wiedergabetaste klicken, um den Code auszuführen, oder auf die Hyperlink-Taste, um "Online ausprobieren" zu kopieren. (Markup-) Links. Und Sie können Ihren Code in tatsächlichen "Code" (Ihren Beitrag) aufteilen, mit einer optionalen Kopf- / Fußzeile zum (hübschen) Drucken eines oder mehrerer Testfälle.JavaScript (Node.js) , 42 Byte
Probieren Sie es online!
JavaScript (Node.js) , 47 Byte
Probieren Sie es online!
quelle
Ruby , 27 Bytes
Probieren Sie es online!
1-Indizierung verwenden
quelle
Leerzeichen , 161 Bytes
Hier ist die offizielle, unkommentierte Einreichung: Probieren Sie es online!
Probieren Sie es online!
Ich habe ein paar Bytes geopfert, damit das Programm fehlerfrei abläuft, ich glaube, ich könnte etwa 7-8 Bytes verlieren und es würde immer noch richtig ausgegeben, aber es würde auch Fehlermeldungen ausgeben, und das will niemand.
Volle Byte Erklärung:
quelle
push_0, read_STDIN_as_int, push_0, retrieve
kann seinpush_0, duplicate_0, read_STDIN_as_int, retrieve
, ein Byte zu speichern. Und das erste Etikett kann ein leeres sein mitNSSN
anstelle vonNSSSN
(und dann kann das zweite Etikett seinNSSSN
; drittesNSSTN
und viertesNSSSSN
). Dies sollte ebenfalls 8 Bytes einsparen. Sie können auch das erste entfernen,Jump_to_third_label
da Sie bereits dasSet_third_label
Recht darunter haben. Insgesamt: 140 Bytes ; (oder mit Kommentaren: Probieren Sie es online aus .) -3 Bytes, wenn SieNNN
exit entfernen .F # (Mono) , 27 Bytes
Probieren Sie es online!
quelle
Gol> <> , 14 Bytes
Probieren Sie es online!
Beispiel volles Programm & wie es funktioniert
quelle
J , 10 Bytes
Probieren Sie es online!
Erläuterung:
quelle
Java 8, 56 Bytes
Portierung der Antwort von @Neil auf JavaScript (ES6) .
Probieren Sie es online aus.
Alte 66 Bytes Antwort:
Probieren Sie es online aus.
Erläuterung:
quelle
Ruby, 27 Bytes
Wie in diesem Antwort werden die
n
ersten Ganzzahlen nach ihrem niedrigstwertigen Bit sortiert.Probieren Sie es online!
quelle