Сортировать список различий

22

Список различий в списке целых чисел - это список различий последовательных членов.

Например, список различий

1, 3, 2 ,4

является

2, -1, 2

Ваша задача - взять в качестве входных данных список различий и вывести, как будет выглядеть список различий, если бы исходный список был отсортирован.

Например список различий

2, 1, -2, -1

Может представлять список

2 4 5 3 2

Который при сортировке

2 2 3 4 5

Который имеет список различий

0 1 1 1

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

code-golf array-manipulation Мастер пшеницы
источник
Гарантируются ли решения уникальными?
H.PWiz
@ H.PWiz Да, они есть.
Пшеничный волшебник
Связанный.
полностью человек
1
@ H.PWiz Быстрое доказательство: список полностью восстанавливаем из списка различий (DL) в сочетании со значением первого элемента, поэтому существует преобразование один в один из L в (FV, DL). Увеличение FV на любую величину равнозначно добавлению этой суммы к каждому элементу L, и поэтому оно не может изменить сортировку L, если это сравнение является соответственно монотонным. (Другими словами, это не влияет на сортировку, если только число, которое вы добавляете, не вызывает целочисленное переполнение).
ЧР Дрост
1
Не могли бы вы добавить еще несколько тестов? Я заметил, что некоторые решения дают разные результаты [-2, 100, -2, -1], например.
Лохматый

Ответы:

16

05AB1E , 4 байта

