# Sort a string by a given ordering

Your challenge is to sort a string, but rather than by the normal alphabetical order (abc..xyz), you will be sorting strings by a specified alphabet.

You must write a program or function that takes two inputs: An alphabet A and an string S. Both will only contain lowercase English letters, and both will contain at least one character.

You must move letters in S so that the letter that appears first in A appears first, then whichever letter appears second in A, etc. There may be some letters in S that do not appear in A, these should be left at the end and not moved around relative to each other.

Test cases:

A       S               Result
axd     haxuizzxaxduxha aaaxxxxdhuizzuh
a       xyz             xyz
abc     dcba            abcd
il      nmiuplliu       iillnmupu
asdf    qwerty          qwerty


Fewest bytes wins!

• Can we print/return an array of singleton strings? Can we take one string and one array of singleton strings as input? May 28, 2018 at 3:47
• @Dennis Yes, both are fine representations of strings. May 28, 2018 at 3:56
• Can we take either or both inputs as an array of individual characters? May 28, 2018 at 12:29
• @Shaggy A string is a character array, so yes. May 28, 2018 at 14:45

# Python 3, 50 47 46 44 bytes

-3 bytes thanks to ngn!

-1 byte thanks to mypetlion

lambda a,s:s.sort(key=lambda c:a.find(c)%27)


Try it online!

Takes in a string as the alphabet and a list of chars as the string and sorts the list in place.

The %27 ensures that if the character is not in the alphabet, the index returned puts it after the rest of the alphabet.

• -a[::-1].find(c) -> (a+c).find(c)
– ngn
May 28, 2018 at 0:53
• (a+c).find(c) -> a.find(c)%27 to save 1 byte May 28, 2018 at 17:38

## Haskell, 42 bytes

a#s=[c|c<-a,d<-s,c==d]++[c|c<-s,all(/=c)a]


Try it online!

a#s=                     -- take alphabet a and string s
c<-a             -- for all c in a
d<-s        --   for all d in s
[c|       c==d]             keep c if c equals d
++                    -- append
[c|c<-s        ]     --   all c of s
,all(/=c)a      --   that are not in a


# Perl 6,  55  43 bytes

->\A,\S{[~] S.comb.sort:{%(A.comb.antipairs){$_}//∞}}  Try it ->\A,\S{[~] S.comb.sort:{A.index($_)//∞}}


Try it

## Expanded:

-> \A, \S {
[~]  # reduce using &infix:«~» (shorter than .join)

S.comb.sort: # split into character list and sort by:

{  # bare block lambda with implicit parameter $_ A.index($_ ) # get the position

//  # if it is undefined (not in A)
∞   # return Inf instead (so it comes at end of result)
}
}

• Since there will only be up to 26 different characters in the input, and ∞ is 3 bytes, you can replace it with 27 and it'll still work and save a byte. Nov 6, 2018 at 16:45

# Haskell, 40 34 bytes

-6 bytes huge thanks to Laikoni.

foldr(\c->r(==c)<>r(/=c))
r=filter


Try it online!

The first line is an expression that takes two arguments: S and A.

• Nice! You can even drop f= because anonymous functions are allowed. May 29, 2018 at 12:18
• Furthermore (<>) is now in Prelude, so this can be shortened to foldr(\c->r(==c)<>r(/=c)) for 34 bytes: Try it online! May 29, 2018 at 13:30

# Stax, 6 bytes

{xrINo


Run and debug it

This sorts by a block that does this.

• Reverse the alphabet.
• Get the index of each character in the reversed alphabet. Missing yields -1.
• Negate the index.

# 05AB1E, 4 bytes

Rvy†


Try it online!

Explanation

R     # Reverse the alphabet
vy   # For each letter ...
†  # Push S with the current letter filtered to the front

• Smarter than Σ²sk>. May 31, 2018 at 23:22
• Too bad about R€† working as expected though :). Sometimes that can work as a smaller vy loop. Nice answer man. May 31, 2018 at 23:28

# Python 2, 38 bytes

def f(a,s):s.sort(None,a[::-1].find,1)


a must be a string, s a list of strings of length 1. f sorts s in place.

Try it online!

### Alternate version, string I/O, 48 bytes

lambda a,s:sorted(s,None,a[::-1].find,1)[2::5]


Try it online!

### How it works

s.sort(None,a[::-1],1) is shorthand for s.sort(cmp=None,key=a[::-1],reverse=1).

From the docs:

reverse is a boolean value. If set to True, then the list elements are sorted as if each comparison were reversed.

• TIL sort can take 4 arguments. May 28, 2018 at 4:11
• Only in Python 2. Python 3 deprecated cmp and made key and reverse keyword-only arguments, so its list.sort takes only one positional argument. May 28, 2018 at 4:19

# J, 5 bytes

]/:i.


Dyadic verb, taking the alphabet on its left and the string to be sorted on the right.

i. finds the indeces of string's characters in the alphabet, the alphabet length if not found.

   'axd' i. 'haxuizzxaxduxha'
3 0 1 3 3 3 3 1 0 1 2 3 1 3 0


/: sorts its left agrument according to the order specified in the right one.

] the rigth argument (the string)

  'haxuizzxaxduxha' /: 3 0 1 3 3 3 3 1 0 1 2 3 1 3 0
