Дайте перестановку без двух последовательных целых чисел рядом друг с другом

18

Вызов

Для целого числа n ≥ 4 выведите перестановку целых чисел [0, n-1] со свойством того, что никакие два последовательных целых числа (целые числа с абсолютной разностью 1) не стоят рядом друг с другом.

Примеры

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]

Вместо этого вы можете использовать 1-индексирование (используя целые числа [1, n] вместо [0, n-1] ).

Ваш код должен выполняться за полиномиальное время по n , поэтому вы не можете попробовать все перестановки и протестировать каждую.

code-golf restricted-complexity Ануш
источник

Когда вы говорите «вывести перестановку», вы имеете в виду как список? Или мы можем создать функцию, которая реализует само отображение перестановок?

xnor

@xnor Это должно быть выведено в некоторой удобочитаемой форме. Мне все равно, как именно.

Anush

Будет [[1,3],[0,2]]ли приемлемый формат вывода?

лохматый

@ Шэгги Это не здорово. Это значит 1,3,0,2?

Ануш

Связанные

Питер Тейлор

Ответы:

31

Желе , 3 2 байта

ḂÞ

Сортирует целые числа в [1, ..., n] по их LSB.

Попробуйте онлайн!

Деннис
источник

Вот это да! Это удивительно.

Ануш

2

«Сортировка по LSB» означает, что все остальные перемещаются в начало, но требует ли определение желе, чтобы числа в каждой половине оставались в своем первоначальном порядке? Если нет, то 100 (4) может быть рядом с 101 (5) и все же быть «отсортировано по LSB». Не нарушая ваш код, но, возможно, описательный комментарий не завершен?

WGroleau

1

@WGroleau Да, Þстабильная сортировка, потому что она реализована с использованием sortedфункции Python , которая гарантированно стабильна .

user202729

3

Алгоритм для меня более впечатляющий, чем маленький размер, по своей хитрости. Вы также можете, я полагаю, изменить порядок следования битов, отсортировать и вернуть его обратно.

WGroleau

4

Может быть только 65536 различных двухбайтовых программ Jelly. Это удивительно , что многие из тех , кто оказываются ответы на ppcg вызовы.

Ануш

16

Python 2 , 32 байта

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

Попробуйте онлайн!

овс
источник

8

Python 3 , 40 , 38 байт

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

Попробуйте онлайн!

Это работает во O(n)времени.

Спасибо Деннису за сохранение 2 байта!

DJMcMayhem
источник

Победитель самого быстрого приза! :)

Anush

Быстрее всего работает или впервые опубликовано?

WGroleau

2

@WGroleau Первое сообщение.

user202729

6

Python 2 , 34 байта

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

Попробуйте онлайн!

Python 2 , 40 байт

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

Попробуйте онлайн!

XNOR
источник

6

Haskell, 22 байта

f является функцией n, которая возвращает соответственно упорядоченный список. Я использую опцию 1-indexing.

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

Penguino
источник

6

Октава , 17 байт

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

Попробуйте онлайн!

Это использует тот же подход, что и многие другие. Объединить два вектора, один со всеми четными числами в включающем диапазоне 2 ... x , и все нечетные числа в включающем диапазоне 1 ... x . Синтаксис должен быть достаточно очевидным, поэтому я не буду это объяснять.

Стьюи Гриффин
источник

1

Не является 3и 2рядом друг с другом f(4)?

pajonk

Упс ... исправлено. Тот же счетчик байтов. :-)

Стьюи Гриффин

5

JavaScript (ES6), 40 байт

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>

Развернуть фрагмент

Редактировать: 1 байт сохранен благодаря @Arnauld.

Нил
источник

5

Gaia , 2 байта

r∫

Попробуйте онлайн!

Это просто (устойчиво) ∫ ORTS целых чисел в диапазоне [1,] входные их ра г Ity.

Мистер Xcoder
источник

Тот же комментарий, что и для Jelly: алгоритм или определение языка гарантируют, что каждая из двух половинок останется в своем первоначальном порядке?

WGroleau

