Перестановки в маскировке

17

Учитывая n - мерный вектор v с вещественными элементами, найти ближайший перестановку p из (1,2,...,n) относительно l1 -Расстояние.

Детали

  • Если это более удобно, можно использовать перестановки (0,1,...,n1) вместо этого. Если имеется несколько ближайших перестановок, вы можете вывести любую или поочередно все из них.
  • Расстояние l1 между двумя векторами u,v определяется как
    d(u,v)=i|uivi|.
  • Если вы хотите, вы можете предположить, что входные данные состоят исключительно из целых чисел.

Примеры

[0.5  1] -> [1 2], [2 1]
c*[1 1 ... 1] -> any permutation
[1 4 2 6 2] -> [1 4 3 5 2], [1 4 2 5 3]
[1 3 5 4 1] -> [2 3 5 4 1], [1 3 5 4 2]
[7 7 3 2 5 6 4 2] -> [8 7 3 2 5 6 4 1], [8 7 3 1 5 6 4 2], [7 8 3 2 5 6 4 1], [7 8 3 1 5 6 4 2]
[-2 4 5 7 -1 9 3] -> [1 4 5 6 2 7 3], [2 4 5 6 1 7 3], [1 4 5 7 2 6 3], [2 4 5 7 1 6 3]
[0 4 2 10 -1 10 5] -> [1 4 2 6 3 7 5], [1 4 3 6 2 7 5], [2 4 3 6 1 7 5], [3 4 2 6 1 7 5], [1 4 2 7 3 6 5], [1 4 3 7 2 6 5], [2 4 3 7 1 6 5], [3 4 2 7 1 6 5]

Octave скрипт для генерации большего количества примеров.

flawr
источник
Гарантируем ли мы, что все элементы v, будут больше, чем 0? Или, по крайней мере, нет 0?
Лохматый
1
Нет, записи vмогут быть любыми целыми числами. (Добавил еще несколько примеров.)
flawr
Если они могут быть любыми действительными числами, то [1.6 2]это важный тестовый пример (жадный алгоритм / лексикографическая сортировка дает неправильный ответ).
гистократ
2
Дублированный замаскированный? Я не уверен, что он должен быть закрыт как таковой, потому что не очевидно, что это та же самая задача (как теперь доказано xnor).
Арно
1
(На самом деле, это не та же самая задача, но все решения связанной задачи являются решениями этой проблемы.)
Арно

Ответы:

13

Python 2 , 60 байт

def f(l):z=zip(l,range(len(l)));print map(sorted(z).index,z)

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

Использует нулевую индексацию.

Быстрый алгоритм с простой идеей. Если вместо этого мы должны переставить список ввода , чтобы сделать его как можно ближе к (1,2,,,,,N) , насколько это возможно, мы должны просто разбирайтесь, как доказано ниже. Поскольку мы вместо перестановки (1,2,,,,,N) , мы выбираем перестановку , что заказали точно так же , как список ввода, как в моем вызове Подражать упорядоченность ( за исключением ввода может быть повторы). (Изменить: мили указали на этот более идентичный вызов , где Деннис имеет тот же ответ .)

Утверждение: Перестановка из списка L , что сводит к минимуму ее расстояние до (1,2,...,n) является l отсортирован.

Доказательство: рассмотрим некоторую другую перестановку l из l . Мы докажем , что не может быть лучше , чем l отсортирован.

Выберите два индекса i,j , у которых l не в порядке, то есть где i<J но li>lJ' . Показано , что замена их не может увеличить расстояние до (1,2,,,,,N) . Отметим, что своп изменяет вклад этих двух элементов следующим образом:

|Lя'-я|+|LJ'-J||Lя'-J|+|LJ'-я|,

Вот отличный способ показать, что это не может быть увеличение. Рассмотрим двух людей, идущих по числовой линии: один идет от Lя' до я а другой от LJ' до J . Общее расстояние, которое они проходят, - это выражение слева. Поскольку я<J но Lя'>LJ' , они переключают, кто выше на числовой линии, что означает, что они должны пересекаться в какой-то момент во время своих прогулок, назовите это п . Но когда они достигают пзатем они могли поменяться местами назначения и пройти одинаковое общее расстояние. И потом, для них не может быть хуже, если бы они с самого начала шли к местам, где они поменялись местами, вместо того, чтобы использовать п в качестве точки пути, что дает общее расстояние с правой стороны.

