18
\$\begingroup\$

Given a \$n\$-dimensional vector \$v\$ with real entries, find a closest permutation \$p\$ of \$(1,2,...,n)\$ with respect to the \$l_1\$-distance.

Details

  • If it is more convenient, you can use permutations of \$(0,1,...,n-1)\$ instead. If there are multiple closest permutations, you can output any one or alternatively all of them.
  • The \$l_1\$ distance between two vectors \$u,v\$ is defined as $$d(u,v) = \sum_i \vert u_i-v_i\vert.$$
  • If you want, you can assume that the input solely consists of integers.

Examples

[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 script for generating more examples.

\$\endgroup\$
6
  • \$\begingroup\$ Are we guaranteed that all the elements of v, will be greater than 0? Or, at least, not 0? \$\endgroup\$
    – Shaggy
    Sep 13, 2019 at 13:36
  • 1
    \$\begingroup\$ No, the entries of v can be any integers. (Added some more examples.) \$\endgroup\$
    – flawr
    Sep 13, 2019 at 13:43
  • \$\begingroup\$ If they can be any real numbers then [1.6 2] is an important test case (greedy algorithm/lexicographic sort gives the wrong answer). \$\endgroup\$
    – histocrat
    Sep 13, 2019 at 16:08
  • 2
    \$\begingroup\$ Duplicate in disguise? I'm not sure it should be closed as such, though, because it's not obvious that it is the same task (as now proved by xnor). \$\endgroup\$
    – Arnauld
    Sep 14, 2019 at 8:52
  • 1
    \$\begingroup\$ (In fact, it's not the same task, but all solutions of the linked challenge are solutions of this one.) \$\endgroup\$
    – Arnauld
    Sep 14, 2019 at 11:08

14 Answers 14

14
\$\begingroup\$

Python 2, 60 bytes

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

Try it online!

Uses zero-indexing.

A fast algorithm with a simple idea. If we instead need to permute the input list to make it as close to \$(1,2,...,n)\$ as possible, we should just sort it, as proven below. Since we're instead permuting \$(1,2,...,n)\$, we choose the permutation that's ordered the same way as the input list, like in my challenge Imitate an ordering (except the input may have repeats). (Edit: miles pointed out this more identical challenge, where Dennis has this same answer.)

Claim: A permutation of the list \$l\$ that minimizes its distance to \$(1,2,...,n)\$ is \$l\$ sorted.

Proof: Consider some other permutation \$l'\$ of \$l\$. We'll prove it can't be better than \$l\$ sorted.

Pick two indices \$i,j\$ that \$l'\$ has out-of-order, that is where \$i<j\$ but \$l'_i > l'_j\$. We show that swapping them can't increase the distance to \$(1,2,...,n)\$. We note that swap changes the contribution these two elements as follows: $$ |l'_i - i | + |l'_j - j | \to |l'_i - j | + |l'_j - i|.$$

Here's a neat way to show this can't be an increase. Consider two people walking on a number line, one going from \$l'_i\$ to \$i\$ and the other from \$l'_j\$ to \$j\$. The total distance they walk is the expression on the left. Since \$i<j\$ but \$l'_i > l'_j\$, they switch who is higher on the number line, which means they must cross at some point during their walks, call it \$p\$. But when they reach \$p\$, they could then swap their destinations and walk the same total distance. And then, it can't be worse for them to have walked to their swapped destinations from the start rather than using \$p\$ as a waypoint, which gives the total distance on the right-hand side.

So, sorting two out-of-order elements in \$l'\$ makes its distance to \$(1,2,...,n)\$ smaller or the same. Repeating this process will sort \$l\$ eventually. So, \$l\$ sorted is at least as good as \$l'\$ for any choice of \$l'\$, which means it as optimal or tied for optimal.

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).

\$\endgroup\$
4
  • \$\begingroup\$ brilliant insight \$\endgroup\$
    – Jonah
    Sep 14, 2019 at 5:20
  • \$\begingroup\$ You've simplified this into finding the ordering. \$\endgroup\$
    – miles
    Sep 14, 2019 at 6:54
  • \$\begingroup\$ @miles That's pretty funny, I completely forgot about that challenge even though I wrote an answer, and Dennis has this exact Python answer which I helped golf. \$\endgroup\$
    – xnor
    Sep 14, 2019 at 8:57
  • \$\begingroup\$ 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. \$\endgroup\$
    – Joel
    Sep 14, 2019 at 14:38
5
\$\begingroup\$

05AB1E, 7 bytes

āœΣαO}н

Try it online!


Explanation

ā              # 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
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Everytime i'm amazed by this, what 05AB1E can't do ? \$\endgroup\$ Sep 13, 2019 at 13:26
  • 5
    \$\begingroup\$ @Therandomguy There aren't a lot of things which cannot be done in 05AB1E, but it's pretty bad at: regex-based challenges; matrix-based challenges (although this has been improved after some new builtins); lack of imaginary numbers; date/time related challenges; etc. However, although hard, it can still be done usually. To give two examples: The Work Day Countdown (go to next day, and get day of week are done manually); Quine outputs itself in binary (UTF-8 conversion is done manually). \$\endgroup\$ Sep 13, 2019 at 14:09
  • \$\begingroup\$ @Grimy should be fixed now :) \$\endgroup\$ Sep 13, 2019 at 19:50
