Imitate an ordering

Question

Given two lists of numbers, a source and a pattern, reorder the source to match the relative ordering of the pattern. Any two entries of the reordered source should compare the same way as the entries at those same positions of the pattern.

For example, the input

s = [-5, 9, 4, 13, 11, -6, 0]
p = [7, -4, 1, -8, 4, -3, 12]

should produce the result

    [11, -5, 4, -6, 9, 0, 13]

Comparing the first and last positions, the result has 11<13, which matches 7<12 in the pattern.

Input: Two equal-length non-empty lists of integers. Each list will have no repeats. It's up to you whether the source or pattern is given first.

Output: A list that rearranges the source numbers to have the same relative ordering as the pattern numbers.

Leaderboard:

var QUESTION_ID=62587,OVERRIDE_USER=20260;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/62587/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;

body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

Answer 1

CJam, 12 10 bytes

{_$f#\$f=}

This is an anonymous function, which takes s p on the stack and leaves the result on the stack. Online demo

With thanks to Martin Büttner for 2 bytes.

Dissection

{         e# Define an anonymous function
  _$f#    e# Use a copy of the pattern to map each element to its sort index
  \$      e# Sort the source
  f=      e# Map each sort index to the corresponding source element
}

Answer 2

J, 9 bytes

/:^:2~/:~

This is a dyadic verb that takes p and s as left and right arguments. Try it online with J.js.

Test run

   7 _4 1 _8 4 _3 12 (/:^:2~/:~) _5 9 4 13 11 _6 0
11 _5 4 _6 9 0 13

How this works

Say we defined assigned the left and right input from the example via

p =: 7 _4 1 _8 4 _3 12
s =: _5 9 4 13 11 _6 0

Then:

• The train /:^:2~/:~ is a hook of the verbs /:^:2~ and /:~, so calling

  p (/:^:2~/:~) s
  

  executes

  p /:^:2~ /:~ s
  

• The adverb ~ in /:~ is reflexive, since /: is used monadically. Thus, calling

  /:~ s
  

  executes

  s /: s
  

• The adverb ~ in /:^:2~ is passive, since the verb /:^:2 is used dyadically. Thus, calling

  p /:^:2~ y
  

  executes

  y /:^:2 p
  

• The adverb ^: is power. Thus, calling

  y /:^:2 p
  

  executes

  y /: y /: p
  

Putting it all together, calling

p (/:^:2~/:~) s

executes

(s /: s) /: (s /: s) /: p

How that works

Dyadic /: is grade up using, i.e., x /:y returns the elements of x, sorted according to the corresponding values of y.

• s /: s simply sorts the elements of s.

• (s /: s) /: p sorts the (sorted) elements of s according to the corresponding values of p.

• Grading up twice essentially computes the ordinals of its right argument.

  Thus, (s /: s) /: (s /: s) /: p sorts the (sorted) elements of s, imitating the order of the elements of p.

Answer 3

Mathematica, 32 27 bytes

Sort@#~Permute~Ordering@#2&

Example usage:

Sort@#~Permute~Ordering@#2 &[{-5, 9, 4, 13, 11, -6, 0}, {7, -4, 1, -8, 4, -3, 12}]
(* {11, -5, 4, -6, 9, 0, 13} *)

Previous attempt:

Sort[#][[Ordering@Ordering@#2]]&

Answer 4

J, 17 bytes

(A.^:_1/:~)~A.@/:

This evaluates to a dyadic (meaning binary) verb. It can be evoked as follows:

  _5 9 4 13 11 _6 0 ((A.^:_1/:~)~A.@/:) 7 _4 1 _8 4 _3 12
11 _5 4 _6 9 0 13

Explanation

This may not be the shortest possible J solution, but it's a novel approach.

                   Left input is x, right input is y.
            A.@/:  The index of the permutation P that sorts y. /: gives the
                   permutation itself, and A. gives its index in the sorted
                   list of all its permutations.
       /:~         x sorted in ascending order. We are applying the x-sorting
                   permutation to x itself.
(A.^:_1   )~       The inverse of the permutation P applied to the sorted
                   version of x. Since P maps y to its sorted version, its
                   inverse maps the sorted version to y, and thus sorted x to
                   the correct output.

Answer 5

Pyth, 10 bytes

@LSvzxLSQQ

Try it online: Demonstration

Explanation

@LSvzxLSQQ implicit: z = first input line as string
                     Q = second input line evaluated
       SQ  sorted(Q)
     xLSQQ find the index for each element of Q in sorted(Q)
  Svz      sorted(evaluated z)
@LSvz      take the element in ^ for each index

Answer 6

Pyth, 7 bytes

XQSQSvz

This is a full program that expects string representations of s and p on two lines. Try it online.

How it works

           Store the first line of input (rep. of s) in z.
           Evaluate the second line of input and store the result (p) in Q.
  SQ       Sort the elements of p.
    Svz    Evaluate the repr. of s and sort its elements.
XQ         Perform transliteration on p.
           This replaces the lowest element of p with the lowest element of s, etc.

Answer 7

Python 2, 51

lambda s,p,a=sorted:[a(s)[a(p).index(x)]for x in p]

Answer 8

Mathematica 56 43 30 29 bytes

o=Ordering;Sort[#][[o@o@#2]]&

Ordering@#2 returns the order of numbers in the pattern. Ordering@Ordering@#2 gives the positions that the sorted elements in the source should occupy.

Sort[#][[o@o@#2]]& returns the source in the required positions, namely, those that have the same relative ordering as the pattern list.

Testing

o=Ordering;Sort[#][[o@o@#2]]&[{-5, 9, 4, 13, 11, -6, 0}, {7, -4, 1, -8, 4, -3, 12}]

{11, -5, 4, -6, 9, 0, 13}

Answer 9

CJam, 8 bytes

{_$@$er}

This is an anonymous functions that expects s and p (topmost) on the stack and pushes the reordered s in return. Try it online in the CJam interpreter.

How it works

_      e# Push a copy of p.
 $     e# Sort it.
  @    e# Rotate s on top of p and the sorted p.
   $   e# Sort s.
    er e# Perform transliteration.
       e# This replaces the lowest element of p with the lowest element of s, etc.

Answer 10

J, 13 bytes

/:@/:@[{/:~@]

I'm still having trouble wrapping my head around J's verb composition, so I feel like some of those @ and [] might be unnecessary. If some more experienced J user could let me know if this can be compressed, that would be great. :)

The verb can be used as follows:

   7 _4 1 _8 4 _3 12 (/:@/:@[{/:~@]) _5 9 4 13 11 _6 0
11 _5 4 _6 9 0 13

Explanation

/:@/:@[{/:~@] NB. Left input is the pattern, right input is the source.
        /:~@] NB. Sort the source.
/:@/:@[       NB. Compute the ordering of the ordering of the pattern.
       {      NB. Use those as indices into the sorted source.

Answer 11

Python 2, 48

lambda*l:map(dict(zip(*map(sorted,l))).get,l[0])

A big glob of functions. This uses the element translation approach of many other answers using a dictionary.

The starred input *l expects the patterns and source in that order, and turns them into a list l.

Mapping sorted sorts both lists, and dict(zip(_)) turns a pair of lists into a dictionary with keys from the first list matched with values in the second, in ascending order. So, the result is that that i-th largest element of the pattern is matched with the i-th largest element of the source.

Finally, we transform the pattern (l[0]) via this dictionary by mapping its .get method.

Answer 12

Bash + coreutils, 55

nl $2|sort -nk2|paste <(sort -n $1) -|sort -nk2|cut -f1

Input is taken as two filenames, for the source and pattern respectively:

$ ./imitord.sh source.txt pattern.txt 
11  
-5  
4   
-6  
9   
0   
13  
$ 

Answer 13

R, 38 bytes

function(s,p)sort(s)[match(p,sort(p))]

Answer 14

Ruby, 51 bytes

->s,p{s.map{|x|s.sort[p.sort.index(p[s.index x])]}}

Answer 15

APL, 17 12 bytes

{⍺[⍋⍺][⍋⍋⍵]}

Thanks to @Dennis, this is now very elegant.

Here's a nice 14-byte solution that doesn't use double indexing:

{⍺[(⍋⍋⍺)⍳⍋⍋⍵]}

Unfortunately, we can't index arrays from within trains in APL.

Answer 16

Haskell, 65 bytes

import Data.List
s#p=[sort s!!i|b<-p,(i,e)<-zip[0..]$sort p,b==e]

Usage example: [-5,9,4,13,11,-6,0] # [7,-4,1,-8,4,-3,12] -> [11,-5,4,-6,9,0,13].

How it works:

           b<-p                              -- for every b in p
               ,(i,e)<-zip[0..]$sort p       -- walk through the sorted list of p 
                                             -- paired with it's index ->
                                             -- (index,element) or (i,e)
                                      ,b==e  -- for those cases where b equals e
 sort s!!i                                   -- take the i-th element from the
                                             -- sorted list s

Answer 17

R, 37 bytes

function(s,p,o=order)s[o(s)][o(o(p))]

Answer 18

TeaScript, 15 bytes

ys¡m™x[yi(l)])

This takes input as an array. The interpreter is currently down because I'm putting up the fancy new interpreter

Explanation

y      // Second input
 s¡    // Sort it = s()
m™     // Map over it = m(#
  x[      // Num in first input at index...
    yi(l) // Current char's index in y
  ]
)

Answer 19

Jelly, 6 bytes, language postdates challenge

Œ¿œ?Ṣ}

Try it online!

This takes the pattern, followed by the source, as two separate arguments.

Explanation

Œ¿œ?Ṣ}
Œ¿      Generate an integer that describes the order of {the first input}
  œ?    Use that integer to reorder
    Ṣ}  the sorted version of the second {input}

Answer 20

Haskell, 56 bytes

import Data.List
p%s=[sort s!!(length$filter(<x)p)|x<-p]

Defines a binary function %. Each entry in p is transformed to the entry of s with the same order statistic, i.e. relative rank in its list. The order statistic of x in p is found by counting the elements smaller than it (sort p!!x produces an annoying Maybe). The result is indexed into sort s.

A zip/lookup solution is the same length, except it gives Just numbers.

import Data.List
p%s=[lookup x$zip(sort p)(sort s)|x<-p]