Tantangan

Diberikan bilangan bulat n ≥ 4 , menghasilkan permutasi bilangan bulat [0, n-1] dengan properti yang tidak memiliki dua bilangan bulat berturut-turut (bilangan bulat dengan selisih mutlak 1) berada di samping satu sama lain.

Contohnya

• 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]

Anda dapat menggunakan pengindeksan 1 sebagai gantinya (menggunakan bilangan bulat [1, n] alih-alih [0, n-1] ).

Kode Anda harus dijalankan dalam waktu polinomial dalam n , sehingga Anda tidak dapat mencoba semua permutasi dan menguji masing-masing.

Jelly , 3 2 byte

ḂÞ

Mengurutkan bilangan bulat dalam [1, ..., n] oleh LSB mereka.

Cobalah online!

Python 2 , 32 byte

lambda n:(range(n|1)*2)[1:n*2:2]

Cobalah online!

Python 3 , 40 , 38 byte

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

Cobalah online!

Ini berjalan dalam O(n)waktu.

Terima kasih kepada Dennis karena telah menghemat 2 byte!

Python 2 , 34 byte

lambda n:range(1,n,2)+range(0,n,2)

Cobalah online!

Python 2 , 40 byte

lambda n:[(k-~k)%(n|1)for k in range(n)]

Cobalah online!

Haskell, 22 byte

f adalah fungsi dari n yang mengembalikan daftar yang dipesan dengan tepat. Saya menggunakan opsi pengindeksan 1.

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

Oktaf , 17 byte

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

Cobalah online!

Ini menggunakan pendekatan yang sama seperti yang lainnya. Menggabungkan dua vektor, satu dengan semua angka genap dalam rentang inklusif 2 ... x , dan semua angka ganjil dalam rentang inklusif 1 ... x . Sintaksnya harus cukup jelas, jadi saya tidak akan menjelaskannya.

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>

Sunting: Disimpan 1 byte berkat @Arnauld.

Gaia , 2 byte

r∫

Cobalah online!

Ini hanya (stabil) ∫ Orts bilangan bulat dalam rentang [1, masukan] oleh mereka pa r ity.

R , 39 36 35 byte

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

Cobalah online!

05AB1E , 3 byte

Port jawaban Python DJMcMayhem dan Dennis's Jelly menjawab

ÝΣÉ

Cobalah online!

Bagaimana?

ÝΣÉ - implicitly take input onto stack  e.g. 7
Ý   - pop a and push range(a)               [0,1,2,3,4,5,6]
 Σ  - sort by (stable):
  É -   is even? (x%2==0 ?)                 [1,3,5,0,2,4,6]
    - implicit print of top of stack

Japt, 4 byte

Anda juga bisa mengganti udengan vuntuk mendapatkan pesanan yang berbeda.

õ ñu

Cobalah

Atau, jika kita dapat menggunakan array 2 array:

õ ó

Cobalah

Mathematica, 50 -> 47 -> 42 byte

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

Cobalah online!

Terima kasih kepada pengguna202729 untuk menunjukkan potensi pengoptimalan dua kali lipat Bergabung [] dipasang pada Flatten [] dan menggunakan fungsi murni.

Saya ingin menambahkan dua komentar.

1) Cukup mudah untuk membangun permutasi spesifik tanpa penurunan atau peningkatan suksesi untuk n> = 4 seperti yang diminta pada OP.

Ini terdiri dari dua daftar berturut-turut.

Untuk genap n ini adalah:
list1 = (2,4, ..., n / 2)
list2 = (1,3, ..., n / 2-1)

Untuk ganjil dan n kita memiliki:
list1 = (2,4, ..., Lantai [n / 2])
list2 = (1,3, ..., Lantai [n / 2])

Untuk "algoritma" ini, hanya satu keputusan yang harus dibuat (n genap atau ganjil), sisanya hanya menuliskan n angka.

Kemungkinan solusi Mathematica disediakan di bagian atas.

2) Pertanyaan terkait adalah berapa banyak izin seperti itu ada sebagai fungsi dari n.

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]

Cobalah online!

Contoh:

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

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

Untuk menghitung jumlah permutasi tersebut merupakan masalah standar.

Untuk n = 4 ada 2: {{2,4,1,3}, {3,1,4,2}}

Untuk n = 5 ada 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}}

Jumlah a (n) dari permutasi ini naik dengan cepat: 2, 14, 90, 646, 5242, 47622, ​​479306, 5296790, 63779034, ...

Untuk n besar rasio a (n) / n! tampaknya mendekati batas 1 / e ^ 2 = 0,135335 ... Saya tidak punya bukti ketat tetapi itu hanya dugaan dari bukti numerik. Anda dapat menguji ini dengan mencoba menjalankan program secara online.

Program di atas (berdasarkan referensi yang diberikan di bawah) menghitung angka-angka ini.

Anda dapat menemukan informasi lebih lanjut dalam urutan yang relevan di OEIS: A002464 . Masalah Hertzsprung: cara untuk mengatur dan tidak menyerang raja di papan xx, dengan 1 di setiap baris dan kolom. Juga jumlah permutasi panjang n tanpa naik atau turunnya suksesi.

JavaScript (Node.js) , 42 byte

n=>(f=i=>i<n?[i,...f(i+2)]:i&1?[]:f(1))(0)

Cobalah online!

JavaScript (Node.js) , 47 byte

n=>(f=i=>i--?[n--*2%(N|1)+N%2,...f(i)]:[])(N=n)

Cobalah online!

Ruby , 27 byte

->n{[*2.step(n,2)]|[*1..n]}

Cobalah online!

Menggunakan pengindeksan 1

Spasi , 161 byte

Inilah pengajuan resmi dan tidak diomentari: Coba 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

Cobalah online!

Saya mengorbankan beberapa byte sehingga program akan berjalan tanpa kesalahan, saya percaya bahwa saya bisa kehilangan sekitar 7-8 byte, dan masih akan menampilkan dengan benar, tetapi juga akan menghasilkan pesan kesalahan, dan tidak ada yang menginginkan itu.

Penjelasan Byte Lengkap:

[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

F # (Mono) , 27 byte

let f n=[2..2..n]@[1..2..n]

Cobalah online!

Gol> <> , 14 byte

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

Cobalah online!

Contoh program lengkap & Cara kerjanya

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

J , 10 byte

i./:2|1+i.

Cobalah online!

Penjelasan:

  /:          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   

Java 8, 56 byte

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

Pelabuhan @ Neil JavaScript (ES6) jawaban 's .

Cobalah online.

Jawaban 66 byte lama:

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

Cobalah online.

Penjelasan:

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

Ruby, 27 byte

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

Seperti dalam jawaban ini , nbilangan bulat pertama diurutkan berdasarkan bagian yang paling tidak signifikan.

Cobalah online!