3
\$\begingroup\$

Perl 6, 44 bytes

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

Try it online!

Anonymous codeblock that returns the first minimum permutation with 0 indexing.

Explanation:

{                                          }   # 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

I think I might also be able to get rid of the .sum and sort by just the list of absolute values, but I'm not sure this is actually corret, though it passes my current test cases.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ That was breaking my brain too (or the mostly-equivalent question of "does a greedy algorithm work for this?"). The simplest counterexample is [0.6 1] (assuming we're 0-indexed), where if you optimize for the first value you get [1,0] for a score of 1.4, but if you optimize for the whole vector the 1 is more valuable in the second position for a score of 0.6. \$\endgroup\$
    – histocrat
    Sep 13, 2019 at 16:06
2
\$\begingroup\$

Jelly, 8 bytes

LŒ!ạS¥ÐṂ

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Jelly, 5 bytes

Œ¿œ?J

A monadic Link accepting a list of numbers which yields a list of integers.

Try it online! Or see the test-suite.

How?

Œ¿œ?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

N.B. L (length of) would work in place of J since œ? given an integer, n, on the right would implicitly make the range [1..n] to work with, but J is explicit.

\$\endgroup\$
2
\$\begingroup\$

Ruby, 63 60 bytes

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

Try it online!

There's a math trick here that could be helpful in other answers too--instead of minimizing the sum of the absolute values of the differences, we maximize the sum of the products. Why does that work?

Minimizing the sum of (x-y) squared isn't equivalent to minimizing the sum of |x-y|, but it will always give a valid answer, it just prioritizes reducing large differences over small ones whereas the actual challenge is indifferent between the two.

But (x-y)*(x-y) = x*x+y*y-2*x*y. Since the square terms will always show up somewhere in the sum for any permutation, they don't affect the result, so we can simplify to -2*x*y. The 2 factors out, so we can simplify to -x*y. Then if we change minimizing to maximizing, we can simplify to x*y.

Intuitively, this is similar to observing that if you're trying to maximize square footage using a set of horizontal walls and a set of vertical ones, you're best off pairing walls that are close in size to each other to create rooms that are as close to square as possible. 3*3 + 4*4 = 25, while 3*4 + 4*3 = 24.

Edit: Saved three bytes by generating and evaluating a format string instead of using zip and sum.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Minimizing the sum of (x-y) squared isn't equivalent to minimizing the sum of |x-y|, but it will always give a valid answer. Why is it the case? Is there no \$y\$ that minimizes \$\sum |x-y|\$ but not \$\sum (x-y)^2\$? \$\endgroup\$
    – Joel
    Sep 13, 2019 at 20:36
1
\$\begingroup\$

Gaia, 13 bytes

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

Try it online!

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)
\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6), 61 bytes

Based on xnor's insight.

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

Try it online!

Commented

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 bytes

There  must be  definitely is a more direct way...

0-indexed.

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

Try it online! (with 1-indexed output)

How?

The helper function \$g\$ computes all permutations of \$(0,...,n-1)\$, where \$n\$ is the implicit length of the input array \$a[\;]\$.

For each permutation \$p\$, we compute:

$$k=n-1+\sum_{i=0}^{n-1}(p_i-a_i)^2$$ The only reason for the leading \$n-1\$ is that we re-use the internal counter of \$g\$ to save a few bytes, but it has no impact on the final result.

We eventually return the permutation that leads to the smallest \$k\$.

\$\endgroup\$
1
\$\begingroup\$

Wolfram Language (Mathematica), 14 bytes

#@*#&@Ordering

Try it online!

Based on xnor's insight.

\$\endgroup\$
1
\$\begingroup\$

Python 2, 149 126 112 bytes

-23 bytes thanks to Mr. Xcoder

-14 bytes thanks to 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)))

Try it online!

Uses permutations of (0 ... n-1).

\$\endgroup\$
2
  • \$\begingroup\$ You can switch to Python 2, so that you don't need functools anymore. \$\endgroup\$
    – Mr. Xcoder
    Sep 13, 2019 at 18:43
  • \$\begingroup\$ reduce is usually overkill, especially here where you're adding stuff. I think you can just do sum(abs(p-q)for p,q in zip(x,a)). \$\endgroup\$
    – xnor
    Sep 14, 2019 at 9:03
0
\$\begingroup\$

w/o any permutation package

Python 3, 238 bytes

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]

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Wolfram Language (Mathematica), 57 bytes

f@n_:=MinimalBy[Permutations@Range@Length@n,Tr@Abs[n-#]&]

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Japt -g, 12 bytes

Êõ á ñÈíaU x

Try it

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
\$\endgroup\$
0
\$\begingroup\$

J, 25 8 bytes

#\/:@/:]

Try it online!

Much shorter answer based xnor's brilliant idea.

original answer

J, 25 bytes

(0{]/:1#.|@-"1)i.@!@#A.#\

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.