Imitar uma encomenda

24

Dadas duas listas de números, uma fonte e um padrão , reordene a fonte para corresponder à ordem relativa do padrão. Quaisquer duas entradas da fonte reordenada devem comparar da mesma maneira que as entradas nessas mesmas posições do padrão.

Por exemplo, a entrada

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

deve produzir o resultado

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

Comparando a primeira e a última posição, o resultado tem 11<13, que corresponde 7<12ao padrão.

Entrada: Duas listas de números inteiros não vazios de comprimento igual. Cada lista não terá repetições. Cabe a você decidir se a fonte ou o padrão é fornecido primeiro.

Saída: uma lista que reorganiza os números de origem para ter a mesma ordem relativa que os números de padrão.

Entre os melhores:

Mostrar snippet de código

code-golf sorting permutations xnor
fonte
Deve ser uma função / programa ou uma expressão / fragmento é suficiente?
Adám 02/11/2015
@NBZ A menos que o desafio o substitua, o padrão é que apenas funções e programas sejam permitidos . Funções sem nome são permitidas .
Martin Ender

Respostas:

10

CJam, 12 10 bytes

{_$f#\$f=}

Esta é uma função anônima, que assume s pa pilha e deixa o resultado na pilha. Demonstração online

Com agradecimentos a Martin Büttner por 2 bytes.

Dissecação

{         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
}
Peter Taylor
fonte
{_$@$er}é dois bytes mais curto.
Dennis
@ Dennis, isso é o suficiente diferente para ser uma resposta em separado
Peter Taylor
Se você acha, vou postá-lo como resposta.
Dennis
10

J, 9 bytes

/:^:2~/:~

Este é um verbo diádico que leva p e s como argumentos à esquerda e à direita. Experimente online com J.js .

Execução de teste

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

Como isso funciona

Digamos que definimos as entradas esquerda e direita atribuídas do exemplo via

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

Então:

  • O trem /:^:2~/:~é um gancho dos verbos /:^:2~e /:~, assim, chamando

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

    executa

    p /:^:2~ /:~ s

  • O advérbio ~em /:~é reflexivo , pois /:é usado monadicamente. Assim, chamando

    /:~ s

    executa

    s /: s

  • O advérbio ~in /:^:2~é passivo , uma vez que o verbo /:^:2é usado de forma diádica. Assim, chamando

    p /:^:2~ y

    executa

    y /:^:2 p

  • O advérbio ^:é poder . Assim, chamando

    y /:^:2 p

    executa

    y /: y /: p

Juntando tudo, chamando

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

executa

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

Como isso funciona

Diádico /:é graduado usando , ou seja, x /:yretorna os elementos de x , classificados de acordo com os valores correspondentes de y.

  • s /: ssimplesmente classifica os elementos de s .

  • (s /: s) /: pclassifica os elementos (classificados) de s de acordo com os valores correspondentes de p .

  • Classificar duas vezes calcula essencialmente os ordinais de seu argumento correto.

    Assim, (s /: s) /: (s /: s) /: pclassifica os elementos (classificados) de s , imitando a ordem dos elementos de p .

Dennis
fonte
9

Mathematica, 32 27 bytes

Sort@#~Permute~Ordering@#2&

Exemplo de uso:

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} *)

Tentativa anterior:

Sort[#][[Ordering@Ordering@#2]]&
2012rcampion
fonte
@DavidCarraher Fixed!
precisa saber é o seguinte
11
+1 Eu descobri essa mesma solução 4 minutos depois de você! Você pode salvar alguns bytes:o = Ordering; (Sort@#)[[o@o@#2]] &
DavidC
Adorável nova solução via Permute! Uso muito útil de permutações.
DavidC
7

J, 17 bytes

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

Isso é avaliado como um verbo diádico (significando binário). Pode ser evocado da seguinte maneira:

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

Explicação

Esta pode não ser a solução J mais curta possível, mas é uma abordagem nova.

                   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.
Zgarb
fonte
6

Pitão, 10 bytes

@LSvzxLSQQ

Experimente online: Demonstração

Explicação

@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
Jakube
fonte
XQSQSvzé três bytes mais curto.
Dennis
@Dennis Dang. Por que não pensei nisso? Deseja publicá-lo?
Jakube 2/11
11
Se você o considera suficientemente diferente da sua abordagem, com certeza.
Dennis
6

Pitão, 7 bytes

XQSQSvz

Este é um programa completo que espera representações de seqüência de s e p em duas linhas.Experimente online.

Como funciona

           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.
Dennis
fonte
5

Python 2, 51

lambda s,p,a=sorted:[a(s)[a(p).index(x)]for x in p]
feersum
fonte
Estou confuso: por que existem três parâmetros?
Peter Taylor
@PeterTaylor O terceiro parâmetro tem um valor padrão, portanto, ele pode ser chamado com apenas 2.
feersum
Adicionar PeterTaylor Adicionar uma linha separada a=sortedteria o mesmo efeito.
Xnor
Aaaaaah! Eu estava enganando, e pensei que o corpo começou no =.
Peter Taylor
5

Mathematica 56 43 30 29 bytes

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

Ordering@#2retorna a ordem dos números no padrão. Ordering@Ordering@#2fornece as posições que os elementos classificados na fonte devem ocupar.

Sort[#][[o@o@#2]]& retorna a fonte nas posições necessárias, ou seja, aquelas que têm a mesma ordem relativa que a lista de padrões.

Teste

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}

DavidC
fonte
5

CJam, 8 bytes

{_$@$er}

Esta é uma função que espera anónimos s e p (nível superior) na pilha e empurra os reordenadas s em retorno. Experimente online no intérprete CJam .

Como funciona

_      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.
Dennis
fonte
4

J, 13 bytes

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

Ainda estou tendo problemas para entender a composição dos verbos de J, então me sinto como alguns deles @e []pode ser desnecessário. Se algum usuário J mais experiente pudesse me informar se isso pode ser compactado, isso seria ótimo. :)

O verbo pode ser usado da seguinte maneira:

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

Explicação

/:@/:@[{/:~@] 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.
Martin Ender
fonte
Você pode usar diádico /:para se livrar de {e a @, por 11 bytes:/:~@]/:/:@[
Dennis
@Dennis Obrigado, o Zgarb encontrou outra solução de 11 bytes, entretanto, que precisa apenas de dois /:, mas ainda não tive a oportunidade de atualizar a resposta ( ({~/:)&/:{[).
Martin Ender
4

APL, 17 12 bytes

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

Graças a @Dennis, isso agora é muito elegante.

Aqui está uma boa solução de 14 bytes que não usa a indexação dupla:

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

Infelizmente, não podemos indexar matrizes nos trens da APL.

lirtosiast
fonte
4

Python 2, 48

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

Um grande globo de funções. Isso usa a abordagem de conversão de elementos de muitas outras respostas usando um dicionário.

A entrada com estrela *lespera os padrões e a origem nessa ordem e os transforma em uma lista l.

O mapeamento sortedclassifica as duas listas e dict(zip(_))transforma um par de listas em um dicionário com chaves da primeira lista correspondentes aos valores da segunda, em ordem crescente. Portanto, o resultado é que o idécimo maior elemento do padrão é correspondido ao idécimo maior elemento da fonte.

Finalmente, transformamos o pattern ( l[0]) através deste dicionário, mapeando seu .getmétodo.

xnor
fonte
3

Bash + coreutils, 55

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

A entrada é tomada como dois nomes de arquivos, para a origem e o padrão, respectivamente:

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

R, 38 bytes

function(s,p)sort(s)[match(p,sort(p))]
flodel
fonte
Essa é uma boa abordagem. Não teria pensado em usar match.
Alex A.
3

Ruby, 51 bytes

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

Haskell, 65 bytes

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

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

Como funciona:

           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
nimi
fonte
2

R, 37 bytes

function(s,p,o=order)s[o(s)][o(o(p))]
aPaulT
fonte
2

TeaScript, 15 bytes

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

Isso recebe a entrada como uma matriz. O intérprete está fora do ar porque eu estou colocando o novo intérprete chique

Explicação

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
  ]
)
Downgoat
fonte
Ou eu estou mal entendendo a explicação, ou isso não funciona ... Eu a codifiquei no Pip de acordo com o que acho que funciona, e peguei 13 9 -6 4 11 -5 0a amostra de entrada. ??
DLosc
2

Geleia , 6 bytes, desafio de pós-datas de idiomas

Œ¿œ?Ṣ}

Experimente online!

Isso leva o padrão, seguido pela fonte, como dois argumentos separados.

Explicação

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

fonte
1

Haskell, 56 bytes

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

Define uma função binária %. Cada entrada pé transformada na entrada scom a mesma estatística de ordem, ou seja, classificação relativa em sua lista. A estatística de ordem de xin pé encontrada contando os elementos menores que ele ( sort p!!xproduz um irritante Maybe). O resultado é indexado emsort s .

Uma zip/lookupsolução tem o mesmo comprimento, exceto que fornece Justnúmeros.

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