aaaxxxxdhuizzuh


Try it online!

# APL (Dyalog Unicode), 5 bytesSBCS

Anonymous tacit prefix function, taking [string,ordering] as argument.

⍋⍨/⌷⊃


Try it online!

/ Reduce by the following function:

…⍨ namely the reversed-arguments version of the following function:

⍋ grade the right string according to the left ordering (missing letters go at the end)

⌷ use that to index into…

⊃ the first element of the argument (i.e. the string)

# Python 2, 35 50 bytes

lambda a,s:sorted(s,key=lambda c:-a[::-1].find(c))


Try it online!

Takes a and s as strings; returns a list of singelton strings.

Note: Ouch! Gained 15 bytes to fix...

• Ha! This is actually exactly the same as my original code for my answer. Great minds think alike
– Jo King
May 30, 2018 at 10:34
• @Jo King: Stop controlling my thoughts! :) May 31, 2018 at 6:06

# K (ngn/k), 9 bytes

{y@>-x?y}


Try it online!

{...} is a function with arguments x and y

x?y finds for each element in y the index of its first occurrence in x; if an element is not found in x, its index is considered 0N (-263)

- negates all indices except that it keeps the 0N-s intact, because 263≡-263 (mod 264)

> returns a sort-descending permutation

y@ indexes y with that

# Charcoal, 13 bytes

Ｆθ×ι№ηιΦη¬№θι


Try it online! Link is to verbose version of code. Explanation:

 θ              First input
Ｆ               Loop over characters
η          Second input
ι         Current character
№           Count matches
ι            Current character
×             Repeat
Implicitly print
η       Second input
Φ        Filter
θ    First input
ι   Current character
№     Count matches
¬      Logical not
Implicitly print non-matching characters


# Jelly, 4 bytes

fⱮ;ḟ


A dyadic link accepting the string on the left and the alphabet on the right (as lists of characters) and returning the result (also as a list of characters).

Try it online!

### How?

fⱮ;ḟ - Link: string; alphabet                                    e.g. smallnotxl; xl
Ɱ   - map (for each character in the alphabet):                      1=x; 2=l
f    -   filter keep (keep occurrences of this character from string)   x    lll -> xlll
ḟ - filter discard (discard all alphabet characters from string)   smanot
;  - concatenate                                                    xlllsmanot


# JavaScript (SpiderMonkey), 50 bytes

Takes input in currying syntax (a)(s), where a is a string and s is an array of characters. Returns an array of characters.

a=>s=>s.sort((b,c)=>(g=c=>-1/a.search(c))(b)-g(c))


Try it online!

### How?

We define the helper function g() as:

c => -1 / a.search(c)


which returns:

• 1 if c does not belong to the alphabet
• a float value in [-Inf, 0) based on the position of c in the alphabet otherwise (-Inf, -1, -1/2, -1/3, etc.)

We sort s[ ] by computing g(b) - g(c) for each pair of characters (b, c) passed to the callback of sort().

Because the implementation of sort() in SpiderMonkey is stable, all characters of s[ ] that do not belong to the alphabet are simply moved at the end in order of appearance and are let unchanged when they are compared with each other.

# JavaScript (ES6), 61 bytes

Takes input in currying syntax (a)(s), where both a and s are arrays of characters. Returns a string.

a=>s=>a.map(C=>s=s.filter(c=>c!=C||!(o+=c)),o='')&&o+s.join


Try it online!

# R, 69 62 58 bytes

function(a,s)c(rep(a,rowSums(outer(a,s,"=="))),s[!s%in%a])


Try it online!

Input and output are vectors of individual characters.

Explanation:

function(a,s)c(                              ,           ) #combine:
a,                                      #[each char in a
rep(                                        #each repeated
rowSums(               )              #the number of
outer(a,s,"==")               #occurrence in s]
s            #with s
[ s%in%a]   #all chars in a
!          #omitted


# Brain-Flak (BrainHack), 118 bytes

{({}(<>))<>}{}<>{<>([[]()]<{<>(({})<({}<>[({}<>)]){(<()>)}{}{}>)<>}<>({}<{({}<>)<>}<>>)>[]){({}()<(({}))>)}{}{}<>{}}<>


Try it online!

Input is the first string, followed by a null, followed by the second string. A version that uses a newline as the separator instead adds 24 bytes:

# Brain-Flak, 142 bytes

(()){{}(({}(<>))[(()()()()()){}]<>)}{}<>{<>([[]()]<{<>(({})<({}<>[({}<>)]){(<()>)}{}{}>)<>}<>({}<{({}<>)<>}<>>)>[]){({}()<(({}))>)}{}{}<>{}}<>


Try it online!

### Explanation

# Move A to other stack reversed
# Zeroes are pushed under each character for later.
# (This is the only part that needs to change in order to use newline as separator.)
{({}(<>))<>}{}<>

# For each character in A, starting at the end:
{

# Track current length of S.
<>([[]()]<

# For each character in S:
{

# While keeping character from A
<>(({})<

# Move character from S to second stack and push difference
({}<>[({}<>)])

# Delete character if equal
{(<()>)}{}{}

>)

<>}

# Move S back to first stack while maintaining character from A
<>({}<{({}<>)<>}<>>)

# Push difference between old and new lengths of S
>[])

# Insert character from A at beginning of S that many times
{({}()<(({}))>)}{}{}

<>{}}<>


# C (gcc), 97 bytes

f(D,d,S,s,i,o)char*D,*S;{
while(d--){
for(i=o=s;i--;)S[i]-D[d]?S[--o]=S[i]:0;
while(o--)S[o]=D[d];
}
}


All whitespaces (spaces and newlines) in the code above are only for readability and should be removed.

The dictionary is passed in D and have length d, the string is passed in S and have length s. i and o should be omitted.

Try it online!

# Pyth,  9  5 bytes

ox+vz


Try it here!

ox+vz    Full program. Input format: "S" \n "A".
o        Sort the characters of S by (variable: N)...
x       ... N's index in...
+vz    ... A + N


# Java 8, 98 bytes

a->s->{for(int i=a.length;i-->0;s=s.replaceAll("[^"+a[i]+"]","")+s.replaceAll(a[i],""));return s;}


Try it online.

Explanation:

a->s->{       // Method with String-array and String parameters, and String return-type
for(int i=a.length;i-->0;
//  Loop backwards over the alphabet
s=        //   Replace the current s with:
s.replaceAll("[^"+a[i]+"]","")
//    All the current characters of a in s
+s.replaceAll(a[i],""));
//    Concatted with everything else
return s;}  //  Return the modified s

• Couldn't go lower, even with Java 11's new String.repeat(int) method. Nice! :) May 29, 2018 at 14:34
• @OlivierGrégoire Oh, didn't knew early access to Java 11 was already available. That .repeat(n) looks promising, though. :D May 29, 2018 at 14:48

## Perl 5 with -pF, 43 bytes

$_=<>;print$F[0]x s/@{[shift@F]}//g while@F


Try it online!

• Isn't there a flag that gives you $_=<>; for free? May 28, 2018 at 14:39 • @Pavel yeah, sorry I'm using it to populate @F, but I didn't add it to the header! I'll do that now! Thank you! May 28, 2018 at 17:37 • You can cut 10 bytes off this and still use the same logic: Try it online! Aug 16, 2019 at 3:46 # Prolog (SWI), 136 bytes X/_/[X|_]. X/Y/[Z|R]:-Y\=Z,X/Y/R. i(_,X,[],[X]). i(A,X,[Y|R],[X,Y|R]):-X/Y/A. i(A,X,[Y|R],[Y|S]):-i(A,X,R,S). A*S*T:-foldl(i(A),S,[],T).  Try it online! Example usage: [i,l]*[n,m,i,u,p,l,l,i,u]*S. S = [i, i, l, l, n, m, u, p, u]  # Clean, 61 bytes import StdEnv$a s=[c\\c<-a,k<-s|k==c]++[c\\c<-s|all((<>)c)a]


Try it online!

Defines the function $:: [Char] [Char] -> [Char]. Unsurprisingly, this is literally nimi's Haskell answer but longer. # Jelly, 7 bytes i@oİ$¥Þ


Try it online!

# APL+WIN, 12 bytes

Prompts for screen input of S then A:

s[(,⎕)⍋s←,⎕]


Try it online! Courtesy of Dyalog Classic

# PynTree, 13 bytes

§yz:ṡzCæf+yxx


Try it online!

Port of Jo King's Python answer.

# Explanation

§yz:ṡzCæf+yxx  Anonymous lambda
§              lambda  ,
y                    y
z                     z
:                     :
ṡ                     sorted( ,lambda x:
z                           z
C                                     (          )( )
æf                                    (   ).find
+                                     +
y                                   y
x                                    x
x                                            x