@WGroleau Да, в Gaia мета-оператор сортировки стабилен.

г-н Xcoder

5

R , 39 36 35 байт

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

Попробуйте онлайн!

НГМ
источник

Для нечетных чисел есть конечный NA.

JayCe

tio.run/#%23K/qfZvs/…

JayCe

Вина жены Мы должны были покататься на велосипеде, прежде чем я смог это исправить. Но ты тоже сбрил несколько байтов.

НГМ

Да, я чувствовал себя плохо, прося вас добавить байты, поэтому мне пришлось искать способ удалить некоторые ... это сработало хорошо.

JayCe

1

вдохновлен октавным ответом

Джузеппе

4

05AB1E , 3 байта

Порт DJMcMayhem's Python ответ и ответ Дениса Желе

ÝΣÉ

Попробуйте онлайн!

Как?

ÝΣÉ - 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

Джонатан Аллан
источник

4

Japt, 4 байта

Вы также можете заменить uна, vчтобы получить другой заказ.

õ ñu

Попытайся

Или, если мы можем вывести массив из 2 массивов:

õ ó

Попытайся

мохнатый
источник

Технически второй выводит список чисел, разделенных запятыми ;-) Оба 4, к сожалению, не работают; Вы можете установить первый, изменив uв vили oна õ.

ETHproductions

3

Mathematica, 50 -> 47 -> 42 байта

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

Попробуйте онлайн!

Спасибо user202729 за указание на двойной потенциал оптимизации Join [] вместо Flatten [] и использование чистых функций.

Я хотел бы добавить два замечания.

1) Довольно просто построить определенную перестановку без последовательности падения или нарастания при n> = 4 в соответствии с запросом n OP.

Он состоит из двух последовательных списков.

Для четного n это:
list1 = (2,4, ..., n / 2)
list2 = (1,3, ..., n / 2-1)

Для нечетного n имеем:
list1 = (2,4, ..., Floor [n / 2])
list2 = (1,3, ..., Floor [n / 2])

Для этого «алгоритма» должно быть принято только одно решение (n четных или нечетных), а остальные просто записывают n чисел.

Возможное решение Mathematica предоставляется в верхней части.

2) С этим связан вопрос, сколько таких перестановок существует в зависимости от n.

Mathematica, 124 байта

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]

Попробуйте онлайн!

Пример:

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

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

Подсчет количества таких перестановок является стандартной задачей.

Для n = 4 есть 2: {{2,4,1,3}, {3,1,4,2}}

Для n = 5 существует 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}}

Число a (n) этих перестановок быстро возрастает: 2, 14, 90, 646, 5242, 47622, 479306, 5296790, 63779034, ...

Для больших n отношение a (n) / n! кажется, приближается к пределу 1 / e ^ 2 = 0,135335 ... У меня нет строгих доказательств, но это всего лишь предположение из численных доказательств. Вы можете проверить это, попытавшись запустить программу онлайн.

Программа выше (на основе ссылки, приведенной ниже) рассчитывает эти числа.

Вы можете найти больше информации в соответствующей последовательности на OEIS: A002464 . Проблема Герцшпрунга: способы размещения n неагрессивных королей на доске n X n, по 1 в каждом ряду и столбце. Также число перестановок длины n без последовательностей роста или падения.

Доктор Вольфганг Хинце
источник

@ Stewie Griffin Поскольку я новичок здесь, пожалуйста, объясни более подробно, что ты имеешь в виду. В своем первом замечании я предоставил алгоритм и код, который решает проблему за полиномиальное время. Следовательно, это должно рассматриваться как решение проблемы. Вторая часть расширяет интересную проблему. Следовательно, это следует рассматривать как комментарий.

Доктор Вольфганг Хинце

Я позволил себе немного изменить ваше представление, чтобы ваш код Mathematica был наверху. При вызовах code-golf обязательно указывать фактический код (максимально короткий). То, как я его отформатировал, становится ответом Mathematica, как вы, вероятно, и предполагали, и под вашим исходным объяснением. Если вы чувствуете, что чего-то не хватает или я неправильно отредактировал ваш первоначальный ответ, не стесняйтесь редактировать его самостоятельно. Добро пожаловать в PPCG! :)