Так, сортировка два вне потока порядка элементов в L' делает ее расстояние до (1,2,,,,,N) меньше или же. Повторение этого процесса в конечном итоге отсортирует L . Таким образом, сортировка L по крайней мере, так же хороша, как L' для любого выбора L' , что означает, что она является оптимальной или связана для оптимальной.

Note that the only property of (1,2,,,,,N) that we used is that it's sorted, so the same algorithm would work to permute any given list to minimize its distance to any fixed list.

In the code, the only purpose of z=zip(l,range(len(l))) is to make the input elements distinct, that is to avoid ties, while keeping the same comparisons between unequal elements. If the input we guaranteed to have no repeats, we could remove this and just have lambda l:map(sorted(l).index,l).

xnor
источник
brilliant insight
Jonah
You've simplified this into finding the ordering.
miles
@miles Это довольно забавно, я совершенно забыл об этом вызове, хотя написал ответ, и у Денниса есть именно тот ответ на Python, который я помог гольфу.
xnor
That "visual proof" is neat. I got the same idea but had to lay out each case of that formula to prove it. As a side remark, a few alternatives of obtaining ranks in Python using third-party libraries are shown in this post.
Joel
5

05AB1E , 7 байтов

āœΣαO}н

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


объяснение

ā              # get the numbers 1 to len(input) + 1
 œ             # Permutations of this
  Σ  }         # Sort by ...
   α           # Absolute difference
    O          # Sum these
      н        # And get the first one 
               # implicitly print
Истекшие данные
источник
1
Everytime i'm amazed by this, what 05AB1E can't do ?
Случайный парень
5
@Therandomguy В 05AB1E не так много вещей, которые нельзя сделать, но они довольно плохо справляются с задачами на основе регулярных выражений; матричные задачи (хотя это было улучшено после некоторых новых встроенных функций); отсутствие мнимых чисел; проблемы, связанные с датой / временем; и т. д. Однако, хотя это и сложно, это все же можно сделать обычно. Приведем два примера: обратный отсчет рабочего дня (переход к следующему дню и получение дня недели выполняются вручную); Quine выводит себя в двоичном виде (преобразование UTF-8 выполняется вручную).
Кевин Круйссен
@Grimy должен быть исправлен сейчас :)
действия данных
3

Perl 6 , 44 байта

{permutations(+$_).min((*[]Z-$_)>>.abs.sum)}

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

Анонимный кодовый блок, который возвращает первую минимальную перестановку с индексированием 0.

Объяснение:

{                                          }   # Anonymous code block
 permutations(+$_)                             # From the permutations with the same length
                  .min(                   )    # Find the minimum by
                                      .sum       # The sum of
                                >>.abs           # The absolute values of
                       (*[]Z-$_)                 # The zip subtraction with the input

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

Джо Кинг
источник
1
Это тоже сломало мне мозг (или, в основном, эквивалентный вопрос «работает ли для этого жадный алгоритм?»). Простейший контрпример - это [0.6 1](при условии, что мы проиндексированы 0), где, если вы оптимизируете первое значение, полученное [1,0]для оценки 1,4, но если вы оптимизируете для всего вектора, 1 более ценно во второй позиции для оценки 0,6.
гистократ
2

Желе , 5 байт

Œ¿œ?J

Монадическая ссылка, принимающая список чисел, который выдает список целых чисел.

Попробуйте онлайн! Или посмотрите набор тестов .

Как?

Œ¿œ?J - Link: list of numbers, X
Œ¿    - Index of X in a lexicographically sorted list of
         all permutations of X's items
    J - range of length of X
  œ?  - Permutation at the index given on the left of the
         items given on the right

NB L(длина) будет работать вместо того, чтобы Jс тех пор, как œ?дано целое число n, справа будет неявно сделать диапазон [1..n]для работы, но Jявно.

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

Рубин , 63 60 байт

->v{[*1..v.size].permutation.max_by{|p|eval [p,0]*'*%p+'%v}}

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

Здесь есть математический трюк, который может быть полезен и в других ответах - вместо того, чтобы минимизировать сумму абсолютных значений разностей, мы максимизируем сумму продуктов. Почему это работает?

Минимизация суммы (x-y) squaredне эквивалентна минимизации суммы|x-y| , но она всегда даст верный ответ, она просто придает приоритет сокращению больших различий по сравнению с маленькими, тогда как реальная задача безразлична между ними.

Но (x-y)*(x-y)= x*x+y*y-2*x*y. Поскольку квадратные члены всегда будут отображаться где-то в сумме для любой перестановки, они не влияют на результат, поэтому мы можем упростить до -2*x*y. В 2сглаживает, поэтому мы можем упростить -x*y. Тогда, если мы изменим минимизацию на максимизацию, мы можем упростить до x*y.

