Geben Sie eine Permutation ohne zwei aufeinanderfolgende ganze Zahlen nebeneinander an

18

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.

Anush
quelle
Wenn Sie "Ausgabe einer Permutation" sagen, meinen Sie das als Liste? Oder können wir eine Funktion erzeugen, die die Permutationszuordnung selbst implementiert?
xnor
@xnor Es sollte in einer für Menschen lesbaren Form ausgegeben werden. Es ist mir egal, wie.
Anush
Wäre [[1,3],[0,2]]ein akzeptables Ausgabeformat?
Shaggy
@ Shaggy Es ist nicht so toll. Bedeutet das 1,3,0,2?
Anush
Related
Peter Taylor

Antworten:

31

Gelee , 3 2 Bytes

ḂÞ

Sortiert die Ganzzahlen in [1, ..., n] nach ihrem LSB.

Probieren Sie es online!

Dennis
quelle
Wow! Das ist großartig.
Anush
2
"Nach LSB sortieren" bedeutet, dass sich alle anderen an den Anfang bewegen. Erfordert die Definition von Jelly jedoch, dass die Zahlen in jeder Hälfte in ihrer ursprünglichen Reihenfolge bleiben? Wenn nicht, könnte 100 (4) neben 101 (5) stehen und immer noch nach LSB sortiert sein. Sie haben keinen Fehler an Ihrem Code gemacht, aber vielleicht ist der beschreibende Kommentar nicht vollständig?
WGroleau
1
@WGroleau Ja, Þstabile Sortierung, da die Implementierung mit der Python- sortedFunktion erfolgt, die garantiert stabil ist .
user202729
3
Der Algorithmus ist für mich beeindruckender als die geringe Größe in seiner Klugheit. Sie können die Bitreihenfolge auch umkehren, sortieren und zurückdrehen.
WGroleau
4
Es kann nur 65536 verschiedene Zwei-Byte-Jelly-Programme geben. Es ist erstaunlich, dass sich so viele davon als Antworten auf PPCG-Herausforderungen herausstellen.
Anush
8

Python 3 , 40 , 38 Bytes

lambda n:[*range(1,n,2),*range(0,n,2)]

Probieren Sie es online!

Das läuft O(n)pünktlich.

Danke an Dennis für das Speichern von 2 Bytes!

DJMcMayhem
quelle
Gewinner des schnellsten Preises! :)
Anush
Am schnellsten laufen oder zuerst gepostet?
WGroleau
2
@WGroleau Zuerst gebucht.
user202729
6

Haskell, 22 Bytes

f ist eine Funktion von n, die eine entsprechend geordnete Liste zurückgibt. Ich verwende die Option 1-Indizierung.

f n=[2,4..n]++[1,3..n]
Pinguino
quelle
6

Oktave , 17 Bytes

@(x)[2:2:x,1:2:x]

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.

Stewie Griffin
quelle
1
Sind nicht 3und 2nebeneinander in f(4)?
Pajonk
Ups ... behoben. Gleiche Byteanzahl. :-)
Stewie Griffin
5

JavaScript (ES6), 40 Byte

f=
n=>[...Array(i=n)].map(_=>(i+--i)%(n|1))
<input type=number min=4 oninput=o.textContent=f(+this.value).join`\n`><pre id=o>

Bearbeiten: 1 Byte dank @Arnauld gespeichert.

Neil
quelle
5

Gaia , 2 Bytes

r∫

Probieren Sie es online!

Dies einfach (stable) ORT die ganzen Zahlen im Bereich [1, Eingang] durch ihre pa r ity.

Mr. Xcoder
quelle
Gleicher Kommentar wie zu Jelly: Gewährleistet der Algorithmus oder die Definition der Sprache, dass die beiden Hälften jeweils in ihrer ursprünglichen Reihenfolge bleiben?
WGroleau
@WGroleau Ja, in Gaia ist der Sortier-Meta-Operator stabil.
Mr. Xcoder
5

R , 39 36 35 Bytes

function(x)c(seq(2,x,2),seq(1,x,2))

Probieren Sie es online!

ngm
quelle
Es gibt eine nachgestellte NA für ungerade Zahlen.
JayCe
Frau ist schuld. Wir mussten unsere Radtour machen, bevor ich das reparieren konnte. Aber Sie haben auch ein paar Bytes abgeschnitten.
ngm
Ja, ich hatte ein schlechtes Gewissen, Sie zu bitten, Bytes hinzuzufügen, also musste ich einen Weg finden, einige zu entfernen ... es hat gut funktioniert.
JayCe
4

Japt, 4 Bytes

Sie können auch ersetzen umit veiner anderen Ordnung zu bringen.

õ ñu