Кевин Круйссен

@ Kevin Cruijssen Большое спасибо за теплый прием и редактирование моего наивного представления. Теперь я добавил программу Mathematica для второго замечания. Что, скорее всего, не Lege Artis. Больше всего я не знаю, как создать красивую ссылку "попробуй онлайн".

Доктор Вольфганг Хинце

Любая ссылка может быть создана с помощью [some text](the_link). Что касается ссылки «Попробуйте онлайн», в частности, веб-сайт https://tio.run/ , который размещается на нашем собственном @Dennis, содержит ссылки на все виды языков программирования. Wolfram Language (Mathematica) является одним из них. Вверху вы можете нажать кнопку воспроизведения, чтобы запустить код, или кнопку гиперссылки, чтобы скопировать «Попробуйте онлайн». (markup-) ссылка. И вы можете разделить ваш код на фактический «Код» (ваше представление) с помощью дополнительного верхнего / нижнего колонтитула для (красивой) печати одного или нескольких тестовых случаев.

Кевин Круйссен

Извиняюсь за мой несколько грубый комментарий, и отсутствие ответа после этого! Ответ появился в очереди на просмотр, и я не заметил код из-за форматирования. Нередки случаи, когда новые пользователи публикуют «интересные наблюдения» на вызовы, не давая реального ответа на них. Хотя это сделано добросовестно, это не то, о чем сайт. Я думал, что это был такой ответ. Я должен был ответить на ваш комментарий, но я торопился и не смог написать новый комментарий, поэтому вместо этого я просто удалил старый. Извиняюсь! И добро пожаловать на сайт! Я надеюсь, что вы останетесь здесь! :)

Стьюи Гриффин,

2

JavaScript (Node.js) , 42 байта

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

Попробуйте онлайн!

JavaScript (Node.js) , 47 байт

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

Попробуйте онлайн!

l4m2
источник

2

Рубин , 27 байт

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

Попробуйте онлайн!

Использование 1-индексации

гигабайт
источник

2

Пробел , 161 байт

Вот официальное, некомментированное представление: попробуйте онлайн!

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

Попробуйте онлайн!

Я пожертвовал несколькими байтами, чтобы программа работала без ошибок, я считаю, что я могу потерять около 7-8 байтов, и все равно будет выводиться правильно, но он также будет выводить сообщения об ошибках, и никто этого не хочет.

Полное Байт Объяснение:

[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
источник

Некоторые вещи в гольф: push_0, read_STDIN_as_int, push_0, retrieveможно push_0, duplicate_0, read_STDIN_as_int, retrieveсэкономить байт. И первая метка может быть пустой с NSSNвместо NSSSN(а затем вторая метка может быть NSSSN; третья NSSTN; и четвертая NSSSSN). Это также должно сэкономить 8 байт. Кроме того, вы можете удалить первый, Jump_to_third_labelпотому что у вас уже есть Set_third_labelправо под ним. Всего: 140 байт ; (или с комментариями: попробуйте онлайн .) -3 байта, если вы удалите NNNвыход.

Кевин Круйссен

1

F # (моно) , 27 байтов

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

Попробуйте онлайн!

Хенрик Хансен
источник

1

Gol> <> , 14 байт

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

Попробуйте онлайн!

Пример полной программы и как она работает

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

фонтанчик для питья
источник

1

J , 10 байт

i./:2|1+i.

Попробуйте онлайн!

Объяснение:

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

Гален Иванов
источник

1

Java 8, 56 байт

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

Порт ответа @Neil на JavaScript (ES6) .

Попробуйте онлайн.

Старый 66-байтовый ответ:

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

Попробуйте онлайн.

Объяснение:

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

Кевин Круйссен
источник

1

Рубин, 27 байт

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

Как и в этом ответе , nпервые целые числа отсортированы по их младшему значащему биту.

Попробуйте онлайн!

Эрик Думинил
источник