.¥{¥

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

объяснение

.¥{¥
.¥   # Undelta the input list
  {  # Sort it
   ¥ # And get the deltas
Datboi
источник
Undelta05AB1E имеет большинство встроенных ниш. o0
полностью человек
2
Ах, чёрт, побей меня к этому. Я всегда хотел использовать undelta.
Волшебная Урна Осьминога
16
Undeltaಠ ___ ಠ
Business Cat
1
«Унделта» - это просто накопительная сумма, верно?
Згарб
2
@Zgarb Undelta добавляет 0 в качестве первого элемента списка, а затем в точности, как вы сказали, кумулятивную сумму или обратную дельту.
Волшебная Урна Осьминога
9

Python 3 с Numpy , 56 54 53 байта

2 байта отключены благодаря @Artyer (Numpy's sortвместо стандартного sorted). 1 байт благодаря @notjagan (переходит 0в cumsum)

lambda x:diff(sort(cumsum([0]+x)))
from numpy import*

Код определяет анонимную функцию, которая вводит список или массив Numpy и выводит массив Numpy.

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

Луис Мендо
источник
1
Вау, ты научил меня чему-то новому сегодня. Мой подход numpyбыл намного дольше. Я вернусь завтра, чтобы выразить это, потому что вижу, что ты уже в шапке. Очень хорошо!
г-н Xcoder
@ Mr.Xcoder Спасибо! Я не эксперт по Numpy, я просто следовал тому, что сделал бы в Matlab: diff(sort([0 cumsum(x)]))(в Matlab [ ]- конкатенация)
Луис Мендо,
Обязанность выполнена!
г-н Xcoder
-1 байт , перемещая 0в cumsum.
notjagan
5

Mathematica, 40 байт

Differences@Sort@Accumulate@Join[{1},#]&
J42161217
источник
Differences@Sort@FoldList[+##&,1,#]&
алефальфа
4

Шелуха , 4 байта

Ẋ-O∫

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

Explaination

      -- implicit input, e.g                               [2,1,-2,-1]
   ∫  -- cumulative sum                                    [0,2,3,1,0]
  O   -- sort                                              [0,0,1,2,3]
Ẋ     -- apply function to all adjacent pairs in the list  [(0,0),(0,1),(1,2),(2,3)]
 -    --   subtract                                        [0,1,1,1]
H.PWiz
источник
Еще один язык, на котором есть унделта? Или какой-нибудь любитель встроенный?
г-н Xcoder
@Мистер. Xcoder Случается так, что константа такая же, как ундельта
H.PWiz
@ H.PWiz На самом деле это не то, что мы называем cumsum ... если только вы не примете во внимание пустой префикс.
Эрик Outgolfer
@EriktheOutgolfer Да, именно так и поступает шелуха, как и scanl(+)0в Haskell.
H.PWiz
4

Pyth , 9 байт

-1 байт благодаря @EriktheOutgolfer .

.+S+0sM._

Тестирование.

Pyth , 10 байт

.+S.u+YNQ0

Попробуйте онлайн! или попробуйте больше тестовых случаев .

Мистер Xcoder
источник
Как и в моем (удаленном) ответе, вы можете использовать +0sM._вместо .u+YNQ0-1.
Эрик Outgolfer
@EriktheOutgolfer Почему вы удалили его?
мистер Xcoder
Думал, что основная идея была слишком похожа на вашу.
Эрик Outgolfer
@EriktheOutgolfer Хорошо, спасибо тогда
г-н Xcoder
m=+Zвариант такой же длины sM._, но, к сожалению, не похоже, что он может быть короче.
FryAmTheEggman
4

JavaScript (ES6), 57 56 байт

Сохранено 1 байт благодаря @ETHproductions

a=>a.map(n=>t-=n,p=t=0).sort((a,b)=>b-a).map(n=>p-(p=n))

демонстрация

Показать фрагмент кода

Arnauld
источник
.sort((a,b)=>a-b)Это способ получить дельты? Сортировка с вычитанием? : P
полностью человек
@totallyhuman Первый map()дает дельты. Этот код сортирует их. 2-я карта перестраивает новые дельты. Метод JS sort()по умолчанию использует лексикографический порядок. Итак, нам нужен этот специализированный обратный вызов для номеров> 9 (к сожалению).
Арно,
Это -p+(p=n)раздражает меня, но, к сожалению, лучшего способа нет ... если только ...
ETHproductions
какого черта, я не нажал кнопку отправки> _ <Но в любом случае, я думаю , что вы можете сохранить байт с этим редактированием ...
ETHproductions
@ETHproductions Спасибо :-)
Арно
3

Java 8, 123 байта

Стандартное решение: ввод суммарной суммы, сортировка, затем дифференциал. Никаких существенных уловок реализации также.

l->{int s=l.length,d[]=new int[s+1],i=0;while(i<s)d[i+1]=d[i]+l[i++];for(java.util.Arrays.sort(d);i-->0;)l[i]=d[i+1]-d[i];}

В ролях Consumer<int[]>. Выход является мутированным входом.

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

Неуправляемая лямбда

l -> {
    int
        s = l.length,
        d[] = new int[s + 1],
        i = 0
    ;
    while (i < s)
        d[i + 1] = d[i] + l[i++];
    for (java.util.Arrays.sort(d); i-- > 0; )
        l[i] = d[i + 1] - d[i];
}

Подтверждения

  • -3 байта благодаря Оливье Грегуару , мастеру нечестивой автоинкрементации
  • -1 байт благодаря Nevay
Jakob
источник
1
Вы можете сыграть в гольф 3 байта, переставив позиции, в которых вы делаете свои приращения и ваши общие вычисления: l->{int s=l.length,d[]=new int[s+1],i=0;for(;i<s;)d[i+1]=d[i]+l[i++];java.util.Arrays.sort(d);for(i=0;i<s;)l[i]=-d[i]+d[++i];}(остерегайтесь невидимых символов SE при копировании / вставке)
Оливье Грегуар
1
Спасибо за мой новый титул;) Вот еще один декремент о нечестии, чтобы праздновать for(;i>0;)l[i-1]=d[i]-d[--i];(последний цикл)
Оливье Грегуар
Я только что переделал эту петлю сам, достигнув for(;i-->0;)l[i]=d[i+1]-d[i];такой же длины. Обновление впереди.
Якоб
2
Вы можете сохранить 1 байт, используя l->{int s=l.length,d[]=new int[s+1],i=0;while(i<s)d[i+1]=d[i]+l[i++];for(java.util.Arrays.sort(d);i-->0;l[i]=d[i+1]-d[i]);}.
Невай
Ах да, конечно. Благодарность!
Якоб
2

R , 31 32 байта

-4 байта спасибо @ user2390246 за diffinv

+5 байтов от Ярко за cat

cat(diff(sort(diffinv(scan()))))

Читает из стандартного ввода, пишет в стандартный вывод. diffinvявляется обратной diffвеличиной для данного начального значения (по умолчанию 0). Так как он diffснова издан, не имеет значения, что это за значение.

Как указал Ярко Дуббелдам, мне нужно было правильно вывести результат, стоимостью пять байтов. Увы.

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

Giuseppe
источник
Это то, что я тоже имел в виду. Нужно ли обрабатывать печать, хотя, поскольку она выполняется как полная программа (через source), она ничего не выводит.
JAD
1
Если вы используете, diffinvа не cumsumвам не нужно добавлять ноль.
user2390246
@ user2390246 вау, очень мило! ТИЛ о диффинв.
Джузеппе
Я тоже! У меня просто был быстрый поиск, чтобы увидеть, были ли какие-либо предыдущие ответы, к которым я мог бы применить это.
user2390246
1

Python 2 , 83 байта

l,r=input(),[1]
for i in l:r+=[r[-1]+i]
r.sort()
print[b-a for a,b in zip(r,r[1:])]

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

Ужасное решение.

totallyhuman
источник
На самом деле это не так страшно
мистер Xcoder
+=Оператор Python для списков работает с любой итерацией, поэтому вы можете использовать r+=r[-1]+i,вместо r+=[r[-1]+i]одного байта и сохранять его.
Джонатан Фрех
1

Perl 6 , 46 байт

{[\+](0,|@_).sort.rotor(2=>-1).flat.map(*R-*)}

Попытайся

Expanded:

{  # bare block lambda with implicit signature :(*@_)

  [\+](         # triangle reduce using &infix:«+»
    0,          # start with 0
    |@_         # Slip in the arguments from the outer block
  )             #                  (0, 2, 3, 1, 0)

  .sort         # sort the results (0,0,1,2,3)
  .rotor(2=>-1) # group in twos    ((0,0),(0,1),(1,2),(2,3))
  .flat         # flatten          (0,0,0,1,1,2,2,3)
  .map(*R-*)    # grab 2 values at a time, and subtract first from second
                # (0, 1, 1, 1)
}
Брэд Гилберт b2gills
источник
1

Haskell , 74 байта

import Data.List
g=sort.scanl(+)0
h l|k<-g l=map(\(x,y)->x-y)$zip(tail$k)k

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

Непосредственная.

jferard
источник
3
=<<от функции монады пригождается: (zipWith(-)=<<tail).sort.scanl(+)0
Ними
@nimi Очень мило. Я не знаток монад, но я должен был подумать zipWith.
Jferard
1

TI-Basic (TI-84 Plus CE), 23 байта

Prompt X
augment({0},cumSum(LX→X
SortA(LX
ΔList(LX

Запрашивает ввод пользователя. Список должен быть введен с начальным {, с номерами, разделенными ,, и с дополнительным трейлингом }.

TI-Basic - это токенизированный язык ; ΔList(и cumSum(являются двухбайтовыми токенами, все остальные используемые токены по одному байту каждый.

Пример выполнения (с NAMEуказанием имени программы и {4,-2,7,-4,0}ввода):

prgmNAME
X=?{4,-2,7,-4,0}
               {2 2 1 0 4}

Объяснение:

Prompt X                  # 3 bytes, get list input, store in LX
augment({0},cumSum(LX→X   # 12 bytes, 
          # store the list ({0} prepended to the cumulative sum of LX) to LX
SortA(LX                  # 4 bytes, sort LX ascending
ΔList(LX                  # 4 bytes, implicitly print the difference list of LX
pizzapants184
источник
Вам нужно это L?
Захари
@ Zacharý вы можете опустить их при сохранении списка, но если пропустить их при ссылках, это будет означать числовую переменную X вместо списка
pizzapants184
1

C ++ (gcc) , 136 байт

Как неназванная общая лямбда, предполагая, что ввод будет похожим, std::listи возвращая через опорный параметр.

[](auto&L){auto r=L.begin(),l=L.insert(r,0);while(r!=L.end())*r+++=*l++;for(L.sort(),l=r=--L.end();--l!=L.begin();*r---=*l);L.erase(l);}

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

Ungolfed:

[](auto&L){
 auto r=L.begin(),
      l=L.insert(r,0); //adds a zero right in front
 while(r!=L.end())
   *r++ += *l++;       //sum left to right
 for(
  L.sort(),            //sorting invalidates the iterators
  l=r=--L.end();       //so, reinit
  --l!=L.begin();      //decrement l beforehand 
  *r-- -= *l           //diff right to left
 );
 L.erase(l);           //l==L.begin(), so this removes the temporary 0
}
Карл Напф
источник
1

Pyth, 8 байт

.+S+M.uP

демонстрация

.+S+M.uP
.+S+M.uPNQ    Implicit variables
     .u  Q    Apply the following function to the input repeatedly until it
              stops changing, then output the list of values, including the
              starting value.
       PN     Remove the last element. No-op if the list is empty.
   +M         Sum each list. This gives the cumulative sums in reverse order,
              including a 0 at the end for the empty list.
  S           Sort
.+            Deltas
isaacg
источник
+1 Это аккуратный обходной путь с кумулятивной фиксированной точкой. Я лично даже не думал об этом.
г-н Xcoder
1

TI-Basic, 20 байтов

cumSum(augment({0},Ans->L1
SortA(L1
ΔList(L1
Timtech
источник
1

VB.NET (.NET 4.5), 109 байт

Sub A(n)
Dim c=n.count-1
For i=1To c
n(i)+=n(i-1)
Next
n.Sort()
For i=c To 1 Step-1
n(i)-=n(i-1)
Next
End Sub

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

  1. Восстанавливает исходный список, добавляя вперед через список (предполагает неявный 0 в качестве первого элемента)
  2. Сортирует оригинальный список
  3. Получает различия, возвращаясь назад (поэтому мне не нужно отслеживать другой список) (неявный первый элемент 0 означает, что первое различие совпадает с наименьшим элементом)

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

Брайан Дж
источник
Не могли бы вы обновить ссылку TIO?
Тейлор Скотт
@TaylorScott Обновление каким образом?
Брайан Дж.
Ваша ссылка TIO показывает совершенно другой код, чем в вашем ответе
Тейлор Скотт
1
@ ТейлорСкотт Ааа ... Понятно. Мне пришлось внести некоторые коррективы, потому что TIO использует Mono, но я использовал компилятор .NET 4.5
Брайан J
1

APL (Дьялог) , 15 14 байтов

-1 байт благодаря ngn .

(¯2-/⍋⊃¨⊂)0,+\

+\ накопленная сумма

0, ставить ноль

(… ) Примените к этому следующую молчаливую функцию:

 ⊂ заключить (чтобы мы могли выбрать несколько предметов)

 ⍋⊃¨ пусть каждый из индексов, которые будут сортировать аргумент, выберет из этого

 ¯2-/ обратная попарная разница

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

Оригинальное решение, найденное участниками Code Golf Hackathon на встрече пользователей Dyalog '17 :

¯2-/l[⍋l←+\0,⎕]

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

⎕ запрос на ввод

0, ставить ноль

+\ накопленная сумма

l← хранить как l

⍋ найти индексы, которые будут сортировать l

l[...]  использовать это для индексации вl

¯2-/ обратная попарная разница

оборота Адам
источник
1
Я не знаю, было ли это разрешено на хакатоне, но если вы переписали его в стиле без очков, вы могли бы сохранить символ: (¯2- / ⍋⊃¨⊂) 0, + \
ngn
@ngn Эта часть семинара была направлена ​​на то, чтобы участники начали с PPCG, поэтому здесь были правила PPCG. Спасибо.
Адам
0

Рёда , 42 байта

{i=0{[0];[i]if i+=_}|sort|slide 2|[_2-_1]}

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

Это похоже на ответ Perl 6 . .sortесть |sort, .rotor(2=>-1).flatесть |slide 2 и .map(*R-*)есть|[_2-_1] .

Объяснение:

{
  i=0 /* initialize variable i */
  /* the following block recreates the original list from differences: */
  {
    [0];       /* push 0 to the stream */
    [i]if i+=_ /* add every number in the stream to i and push i back */
  }|
  sort|    /* sort the numbers */
  slide 2| /* for values i1, i2, i3, ... in the stream
              push pairs i1, i2, i2, i3, ... */
  [_2-_1]  /* calculate difference of numbers in each pair in the stream */
}

Утверждение [i]if i+=_эквивалентно

for sfv do
  if i += sfv do
    push(i)
  done
done

+=Оператор не нажмет значение потока, поэтому truthy. Я также мог бы использовать какой-то блок (например {|j|i+=j;[i]}_), чтобы связать операторы сложения и сжатия, но ifон короче.

fergusq
источник
0

Юлия 0.6.0 (34 байта)

Практически копия того, что было сделано в R и Python 3

x->diff(sort(cumsum(vcat([0],x))))

Goysa
источник
0

J, 10 байт

/:~&.(+/\)

объяснение

«сортировать по сумме сканирования»: в J соединение Under &.применяет преобразование справа от входа, затем применяет глагол слева (в данном случае сортировка/:~ ), а затем выполняет обратное преобразование. То есть J понимает, как инвертировать сумму сканирования, что именно здесь и необходимо: последовательные различия - это входные данные, которые при суммировании сканирования будут производить эту сумму сканирования.

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

Ион
источник