Versuch es

Oder, wenn wir ein Array von 2 Arrays ausgeben können:

õ ó

Versuch es

Zottelig
quelle
Technisch gibt der zweite eine Liste von Zahlen aus, die durch Kommas getrennt sind ;-) Beide schlagen 4leider fehl ; Sie können die ersten beheben , indem Sie uauf voder ozu õ.
ETHproductions
3

Mathematica, 50 -> 47 -> 42 Bytes

p = Join[Range[2, #, 2], Range[1, #, 2]] &

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

a[0] = a[1] = 1; a[2] = a[3] = 0;
a[n_] := a[n] = (n + 1)*a[n - 1] - (n - 2)*a[n - 2] - (n - 5)*a[n - 3] + (n - 3)*a[n - 4]

Probieren Sie es online!

Beispiel:

a[#] & /@ Range[4, 12]

{2, 14, 90, 646, 5242, 47622, ​​479306, 5296790, 63779034}

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.

Dr. Wolfgang Hintze
quelle
@ Stewie Griffin Da ich neu hier bin, erkläre bitte genauer, was du meinst. In meiner ersten Bemerkung habe ich einen Algorithmus und einen Code angegeben, der das Problem in der Polynomzeit löst. Daher sollte es als Lösung für die Herausforderung betrachtet werden. Der zweite Teil erweitert das interessante Problem. Daher sollte es als Kommentar angesehen werden.
Dr. Wolfgang Hintze
Ich habe mir erlaubt, Ihre Eingabe leicht zu ändern, damit Ihr Mathematica-Code ganz oben steht. Bei Code-Golf-Herausforderungen ist es obligatorisch, den tatsächlichen Code (so kurz wie möglich) anzugeben. So wie ich es formatiert habe, wird es zu einer Mathematica-Antwort, wie Sie es wahrscheinlich beabsichtigt haben, und Ihre ursprüngliche Erklärung ist immer noch darunter. Wenn Sie das Gefühl haben, dass etwas fehlt oder ich Ihre ursprüngliche Antwort falsch bearbeitet habe, können Sie es jederzeit selbst bearbeiten. Willkommen bei PPCG! :)
Kevin Cruijssen
@ Kevin Cruijssen Vielen Dank für den herzlichen Empfang und die Bearbeitung meines naiven Beitrags. Ich habe jetzt ein Mathematica-Programm für die zweite Bemerkung hinzugefügt. Das ist höchstwahrscheinlich nicht lege artis. Am allermeisten weiß ich nicht, wie man den netten "es online versuchen" -Link erstellt.
Dr. Wolfgang Hintze
Jeder Link kann mit erstellt werden [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.
Kevin Cruijssen
Entschuldigung für meinen etwas stumpfen Kommentar und die fehlende Antwort danach! Die Antwort wurde in der Überprüfungswarteschlange angezeigt, und ich habe den Code aufgrund der Formatierung nicht bemerkt. Es ist nicht ungewöhnlich, dass neue Benutzer "interessante Beobachtungen" zu Herausforderungen posten, ohne eine tatsächliche Antwort darauf zu geben. Während es in gutem Glauben getan wird, ist es nicht, worum es auf der Website geht. Ich dachte, das wäre so eine Antwort. Ich hätte auf Ihren Kommentar antworten sollen, aber ich hatte es eilig und konnte keinen neuen Kommentar schreiben. Stattdessen habe ich einfach den alten entfernt. Entschuldigung! Und willkommen auf der Seite! Ich hoffe du bleibst dabei! :)
Stewie Griffin
2

Leerzeichen , 161 Bytes

Hier ist die offizielle, unkommentierte Einreichung: Probieren Sie es online!

push_0   
read_n	
		push_0   
retreive_n			push_1  		
subtract	   dup_and_out[ 
 	
 	]label_s'
   
'push_2  		 
subtract	   dup[ 
 ]jump_next_if_neg:
		  
:dup_and_out[ 
 	
 	]else_jump_back:
 
 
:label_ss'
    
'push_0   
retreive_n			push_2  		 
subtract	   dup_and_out[ 
 	
 	]dup[ 
 ]jump_next:
 
    
:label_ssss'
      
'push_2  		 
subtract	   dup[ 
 ]jump_end_if_neg:
		   
:dup_and_out[ 
 	
 	]else_jump_back:
 
    
:label_sss'
     
'end



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:

[Space][Space][Space][N]                   Push a 0 on the stack
[Tab][Tab][N][Tab][Tab][Tab][Tab]          Read input value and store in heap
[Space][Space][Space][N]                   Push a 0 on the stack again
[Tab][Tab][Tab]                            Retrieve the value from the heap
[Space][Space][Tab][Tab][N]                Push a -1 on the stack
[Tab][Space][Space][Space]                 Add -1 to value
[Space][N][Space]                          Duplicate 
[Tab][N][Space][Tab]                       Output
[N][Space][Space][Space][N]                Set First Label
[Space][Space][Tab][Tab][Space][N]         Push a -2 on the stack
[Tab][Space][Space][Space]                 Subtract 2 from value
[Space][N][Space]                          Duplicate
[N][Tab][Tab][Space][Space][N]             If negative, jump to second label
[Space][N][Space]                          Duplicate
[Tab][N][Space][Tab]                       Output
[N][Space][N][Space][N]                    Jump back to first label
[N][Space][Space][Space][Space][N]         Set Second Label
[Space][Space][Space][N]                   Push a 0 on the stack
[Tab][Tab][Tab]                            Retrieve input value from heap again
[Space][Space][Tab][Tab][Space][N]         Push a -2 on the stack
[Tab][Space][Space][Space]                 This time, Add a -2 to the value
[Space][N][Space]                          Duplicate
[Tab][N][Space][Tab]                       Output
[Space][N][Space]                          Duplicate
[N][Space][N][Space][Tab][N]               Jump to third label
[N][Space][Space][Space][Tab][N]           Set third label
[Space][Space][Tab][Tab][Space][N]         Push a -2 on the stack
[Tab][Space][Space][Space]                 Subtract 2 from value
[Space][N][Space]                          Duplicate
[N][Tab][Tab][Space][Space][Space][N]      Jump to end if negative
[Space][N][Space]                          Duplicate
[Tab][N][Space][Tab]                       Output
[N][Space][N][Space][Tab][N]               Jump back to third label
[N][Space][Space][Space][Space][Space][N]  Set fourth label/end
[N][N][N]                                  Terminate
X1M4L
quelle
Einige Dinge zum Golfen: push_0, read_STDIN_as_int, push_0, retrievekann sein push_0, duplicate_0, read_STDIN_as_int, retrieve, ein Byte zu speichern. Und das erste Etikett kann ein leeres sein mit NSSNanstelle von NSSSN(und dann kann das zweite Etikett sein NSSSN; drittes NSSTNund viertes NSSSSN). Dies sollte ebenfalls 8 Bytes einsparen. Sie können auch das erste entfernen, Jump_to_third_labelda Sie bereits das Set_third_labelRecht darunter haben. Insgesamt: 140 Bytes ; (oder mit Kommentaren: Probieren Sie es online aus .) -3 Bytes, wenn Sie NNNexit entfernen .
Kevin Cruijssen
1

Gol> <> , 14 Bytes

FL:2%Z}:3=?$|B

Probieren Sie es online!

Beispiel volles Programm & wie es funktioniert

1AGIE;GDlR~
FL:2%Z}:3=?$|B

