Вступление

Я определил класс перестановок муравьев в более раннем испытании . Напомним, что перестановка p чисел от 0 до r-1 является сложной, если для каждой записи p [i], кроме первой, существует более ранняя запись p [ik] такая, что p [i] == p [ ик] ± 1 . В качестве забавного факта я также заявил, что для r ≥ 1 существует ровно 2 ^r-1 перестановки antsy длины r . Это означает, что существует взаимно-однозначное соответствие между перестановками antsy длины r и двоичными векторами длины r-1., В этой задаче ваша задача - реализовать такую ​​переписку.

Задание

Ваша задача - написать программу или функцию, которая принимает двоичный вектор длиной 1 ≤ n ≤ 99 и выводит перестановку antsy длины n + 1 . Перестановка может быть либо на основе 0, либо на основе 1 (но это должно быть согласовано), а вход и выход могут быть в любом приемлемом формате. Кроме того, разные входы всегда должны давать разные выходы; кроме этого, вы можете возвращать любую перестановку, которую хотите.

Побеждает самое низкое число байтов.

пример

Перестановки (основанные на 0) длиной 4

0 1 2 3
1 0 2 3
1 2 0 3
1 2 3 0
2 1 0 3
2 1 3 0
2 3 1 0
3 2 1 0

и ваша программа должна вернуть один из них для каждого из восьми битовых векторов длины 3:

0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

Желе , 12 11 10 байт

ḟẋLṭ+
0;ç/

Попробуйте онлайн! или генерировать все перестановки длины 4 .

Как это устроено

0;ç/   Main link. Argument: B (bit array)

0;     Prepend a 0 to B.
  ç/   Reduce [0] + B by the helper link.


ḟẋLṭ+  Helper link. Left argument: A (array or 0). Right argument: b (bit)

 ẋ     Repeat A b times, yielding A or [].
ḟ      Filter false; remove the elements of A or [] from A.
  L    Get the length of the resulting array.
       This yield len(A) if b = 0 and 0 if b = 1.
    +  Add b to all elements of A.
   ṭ   Tack; append the result to the left to the result to the right.

Python 2, 62 60 байт

x=0,
for n in input():x=[t-n+1for t in x]+[n*len(x)]
print x

Спасибо @xnor за 2 байта!

Проверьте это на Ideone .

Python, 54 байта

lambda l:[i-i*x+sum(l[i:])for i,x in enumerate([1]+l)]

Использует следующую процедуру:

1. Добавьте 1 к списку.
2. Для каждой записи 0 напишите свою позицию в списке с 0 индексами.
3. Для каждой записи напишите число 1 справа от нее, не считая себя.
4. Добавьте результаты шагов 2 и 3 по отдельности.

Например, l=[1,0,1,0]даетf(l) == [2,1,3,0,4]

List with prepended 1         1 1 0 1 0

0-indexed position for 0's        2   4
Number of 1's to right        2 1 1 0 0
Sum of above two              2 1 3 0 4

Добавление 0 также даст тот же результат. Это enumerateнеуклюжий, я посмотрю, может ли это сделать лучше рекурсивно.

JavaScript (ES6), 48 47 45 байт

a=>[h=l=0,...a.map(c=>c?--l:++h)].map(e=>e-l)

Это оказалось похоже на метод @ETHproductions, за исключением того, что я начал с прямого вычисления первого элемента, а затем использовал двоичный вектор, чтобы определить, является ли каждая цифра новым максимумом или новым минимумом. Редактировать: 1 байт сохранен благодаря @ETHproductions. Сохранено 2 байта, начиная с нуля и корректируя впоследствии. Мой предыдущий метод оказался похожим на метод @ Dennis, но занял 54 байта:

a=>a.reduce((r,b)=>[...r.map(e=>b+e),r.length*!b],[0])

Perl, 33 байта

Включает +1 для -p

Задать вектор как строку без пробелов в STDIN:

antsy.pl <<< 110

antsy.pl:

#!/usr/bin/perl -p
s%^|.%y/0//+($&?++$a:$b--).$"%eg

JavaScript (ES6), 52 байта

v=>[...v,l=0].map(x=>x?l++:h--,h=v.length).reverse()

Проверьте это:

f=v=>[...v,l=0].map(x=>x?l++:h--,h=v.length).reverse()
g=v=>console.log(f((v.match(/[01]/g)||[]).map(x=>+x)))

<input oninput="g(this.value)" value="010">

объяснение

Это использует тот факт, что при перестановке перестановок каждый элемент либо на 1 больше, чем максимум предыдущих низких записей, либо на 1 меньше, чем минимум предыдущих высоких записей. Обозначая более высокий элемент как a 0и более низкий элемент как a 1, мы можем создать точное взаимно-однозначное соответствие между перестановками antsy длины n и двоичными векторами длины n - 1 .

Лучшее, что я мог сделать с техникой Денниса, это 57 51 байт:

v=>v.reduce((x,n)=>[...x.map(i=>i+n),!n*++j],[j=0])
v=>v.map(n=>x=[...x.map(i=>i+n),!n*++j],x=[j=0])&&x

Решение xnor - 56 (сохранено 1 байт благодаря @Neil):

l=>[1,...l].map((x,i)=>i*!x+eval(l.slice(i).join`+`||0))

Haskell, 40 байт

foldl(\r a->map(+0^a)r++[a*length r])[0]

Решение Python Денниса прекрасно в Haskell с mapи fold. Это короче, чем мои попытки портировать мою прямую входную конструкцию:

f l=[i*0^x+sum(drop i l)|(i,x)<-zip[0..]$0:l]
f l=[a+c-b*c|(a,c,b)<-zip3(scanr(+)0l)[0..]$0:l]

Пакет, 127 байт

@set s=%*
@set/an=h=l=%s: =+%
@for %%b in (%*)do @call:%%b
:0
@echo %n%
@set/an=h+=1
@exit/b
:1
@echo %n%
@set/an=l-=1

Принимает ввод в качестве параметров командной строки, вывод разделяется строкой. (Можно вводить через STDIN как разделенные пробелами без дополнительных затрат.)