Интуитивно это похоже на наблюдение того, что, если вы пытаетесь максимизировать квадратные метры, используя набор горизонтальных и вертикальных стен, лучше всего объединить стены, близкие по размеру друг к другу, для создания комнат, которые будут как можно ближе к квадрату. 3*3 + 4*4 = 25, пока3*4 + 4*3 = 24 .

Редактировать: Сохранение трех байтов путем генерации и оценки строки формата вместо использования zip и sum.

histocrat
источник
2
Минимизация суммы квадратов (xy) не эквивалентна минимизации суммы | xy |, но всегда даст правильный ответ. Почему это так? Нет лиY что сводит к минимуму Σ|Икс-Y| но нет Σ(Икс-Y)2?
Джоэл
1

Gaia , 13 байт

e:l┅f⟪D†Σ⟫∫ₔ(

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

e:		| eval and dup input
l┅f		| push permutations of [1..length(input)]
⟪   ⟫∫ₔ		| iterate over the permutations, sorting with minimum first
 D†Σ		| the sum of the absolute difference of the paired elements
       (	| and select the first (minimum)
Giuseppe
источник
1

JavaScript (ES6), 61 байт

Основано на проницательности xnor .

a=>[...a].map(g=n=>g[n]=a.sort((a,b)=>a-b).indexOf(n,g[n])+1)

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

комментарии

a =>                    // a[] = input array
  [...a]                // create a copy of a[] (unsorted)
  .map(g = n =>         // let g be in a object; for each value n in the copy of a[]:
    g[n] =              //   update g[n]:
      a.sort(           //     sort a[] ...
        (a, b) => a - b //       ... in ascending order
      ).indexOf(        //     and find the position
        n,              //       of n in this sorted array,
        g[n]            //       starting at g[n] (interpreted as 0 if undefined)
      ) + 1             //     add 1
  )                     // end of map()

JavaScript (ES6),  130  128 байт

Там  должен быть  , безусловно , является более прямым путем ...

0 индексированные.

a=>(m=g=(k,p=[])=>1/a[k]?(h=i=>i>k||g(k+1,b=[...p],b.splice(i,0,k),h(-~i)))``:p.map((v,i)=>k+=(v-=a[i])*v)|k>m||(R=p,m=k))(0)&&R

Попробуйте онлайн! (с 1-индексированным выходом)

Как?

Вспомогательная функция грамм вычисляет все перестановки (0,,,,,N-1), где N неявная длина входного массива a[],

Для каждой перестановки пмы вычисляем:

Кзнак равноN-1+Σязнак равно0N-1(пя-aя)2
Единственная причина для ведущих N-1 является то, что мы повторно используем внутренний счетчик грамм сохранить несколько байтов, но это не влияет на конечный результат.

В конечном итоге мы возвращаем перестановку, которая приводит к наименьшему К,

Arnauld
источник
1

Python 2 , 149 126 112 байтов

-23 байта благодаря мистеру Xcoder

-14 байт благодаря xnor

from itertools import*
f=lambda a:min(permutations(range(len(a))),key=lambda x:sum(abs(a-b)for a,b in zip(x,a)))

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

Использует перестановки (0 ... n-1).

Hiatsu
источник
Вы можете переключиться на Python 2, так что вам больше не нужен functools.
г-н Xcoder
reduceобычно излишним, особенно здесь, где вы добавляете вещи. Я думаю, что вы можете просто сделать sum(abs(p-q)for p,q in zip(x,a)).
xnor
0

без любого пакета перестановок

Python 3 , 238 байт

def p(a,r,l):
 if r==[]:l+=[a];return
 for i in range(len(r)):
  p(a+[r[i]],r[:i]+r[i+1:],l)
def m(l):
 s=(float("inf"),0);q=[];p([],list(range(len(l))),q)
 for t in q:D=sum(abs(e-f)for e,f in zip(l,t));s=(D,t)if D<s[0]else s
 return s[1]

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

Дэвид
источник
0

Japt -g , 12 байт

Êõ á ñÈíaU x

Попытайся

For 0-indexed, replace the first 2 bytes with m, to map the array to its indices instead.

Êõ á ñÈíaU x     :Implicit input of array U
Ê                :Length
 õ               :Range [0,Ê]
   á             :Permutations
     ñÈ          :Sort by
       í U       :  Interleave with U
        a        :  Reduce each pair by absolute difference
           x     :  Reduce resulting array by addition
                 :Implicit output of first sub-array
мохнатый
источник