1AG          Register row 1 as function G
   IE;       Take number input; halt on EOF
      GD     Call G and print the stack
        lR~  Empty the stack
             Repeat indefinitely

F           |   Repeat n times...
 L              Push loop counter (0..n-1)
  :2%Z}         If even, move to bottom of the stack
       :3=?$    If top == 3, swap top two
                  This is activated only once to make [2 0 3 1]
             B  Return
Bubbler
quelle
1

J , 10 Bytes

i./:2|1+i.

Probieren Sie es online!

Erläuterung:

  /:          sort
i.            the numbers in the range 0..n-1 
    2|        according the remainder mod 2 of 
      1+i.    the numbers in the range 1..n   
Galen Ivanov
quelle
1

Java 8, 56 Bytes

n->{for(int i=n;i>0;)System.out.println((i+--i)%(n|1));}

Portierung der Antwort von @Neil auf JavaScript (ES6) .

Probieren Sie es online aus.


Alte 66 Bytes Antwort:

n->{String[]r={"",""};for(;n-->0;)r[n%2]+=n+" ";return r[0]+r[1];}

Probieren Sie es online aus.

Erläuterung:

n->{                  // Method with integer parameter and String return-type
  String[]r={"",""};  //  Result-Strings, both starting empty
  for(;n-->0;)        //  Loop in the range (n, 0]
    r[i%2]+=i+" ";    //   Append `i` and a space to one of the two result-Strings,
                      //   depending on if it is even (first) or odd (second)
  return r[0]+r[1];}  //  Return the two result-Strings appended to each other
Kevin Cruijssen
quelle
1

Ruby, 27 Bytes

->n{(1..n).sort_by{|i|i&1}}

Wie in diesem Antwort werden die nersten Ganzzahlen nach ihrem niedrigstwertigen Bit sortiert.

Probieren Sie es online!

Eric Duminil
quelle