24
\$\begingroup\$

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>

\$\endgroup\$

20 Answers 20

10
\$\begingroup\$

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
}
\$\endgroup\$
  • \$\begingroup\$ {_$@$er} is two bytes shorter. \$\endgroup\$ – Dennis Nov 2 '15 at 18:54
  • \$\begingroup\$ @Dennis, that's different enough to be a separate answer \$\endgroup\$ – Peter Taylor Nov 2 '15 at 19:04
  • \$\begingroup\$ If you think so, I'll post it as an answer. \$\endgroup\$ – Dennis Nov 2 '15 at 20:20
10
\$\begingroup\$

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.

\$\endgroup\$
9
\$\begingroup\$

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]]&
\$\endgroup\$
  • \$\begingroup\$ @DavidCarraher Fixed! \$\endgroup\$ – 2012rcampion Nov 1 '15 at 22:29
  • 1
    \$\begingroup\$ +1 I discovered this very same solution 4 minutes after you! You can save a couple of bytes: o = Ordering; (Sort@#)[[o@o@#2]] & \$\endgroup\$ – DavidC Nov 1 '15 at 22:35
  • \$\begingroup\$ Lovely new solution via Permute! Very useful use of permutations. \$\endgroup\$ – DavidC Nov 1 '15 at 22:36
7
\$\begingroup\$

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

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
\$\endgroup\$
  • \$\begingroup\$ XQSQSvz is three bytes shorter. \$\endgroup\$ – Dennis Nov 2 '15 at 18:51
  • \$\begingroup\$ @Dennis Dang. Why didn't I thougth of this? Do you want to post it? \$\endgroup\$ – Jakube Nov 2 '15 at 19:23
  • 1
    \$\begingroup\$ If you consider it sufficiently different from your approach, sure. \$\endgroup\$ – Dennis Nov 2 '15 at 20:19
6
\$\begingroup\$

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

Python 2, 51

lambda s,p,a=sorted:[a(s)[a(p).index(x)]for x in p]
\$\endgroup\$
  • \$\begingroup\$ I'm confused: why are there three parameters? \$\endgroup\$ – Peter Taylor Nov 1 '15 at 21:49
  • \$\begingroup\$ @PeterTaylor The third parameter has a default value, so it can be called with only 2. \$\endgroup\$ – feersum Nov 1 '15 at 21:50
  • \$\begingroup\$ @PeterTaylor Adding a separate line a=sorted would have the same effect. \$\endgroup\$ – xnor Nov 1 '15 at 21:52
  • \$\begingroup\$ Aaaaaah! I was misparsing, and thought that the body began at the =. \$\endgroup\$ – Peter Taylor Nov 1 '15 at 21:53
5
\$\begingroup\$

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}

\$\endgroup\$
5
\$\begingroup\$

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

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.
\$\endgroup\$
  • \$\begingroup\$ You can use dyadic /: to get rid of { and a @, for 11 bytes: /:~@]/:/:@[ \$\endgroup\$ – Dennis Nov 2 '15 at 15:29
  • \$\begingroup\$ @Dennis Thanks, Zgarb has found another 11-byte solution in the meantime which only needs two /:, but I haven't got round to updating the answer yet (({~/:)&/:{[). \$\endgroup\$ – Martin Ender Nov 2 '15 at 15:36
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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

R, 38 bytes

function(s,p)sort(s)[match(p,sort(p))]
\$\endgroup\$
  • \$\begingroup\$ This is a nice approach. Wouldn't have thought to use match. \$\endgroup\$ – Alex A. Nov 1 '15 at 22:54
3
\$\begingroup\$

Ruby, 51 bytes

->s,p{s.map{|x|s.sort[p.sort.index(p[s.index x])]}}
\$\endgroup\$
2
\$\begingroup\$

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

R, 37 bytes

function(s,p,o=order)s[o(s)][o(o(p))]
\$\endgroup\$
2
\$\begingroup\$

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
  ]
)
\$\endgroup\$
  • \$\begingroup\$ Either I'm badly misunderstanding the explanation, or this doesn't work... I coded it up in Pip according to what I think it does, and got 13 9 -6 4 11 -5 0 for the sample input. ?? \$\endgroup\$ – DLosc Nov 4 '15 at 7:24
2
\$\begingroup\$

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

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]
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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