Order disjoint list items: Difference between revisions

From Rosetta Code
Content added Content deleted
m (→‎{{header|REXX}}: add/changed whitespace and comments, changed wording in the REXX section header, made other cosmetic changes.)
Line 780: Line 780:


=={{header|REXX}}==
=={{header|REXX}}==
Items in   N   needn't be in   M.
Items in &nbsp; <big>'''N'''</big> &nbsp; needn't be in &nbsp; <big>'''M'''</big>.
<lang rexx>/*REXX program orders a disjoint list of M items with a list of N items.*/
<lang rexx>/*REXX program orders a disjoint list of M items with a list of N items.*/
used = '0'x /*indicates word has been parsed.*/
used = '0'x /*indicates that a word has been parsed*/
@. = /*placeholder indicates e─o─array*/
@. = /*placeholder indicates end─of─array, */
@.1 = " the cat sat on the mat | mat cat " /*string.*/
@.1 = " the cat sat on the mat | mat cat " /*a string. */
@.2 = " the cat sat on the mat | cat mat " /*string.*/
@.2 = " the cat sat on the mat | cat mat " /*" " */
@.3 = " A B C A B C A B C | C A C A " /*string.*/
@.3 = " A B C A B C A B C | C A C A " /*" " */
@.4 = " A B C A B D A B E | E A D A " /*string.*/
@.4 = " A B C A B D A B E | E A D A " /*" " */
@.5 = " A B | B " /*string.*/
@.5 = " A B | B " /*" " */
@.6 = " A B | B A " /*string.*/
@.6 = " A B | B A " /*" " */
@.7 = " A B B A | B A " /*string.*/
@.7 = " A B B A | B A " /*" " */
@.8 = " | " /*string.*/
@.8 = " | " /*" " */
@.9 = " A | A " /*string.*/
@.9 = " A | A " /*" " */
@.10 = " A B | " /*string.*/
@.10 = " A B | " /*" " */
@.11 = " A B B A | A B " /*string.*/
@.11 = " A B B A | A B " /*" " */
@.12 = " A B A B | A B " /*string.*/
@.12 = " A B A B | A B " /*" " */
@.13 = " A B A B | B A B A " /*string.*/
@.13 = " A B A B | B A B A " /*" " */
@.14 = " A B C C B A | A C A C " /*string.*/
@.14 = " A B C C B A | A C A C " /*" " */
@.15 = " A B C C B A | C A C A " /*string.*/
@.15 = " A B C C B A | C A C A " /*" " */
/* [↓] process each input string*/
/* ════════════M═══════════ ════N════ */
do j=1 while @.j\==''; r.= /*nullify the replacement string.*/
/* [↓] process each input strings. */
parse var @.j m '|' n /*parse input string into M & N.*/
do j=1 while @.j\==''; r.= /*nullify the replacement string [R.] */
parse var @.j m '|' n /*parse input string into M and N. */
mw=words(m); do i=mw for mw by -1; x=word(m,i); !.i=x; $.x=i; end
/* [↑] build ! and $ arrays. */
#=words(m) /*#: number of words in the M list.*/
do k=1 for words(n)%2 by 2 /* [↓] process the N array. */
do i=# for # by -1 /*process list items in reverse order. */
_=word(n,k); v=word(n,k+1) /*get an order word & replacement*/
_=word(m,i) /*obtain a soecific word from the list.*/
!.i=_; $._=i /*construct the !. and $. arrays.*/
p1=wordpos(_,m); p2=wordpos(v,m) /*positions of word & replacement*/
if p1==0 | p2==0 then iterate /*if either not found, skip 'em. */
end /*i*/

if $._>>$.v then do; r.p2=!.p1; r.p1=!.p2; end /*switch words.*/
else do; r.p1=!.p1; r.p2=!.p2; end /*don't switch.*/
do k=1 for words(n)%2 by 2 /* [↓] process the N array. */
!.p1=used; !.p2=used; m= /*mark as used.*/
_=word(n,k); v=word(n,k+1) /*get an order word and the replacement*/
do i=1 for mw; m=m !.i; x=word(m,i); !.i=x; $.x=i; end
p1=wordpos(_,m); p2=wordpos(v,m) /*positions of " " " " */
end /*k*/ /* [↑] rebuild the ! & $ arrays.*/
if p1==0 | p2==0 then iterate /*if either not found, then skip them. */

mp= /*the MP (M') string (so far).*/
do q=1 for mw; if !.q==used then mp=mp r.q /*use original. */
if $._>>$.v then do; r.p2=!.p1; r.p1=!.p2; end /*switch the words.*/
else mp=mp !.q /*use substitute*/
else do; r.p1=!.p1; r.p2=!.p2; end /*don't switch. */

end /*q*/ /* [↑] re-build the (output) str*/
/*═══════════════════════════════*/
!.p1=used; !.p2=used /*mark 'em as used.*/
m=
say @.j '───►' space(mp) /*display the new text reordered.*/
end /*j*/ /* [↑] end of processing N words*/
do i=1 for #; m=m !.i; _=word(m,i); !.i=_; $._=i; end
/*stick a fork in it, we're done.*/</lang>
end /*k*/ /* [↑] rebuild the !. and $. arrays.*/

'''output''' using the internal (input) strings:
mp= /*the MP (aka M') string (so far). */
do q=1 for #; if !.q==used then mp=mp r.q /*use the original.*/
else mp=mp !.q /*use substitute. */
end /*q*/ /* [↑] re─build the (output) string. */

say @.j '───►' space(mp) /*display new re─ordered text ──► term.*/
end /*j*/ /* [↑] end of processing for N words*/
/*stick a fork in it, we're all done. */</lang>
'''output''' &nbsp; using the internal (input) strings:
<pre>
<pre>
the cat sat on the mat | mat cat ───► the mat sat on the cat
the cat sat on the mat | mat cat ───► the mat sat on the cat
the cat sat on the mat | cat mat ───► the cat sat on the mat
the cat sat on the mat | cat mat ───► the cat sat on the mat
A B C A B C A B C | C A C A ───► C B A C B A A B C
A B C A B C A B C | C A C A ───► C B A C B A A B C
A B C A B D A B E | E A D A ───► E B C A B D A B A
A B C A B D A B E | E A D A ───► E B C A B D A B A
A B | B ───► A B
A B | B ───► A B
A B | B A ───► B A
A B | B A ───► B A
A B B A | B A ───► B A B A
A B B A | B A ───► B A B A
| ───►
| ───►
A | A ───► A
A | A ───► A
A B | ───► A B
A B | ───► A B
A B B A | A B ───► A B B A
A B B A | A B ───► A B B A
A B A B | A B ───► A B A B
A B A B | A B ───► A B A B
A B A B | B A B A ───► B A B A
A B A B | B A B A ───► B A B A
A B C C B A | A C A C ───► A B C A B C
A B C C B A | A C A C ───► A B C A B C
A B C C B A | C A C A ───► C B A C B A
A B C C B A | C A C A ───► C B A C B A
</pre>
</pre>



Revision as of 01:24, 14 October 2015

Task
Order disjoint list items
You are encouraged to solve this task according to the task description, using any language you may know.

Given M as a list of items and another list N of items chosen from M, create M' as a list with the first occurrences of items from N sorted to be in one of the set of indices of their original occurrence in M but in the order given by their order in N. That is, items in N are taken from M without replacement, then the corresponding positions in M' are filled by successive items from N.

For example:

if M is 'the cat sat on the mat'
And N is 'mat cat'
Then the result M' is 'the mat sat on the cat'.

The words not in N are left in their original positions.

If there are duplications then only the first instances in M up to as many as are mentioned in N are potentially re-ordered.

For example:

M = 'A B C A B C A B C'
N = 'C A C A'

Is ordered as:

M' = 'C B A C B A A B C'

Show the output, here, for at least the following inputs:

Data M: 'the cat sat on the mat' Order N: 'mat cat'
Data M: 'the cat sat on the mat' Order N: 'cat mat'
Data M: 'A B C A B C A B C'      Order N: 'C A C A'
Data M: 'A B C A B D A B E'      Order N: 'E A D A'
Data M: 'A B'                    Order N: 'B'      
Data M: 'A B'                    Order N: 'B A'    
Data M: 'A B B A'                Order N: 'B A'
Cf

AutoHotkey

Works with: AutoHotkey 1.1

<lang AutoHotkey>Data := [ {M: "the cat sat on the mat", N: "mat cat"} , {M: "the cat sat on the mat", N: "cat mat"} , {M: "A B C A B C A B C", N: "C A C A"} , {M: "A B C A B D A B E", N: "E A D A"} , {M: "A B", N: "B"} , {M: "A B", N: "B A"} , {M: "A B B A", N: "B A"} ]

for Key, Val in Data Output .= Val.M " :: " Val.N " -> " OrderDisjointList(Val.M, Val.N) "`n" MsgBox, % RTrim(Output, "`n")

OrderDisjointList(M, N) { ItemsN := [] Loop, Parse, N, % A_Space ItemsN[A_LoopField] := ItemsN[A_LoopField] ? ItemsN[A_LoopField] + 1 : 1 N := StrSplit(N, A_Space) Loop, Parse, M, % A_Space Result .= (ItemsN[A_LoopField]-- > 0 ? N.Remove(1) : A_LoopField) " " return RTrim(Result) }</lang>

Output:
the cat sat on the mat :: mat cat -> the mat sat on the cat
the cat sat on the mat :: cat mat -> the cat sat on the mat
A B C A B C A B C :: C A C A -> C B A C B A A B C
A B C A B D A B E :: E A D A -> E B C A B D A B A
A B :: B -> A B
A B :: B A -> B A
A B B A :: B A -> B A B A

Bracmat

<lang bracmat>( ( odli

 =   M N NN item A Z R
   .   !arg:(?M.?N)
     & :?NN
     &   whl
       ' ( !N:%?item ?N
         & (   !M:?A !item ?Z
             & !A (.) !Z:?M
             & !NN !item:?NN
           |
           )
         )
     & :?R
     &   whl
       ' ( !M:?A (.) ?M
         & !NN:%?item ?NN
         & !R !A !item:?R
         )
     & !R !M
 )

& (the cat sat on the mat.mat cat)

     (the cat sat on the mat.cat mat)
     (A B C A B C A B C.C A C A)
     (A B C A B D A B E.E A D A)
     (A B.B)
     (A B.B A)
     (A B B A.B A)
 : ?tests

& whl

 ' ( !tests:(?M.?N) ?tests
   & put$("Data M:" !M)
   & put$("\tOrder N:" !N)
   & out$(\t odli$(!M.!N))
   )

);</lang> Output:

Data M: the cat sat on the mat  Order N: mat cat         the mat sat on the cat
Data M: the cat sat on the mat  Order N: cat mat         the cat sat on the mat
Data M: A B C A B C A B C       Order N: C A C A         C B A C B A A B C
Data M: A B C A B D A B E       Order N: E A D A         E B C A B D A B A
Data M: A B     Order N: B       A B
Data M: A B     Order N: B A     B A
Data M: A B B A Order N: B A     B A B A

D

Translation of: Python

This version is not efficient. <lang d>import std.stdio, std.string, std.algorithm, std.array, std.range,

      std.conv;

T[] orderDisjointArrayItems(T)(in T[] data, in T[] items) pure /*nothrow*/ @safe {

   int[] itemIndices;
   foreach (item; items.dup.sort().uniq) {
       immutable int itemCount = items.count(item);
       assert(data.count(item) >= itemCount,
              text("More of ", item, " than in data"));
       auto lastIndex = [-1];
       foreach (immutable _; 0 .. itemCount) {
           immutable start = lastIndex.back + 1;
           lastIndex ~= data[start .. $].countUntil(item) + start;
       }
       itemIndices ~= lastIndex.dropOne;
   }
   itemIndices.sort();
   auto result = data.dup;
   foreach (index, item; zip(itemIndices, items))
       result[index] = item;
   return result;

}

void main() {

   immutable problems =
  "the cat sat on the mat  | mat cat
   the cat sat on the mat  | cat mat
   A B C A B C A B C       | C A C A
   A B C A B D A B E       | E A D A
   A B                     | B
   A B                     | B A
   A B B A                 | B A
                           |
   A                       | A
   A B                     |
   A B B A                 | A B
   A B A B                 | A B
   A B A B                 | B A B A
   A B C C B A             | A C A C
   A B C C B A             | C A C A"
   .splitLines.map!(r => r.split("|")).array;
   foreach (immutable p; problems) {
       immutable a = p[0].split;
       immutable b = p[1].split;
       writefln("%s | %s -> %-(%s %)", p[0].strip, p[1].strip,
                orderDisjointArrayItems(a, b));
   }

}</lang>

Output:
the cat sat on the mat | mat cat -> the mat sat on the cat
the cat sat on the mat | cat mat -> the cat sat on the mat
A B C A B C A B C | C A C A -> C B A C B A A B C
A B C A B D A B E | E A D A -> E B C A B D A B A
A B | B -> A B
A B | B A -> B A
A B B A | B A -> B A B A
 |  -> 
A | A -> A
A B |  -> A B
A B B A | A B -> A B B A
A B A B | A B -> A B A B
A B A B | B A B A -> B A B A
A B C C B A | A C A C -> A B C A B C
A B C C B A | C A C A -> C B A C B A

Go

<lang go>package main

import ( "fmt" "sort" "strings" )

type indexSort struct { val sort.Interface ind []int }

func (s indexSort) Len() int { return len(s.ind) } func (s indexSort) Less(i, j int) bool { return s.ind[i] < s.ind[j] } func (s indexSort) Swap(i, j int) { s.val.Swap(s.ind[i], s.ind[j]) s.ind[i], s.ind[j] = s.ind[j], s.ind[i] }

func disjointSliceSort(m, n []string) []string { s := indexSort{sort.StringSlice(m), make([]int, 0, len(n))} used := make(map[int]bool) for _, nw := range n { for i, mw := range m { if used[i] || mw != nw { continue } used[i] = true s.ind = append(s.ind, i) break } } sort.Sort(s) return s.val.(sort.StringSlice) }

func disjointStringSort(m, n string) string { return strings.Join( disjointSliceSort(strings.Fields(m), strings.Fields(n)), " ") }

func main() { for _, data := range []struct{ m, n string }{ {"the cat sat on the mat", "mat cat"}, {"the cat sat on the mat", "cat mat"}, {"A B C A B C A B C", "C A C A"}, {"A B C A B D A B E", "E A D A"}, {"A B", "B"}, {"A B", "B A"}, {"A B B A", "B A"}, } { mp := disjointStringSort(data.m, data.n) fmt.Printf("%s → %s » %s\n", data.m, data.n, mp) }

}</lang>

Output:
the cat sat on the mat → mat cat » the mat sat on the cat
the cat sat on the mat → cat mat » the cat sat on the mat
the cat sat on the mat → cat cat cat mat » the cat sat on the mat
A B C A B C A B C → C A C A » C B A C B A A B C
A B C A B D A B E → E A D A » E B C A B D A B A
A B → B » A B
A B → B A » B A
A B B A → B A » B A B A

Icon and Unicon

Works in both languages. Assumes a single blank separates items:

<lang unicon>procedure main(A)

   every write(" -> ",odli("the cat sat on the mat","mat cat"))
   every write(" -> ",odli("the cat sat on the mat","cat mat"))
   every write(" -> ",odli("A B C A B C A B C","C A C A"))
   every write(" -> ",odli("A B C A B D A B E","E A D A"))
   every write(" -> ",odli("A B","B"))
   every write(" -> ",odli("A B","B A"))
   every write(" -> ",odli("A B B A","B A"))

end

procedure odli(M,N)

   writes(M," :: ",N)
   Mp := "" 
   P := N ||:= " "
   (M||" ") ? while item := tab(upto(' '))||move(1) do {
           if find(item,P) then {
               P ?:= 1(tab(find(item)),move(*item))||tab(0)
               N ?:= (item := tab(upto(' '))||move(1), tab(0))
               }
           Mp ||:= item
           }
   return Mp

end</lang>

Output:

->odli
the cat sat on the mat :: mat cat -> the mat sat on the cat 
the cat sat on the mat :: cat mat -> the cat sat on the mat 
A B C A B C A B C :: C A C A -> C B A C B A A B C 
A B C A B D A B E :: E A D A -> E B C A B D A B A 
A B :: B -> A B 
A B :: B A -> B A 
A B B A :: B A -> B A B A 
->

J

Implementation:

<lang J>disjorder=:3 :0&.;:

 clusters=. (</. i.@#) x
 order=. x i.&~. y
 need=. #/.~ y
 from=. ;need (#{.)each (/:~order){clusters
 to=. ;need {.!._ each order{clusters
 (from{x) to} x

)</lang>

Task examples:

<lang J> 'the cat sat on the mat' disjorder 'mat cat' the mat sat on the cat

  'the cat sat on the mat' disjorder 'cat mat'

the cat sat on the mat

  'A B C A B C A B C'      disjorder 'C A C A'

C B A C B A A B C

  'A B C A B D A B E'      disjorder 'E A D A'

D B C D B E A B A

  'A B'                    disjorder 'B'      

A B

  'A B'                    disjorder 'B A'    

B A

  'A B B A'                disjorder 'B A'

B A B A</lang>


Java

Doesn't handle the case when an item of N is not a member of M. <lang java>import java.util.Arrays; import java.util.BitSet; import org.apache.commons.lang3.ArrayUtils;

public class OrderDisjointItems {

   public static void main(String[] args) {
       final String[][] MNs = {{"the cat sat on the mat", "mat cat"},
       {"the cat sat on the mat", "cat mat"},
       {"A B C A B C A B C", "C A C A"}, {"A B C A B D A B E", "E A D A"},
       {"A B", "B"}, {"A B", "B A"}, {"A B B A", "B A"}, {"X X Y", "X"}};
       for (String[] a : MNs) {
           String[] r = orderDisjointItems(a[0].split(" "), a[1].split(" "));
           System.out.printf("%s | %s -> %s%n", a[0], a[1], Arrays.toString(r));
       }
   }
   // if input items cannot be null
   static String[] orderDisjointItems(String[] m, String[] n) {
       for (String e : n) {
           int idx = ArrayUtils.indexOf(m, e);
           if (idx != -1)
               m[idx] = null;
       }
       for (int i = 0, j = 0; i < m.length; i++) {
           if (m[i] == null)
               m[i] = n[j++];
       }
       return m;
   }
   // otherwise
   static String[] orderDisjointItems2(String[] m, String[] n) {
       BitSet bitSet = new BitSet(m.length);
       for (String e : n) {
           int idx = -1;
           do {
               idx = ArrayUtils.indexOf(m, e, idx + 1);
           } while (idx != -1 && bitSet.get(idx));
           if (idx != -1)
               bitSet.set(idx);
       }
       for (int i = 0, j = 0; i < m.length; i++) {
           if (bitSet.get(i))
               m[i] = n[j++];
       }
       return m;
   }

}</lang>

Output:

the cat sat on the mat | mat cat -> [the, mat, sat, on, the, cat]
the cat sat on the mat | cat mat -> [the, cat, sat, on, the, mat]
A B C A B C A B C | C A C A -> [C, B, A, C, B, A, A, B, C]
A B C A B D A B E | E A D A -> [E, B, C, A, B, D, A, B, A]
A B | B -> [A, B]
A B | B A -> [B, A]
A B B A | B A -> [B, A, B, A]
X X Y | X -> [X, X, Y]

jq

Works with: jq version 1.4

Usage: M | disjoint_order(N) <lang jq>def disjoint_order(N):

 # The helper function, indices, ensures that successive occurrences
 # of a particular value in N are matched by successive occurrences
 # in the input on the assumption that null is not initially in the input.
 def indices:
   . as $in
   | reduce range(0; N|length) as $i
      # state: [ array, indices ]
     ( [$in, []];
       (.[0] | index(N[$i])) as $ix | .[0][$ix] = null | .[1] += [$ix])
   | .[1];
 . as $in
 | (indices | sort) as $sorted
 | reduce range(0; N|length) as $i ($in; .[$sorted[$i]] = N[$i] ) ;</lang>

Examples:

(scrollable)

<lang jq>["the", "cat", "sat", "on", "the", "mat"] | indices( ["mat", "cat"] )

  1. => ["the","mat","sat","on","the","cat"]</lang>

<lang jq>["the", "cat", "sat", "on", "the", "mat"] | disjoint_order( ["cat", "mat"] )

  1. => ["the","cat","sat","on","the","mat"]</lang>

<lang jq>["A", "B", "C", "A", "B", "C", "A", "B", "C"] | disjoint_order( ["C", "A", "C", "A"] )

  1. => ["C","B","A","C","B","A","A","B","C"]</lang>

<lang jq>["A", "B", "C", "A", "B", "D", "A", "B", "E"] | disjoint_order( ["E", "A", "D", "A"] )

  1. => ["E","B","C","A","B","D","A","B","A"]</lang>

<lang jq>["A", "B"] | disjoint_order( ["B"] )

  1. => ["A","B"]</lang>

<lang jq>["A", "B"] | disjoint_order( ["B", "A"] )

  1. => ["B","A"]</lang>

<lang jq>["A", "B", "B", "A"] | disjoint_order( ["B", "A"] )

  1. => ["B","A","B","A"]</lang>

<lang jq>["X", "X", "Y"] | disjoint_order(["X"])

  1. => [X, X, Y]</lang>

Julia

order_disjoint works by finding the indices of n in m and replacing the elements in m with those in n according to the sorted indices. When n either contains elements not in m or more copies of an element than exist in m, the function throws a DomainError.

Function <lang Julia> function order_disjoint{T<:AbstractArray}(m::T, n::T)

   rlen = length(n)
   rdis = zeros(Int, rlen)
   for (i, e) in enumerate(n)
       j = findfirst(m, e)
       while j in rdis && j != 0
           j = findnext(m, e, j+1)
       end
       rdis[i] = j
   end
   if 0 in rdis
       throw(DomainError())
   end
   sort!(rdis)
   p = copy(m)
   p[rdis] = n
   return p

end </lang> Main <lang Julia> testm = {["the", "cat", "sat", "on", "the", "mat"],

        ["the", "cat", "sat", "on", "the", "mat"],
        ["A", "B", "C", "A", "B", "C", "A", "B", "C"],
        ["A", "B", "C", "A", "B", "D", "A", "B", "E"],
        ["A", "B"],
        ["A", "B"],
        ["A", "B", "B", "A"],
        }

testn = {["mat", "cat"],

        ["cat", "mat"],
        ["C", "A", "C", "A"],
        ["E", "A", "D", "A"],
        ["B"],
        ["B", "A"],
        ["B", "A"],
        }

for i in 1:length(testm)

   m = join(testm[i], " ")
   n = join(testn[i], " ")
   p = join(order_disjoint(testm[i], testn[i]), " ")
   println("    (", m, ", ", n, ") => ", p)

end </lang>

Output:
    (the cat sat on the mat, mat cat) => the mat sat on the cat
    (the cat sat on the mat, cat mat) => the cat sat on the mat
    (A B C A B C A B C, C A C A) => C B A C B A A B C
    (A B C A B D A B E, E A D A) => E B C A B D A B A
    (A B, B) => A B
    (A B, B A) => B A
    (A B B A, B A) => B A B A

Mathematica

<lang Mathematica>order[m_, n_] :=

 ReplacePart[m, 
  MapThread[
   Rule, {Position[m, Alternatives @@ n][[;; Length[n]]], n}]];

Print[StringRiffle[

  order[{"the", "cat", "sat", "on", "the", "mat"}, {"mat", 
    "cat"}]]];

Print[StringRiffle[

  order[{"the", "cat", "sat", "on", "the", "mat"}, {"cat", 
    "mat"}]]];

Print[StringRiffle[

  order[{"A", "B", "C", "A", "B", "C", "A", "B", "C"}, {"C", "A", 
    "C", "A"}]]];

Print[StringRiffle[

  order[{"A", "B", "C", "A", "B", "D", "A", "B", "E"}, {"E", "A", 
    "D", "A"}]]];

Print[StringRiffle[order[{"A", "B"}, {"B"}]]]; Print[StringRiffle[order[{"A", "B"}, {"B", "A"}]]]; Print[StringRiffle[order[{"A", "B", "B", "A"}, {"B", "A"}]]];</lang>

Output:
the mat sat on the cat
the cat sat on the mat
C B A C B A A B C
E B C A B D A B E
A B
B A
B A B A

Perl

<lang perl>sub dsort {

       my ($m, $n) = @_;
       my %h;
       $h{$_}++ for @$n;
       map $h{$_}-- > 0 ? shift @$n : $_, @$m;

}

for (split "\n", <<"IN")

       the cat sat on the mat  | mat cat
       the cat sat on the mat  | cat mat
       A B C A B C A B C       | C A C A
       A B C A B D A B E       | E A D A
       A B                     | B
       A B                     | B A
       A B B A                 | B A

IN {

       my ($a, $b) = map([split], split '\|');
       print "@$a | @$b -> @{[dsort($a, $b)]}\n";

}</lang>

Output:
the cat sat on the mat | mat cat -> the mat sat on the cat
the cat sat on the mat | mat cat -> the mat sat on the cat
the cat sat on the mat | cat mat -> the cat sat on the mat
A B C A B C A B C | C A C A -> C B A C B A A B C
A B C A B D A B E | E A D A -> E B C A B D A B A
A B | B -> A B
A B | B A -> B A
A B B A | B A -> B A B A

Perl 6

Works with: rakudo version 2014-05-13

<lang perl6>sub order-disjoint-list-items(\M, \N) {

   my \bag = N.BagHash;
   M.map: { bag{$_}-- ?? N.shift !! $_ }

}</lang>

Testing:

<lang perl6>for q:to/---/.comb(/ [\S+]+ % ' ' /).map({[.words]})

   the cat sat on the mat      mat cat
   the cat sat on the mat      cat mat
   A B C A B C A B C           C A C A
   A B C A B D A B E           E A D A
   A B                         B
   A B                         B A
   A B B A                     B A
   X X Y                       X
   A X                         Y A
   ---

-> $m, $n { say "\n$m ==> $n\n", order-disjoint-list-items($m, $n) }</lang>

Output:
the cat sat on the mat ==> mat cat
the mat sat on the cat

the cat sat on the mat ==> cat mat
the cat sat on the mat

A B C A B C A B C ==> C A C A
C B A C B A A B C

A B C A B D A B E ==> E A D A
E B C A B D A B A

A B ==> B
A B

A B ==> B A
B A

A B B A ==> B A
B A B A

X X Y ==> X
X X Y

A X ==> Y A
Y X

PowerShell

<lang PowerShell> function sublistsort($M, $N) {

   $arr = $M.Split(' ')
   $array = $N.Split(' ') | group
   $Count = @($array |foreach {$_.Count})
   $ip, $i = @(), 0
   $arr | foreach{ 
       $name = "$_"
       $j = $array.Name.IndexOf($name)
       if($j -gt -1){
           $k = $Count[$j] - 1
           if($k -ge 0) {
               $ip += @($i)
               $Count[$j] = $k
           }
       }
       $i++
   }
   $i = 0
   $N.Split(' ') | foreach{ $arr[$ip[$i++]] = "$_"}
   [pscustomobject]@{
       "M" = "$M "
       "N" = "$N "
       "M'" = "$($arr)"
   } 

} $M1 = 'the cat sat on the mat' $N1 = 'mat cat' $M2 = 'the cat sat on the mat' $N2 = 'cat mat' $M3 = 'A B C A B C A B C' $N3 = 'C A C A' $M4 = 'A B C A B D A B E' $N4 = 'E A D A' $M5 = 'A B' $N5 = 'B' $M6 = 'A B' $N6 = 'B A' $M7 = 'A B B A' $N7 = 'B A' sublistsort $M1 $N1 sublistsort $M2 $N2 sublistsort $M3 $N3 sublistsort $M4 $N4 sublistsort $M5 $N5 sublistsort $M6 $N6 sublistsort $M7 $N7 </lang> Output:

M                       N        M'                    
-                       -        --                    
the cat sat on the mat  mat cat  the mat sat on the cat
the cat sat on the mat  cat mat  the cat sat on the mat
A B C A B C A B C       C A C A  C B A C B A A B C     
A B C A B D A B E       E A D A  E B C A B D A B A     
A B                     B        A B                   
A B                     B A      B A                   
A B B A                 B A      B A B A

Python

<lang python>from __future__ import print_function

def order_disjoint_list_items(data, items):

   #Modifies data list in-place
   itemindices = []
   for item in set(items):
       itemcount = items.count(item)
       #assert data.count(item) >= itemcount, 'More of %r than in data' % item
       lastindex = [-1]
       for i in range(itemcount):
           lastindex.append(data.index(item, lastindex[-1] + 1))
       itemindices += lastindex[1:]
   itemindices.sort()
   for index, item in zip(itemindices, items):
       data[index] = item

if __name__ == '__main__':

   tostring = ' '.join
   for data, items in [ (str.split('the cat sat on the mat'), str.split('mat cat')),
                        (str.split('the cat sat on the mat'), str.split('cat mat')),
                        (list('ABCABCABC'), list('CACA')),
                        (list('ABCABDABE'), list('EADA')),
                        (list('AB'), list('B')),
                        (list('AB'), list('BA')),
                        (list('ABBA'), list('BA')),
                        (list(), list()),
                        (list('A'), list('A')),
                        (list('AB'), list()),
                        (list('ABBA'), list('AB')),
                        (list('ABAB'), list('AB')),
                        (list('ABAB'), list('BABA')),
                        (list('ABCCBA'), list('ACAC')),
                        (list('ABCCBA'), list('CACA')),
                      ]:
       print('Data M: %-24r Order N: %-9r' % (tostring(data), tostring(items)), end=' ')
       order_disjoint_list_items(data, items)
       print("-> M' %r" % tostring(data))</lang>
Output:
Data M: 'the cat sat on the mat' Order N: 'mat cat' -> M' 'the mat sat on the cat'
Data M: 'the cat sat on the mat' Order N: 'cat mat' -> M' 'the cat sat on the mat'
Data M: 'A B C A B C A B C'      Order N: 'C A C A' -> M' 'C B A C B A A B C'
Data M: 'A B C A B D A B E'      Order N: 'E A D A' -> M' 'E B C A B D A B A'
Data M: 'A B'                    Order N: 'B'       -> M' 'A B'
Data M: 'A B'                    Order N: 'B A'     -> M' 'B A'
Data M: 'A B B A'                Order N: 'B A'     -> M' 'B A B A'
Data M: ''                       Order N: ''        -> M' ''
Data M: 'A'                      Order N: 'A'       -> M' 'A'
Data M: 'A B'                    Order N: ''        -> M' 'A B'
Data M: 'A B B A'                Order N: 'A B'     -> M' 'A B B A'
Data M: 'A B A B'                Order N: 'A B'     -> M' 'A B A B'
Data M: 'A B A B'                Order N: 'B A B A' -> M' 'B A B A'
Data M: 'A B C C B A'            Order N: 'A C A C' -> M' 'A B C A B C'
Data M: 'A B C C B A'            Order N: 'C A C A' -> M' 'C B A C B A'

Racket

<lang racket>#lang racket (define disjorder

 (match-lambda**
  (((list) n) '())      
  ((m (list)) m)      
  (((list h m-tail ...) (list h n-tail ...))
   (list* h (disjorder m-tail n-tail)))
  ;; the (not g/h) below stop greedy matching of the list which
  ;; would pick out orderings from the right first.
  (((list h (and (not g) m-tail-left) ... g m-tail-right ...)
    (list g (and (not h) n-tail-left) ... h n-tail-right ...))
   (disjorder `(,g ,@m-tail-left ,h ,@m-tail-right)
              `(,g ,@n-tail-left ,h ,@n-tail-right)))
  (((list h m-tail ...) n)
   (list* h (disjorder m-tail n)))))

(define (report-disjorder m n)

(printf "Data M: ~a Order N: ~a -> ~a~%"
 (~a #:min-width 25 m) (~a #:min-width 10 n) (disjorder m n)))
Do the task tests

(report-disjorder '(the cat sat on the mat) '(mat cat)) (report-disjorder '(the cat sat on the mat) '(cat mat)) (report-disjorder '(A B C A B C A B C) '(C A C A)) (report-disjorder '(A B C A B D A B E) '(E A D A)) (report-disjorder '(A B) '(B)) (report-disjorder '(A B) '(B A)) (report-disjorder '(A B B A) '(B A))

Do all of the other python tests

(report-disjorder '() '()) (report-disjorder '(A) '(A)) (report-disjorder '(A B) '()) (report-disjorder '(A B B A) '(A B)) (report-disjorder '(A B A B) '(A B)) (report-disjorder '(A B A B) '(B A B A)) (report-disjorder '(A B C C B A) '(A C A C)) (report-disjorder '(A B C C B A) '(C A C A))</lang>

Output:
Data M: (the cat sat on the mat)  Order N: (mat cat)  -> (the mat sat on the cat)
Data M: (the cat sat on the mat)  Order N: (cat mat)  -> (the cat sat on the mat)
Data M: (A B C A B C A B C)       Order N: (C A C A)  -> (C B A C B A A B C)
Data M: (A B C A B D A B E)       Order N: (E A D A)  -> (E B C A B D A B A)
Data M: (A B)                     Order N: (B)        -> (A B)
Data M: (A B)                     Order N: (B A)      -> (B A)
Data M: (A B B A)                 Order N: (B A)      -> (B A B A)
Data M: ()                        Order N: ()         -> ()
Data M: (A)                       Order N: (A)        -> (A)
Data M: (A B)                     Order N: ()         -> (A B)
Data M: (A B B A)                 Order N: (A B)      -> (A B B A)
Data M: (A B A B)                 Order N: (A B)      -> (A B A B)
Data M: (A B A B)                 Order N: (B A B A)  -> (B A B A)
Data M: (A B C C B A)             Order N: (A C A C)  -> (A B C A B C)
Data M: (A B C C B A)             Order N: (C A C A)  -> (C B A C B A)

REXX

Items in   N   needn't be in   M. <lang rexx>/*REXX program orders a disjoint list of M items with a list of N items.*/ used = '0'x /*indicates that a word has been parsed*/ @. = /*placeholder indicates end─of─array, */ @.1 = " the cat sat on the mat | mat cat " /*a string. */ @.2 = " the cat sat on the mat | cat mat " /*" " */ @.3 = " A B C A B C A B C | C A C A " /*" " */ @.4 = " A B C A B D A B E | E A D A " /*" " */ @.5 = " A B | B " /*" " */ @.6 = " A B | B A " /*" " */ @.7 = " A B B A | B A " /*" " */ @.8 = " | " /*" " */ @.9 = " A | A " /*" " */ @.10 = " A B | " /*" " */ @.11 = " A B B A | A B " /*" " */ @.12 = " A B A B | A B " /*" " */ @.13 = " A B A B | B A B A " /*" " */ @.14 = " A B C C B A | A C A C " /*" " */ @.15 = " A B C C B A | C A C A " /*" " */

     /*  ════════════M═══════════             ════N════                      */
                                      /* [↓]  process each input strings.    */
 do j=1  while  @.j\==;     r.=     /*nullify the replacement string  [R.] */
 parse var  @.j  m  '|'  n            /*parse input string into  M  and  N.  */
 #=words(m)                           /*#:   number of words in the  M  list.*/
               do i=#  for #  by -1   /*process list items in reverse order. */
               _=word(m,i)            /*obtain a soecific word from the list.*/
               !.i=_;         $._=i   /*construct the   !.   and  $.  arrays.*/
               end   /*i*/
   do k=1  for  words(n)%2  by 2      /* [↓]  process the  N  array.         */
   _=word(n,k);   v=word(n,k+1)       /*get an order word and the replacement*/
   p1=wordpos(_,m);  p2=wordpos(v,m)  /*positions of   "   "   "       "     */
   if p1==0 | p2==0  then iterate     /*if either not found, then skip them. */
   if $._>>$.v  then do;  r.p2=!.p1;  r.p1=!.p2;  end     /*switch the words.*/
                else do;  r.p1=!.p1;  r.p2=!.p2;  end     /*don't switch.    */
   !.p1=used; !.p2=used                                   /*mark 'em as used.*/
   m=
                     do i=1  for #;  m=m !.i;  _=word(m,i); !.i=_;  $._=i;  end
   end   /*k*/                        /* [↑]  rebuild the  !. and  $. arrays.*/
 mp=                                  /*the  MP  (aka M')  string  (so far). */
      do q=1  for #;   if !.q==used  then mp=mp  r.q      /*use the original.*/
                                     else mp=mp  !.q      /*use substitute.  */
      end   /*q*/                     /* [↑]  re─build the (output) string.  */
 say @.j  '───►'  space(mp)           /*display new re─ordered text ──► term.*/
 end        /*j*/                     /* [↑]  end of processing for  N  words*/
                                      /*stick a fork in it,  we're all done. */</lang>

output   using the internal (input) strings:

 the cat sat on the mat      |      mat cat   ───► the mat sat on the cat
 the cat sat on the mat      |      cat mat   ───► the cat sat on the mat
 A B C A B C A B C           |      C A C A   ───► C B A C B A A B C
 A B C A B D A B E           |      E A D A   ───► E B C A B D A B A
 A B                         |      B         ───► A B
 A B                         |      B A       ───► B A
 A B B A                     |      B A       ───► B A B A
                             |                ───►
 A                           |      A         ───► A
 A B                         |                ───► A B
 A B B A                     |      A B       ───► A B B A
 A B A B                     |      A B       ───► A B A B
 A B A B                     |      B A B A   ───► B A B A
 A B C C B A                 |      A C A C   ───► A B C A B C
 A B C C B A                 |      C A C A   ───► C B A C B A

Ruby

<lang ruby>[ 'the cat sat on the mat', 'mat cat', 'the cat sat on the mat', 'cat mat', 'A B C A B C A B C' , 'C A C A', 'A B C A B D A B E' , 'E A D A', 'A B' , 'B', 'A B' , 'B A', 'A B B A' , 'B A' ].each_slice(2) do |s, o|

 s, o = s.split, o.split
 print [s, '|' , o, ' -> '].join(' ') 
 from = 0
 o.each_slice(2) do |x, y|
   next unless y
   if x > y && (s[from..-1].include? x) && (s[from..-1].include? y)
     new_from = [s.index(x), s.index(y)].max+1
     if s[from..-1].index(x) > s[from..-1].index(y)
       s[s.index(x)+from], s[s.index(y)+from] = s[s.index(y)+from], s[s.index(x)+from]
       from = new_from
     end
   end
 end
 puts s.join(' ')

end </lang>

Output:
the cat sat on the mat | mat cat  -> the mat sat on the cat
the cat sat on the mat | cat mat  -> the cat sat on the mat
A B C A B C A B C | C A C A  -> C B A C B A A B C
A B C A B D A B E | E A D A  -> E B C A B D A B A
A B | B  -> A B
A B | B A  -> B A
A B B A | B A  -> B A B A

Scala

<lang Scala>def order[T](input: Seq[T], using: Seq[T], used: Seq[T] = Seq()): Seq[T] =

 if (input.isEmpty || used.size >= using.size) input
 else if (using diff used contains input.head)
   using(used.size) +: order(input.tail, using, used :+ input.head)
 else input.head +: order(input.tail, using, used)</lang>

Test: <lang Scala>val tests = List(

 "the cat sat on the mat" -> "mat cat",
 "the cat sat on the mat" -> "cat mat",
 "A B C A B C A B C"      -> "C A C A",
 "A B C A B D A B E"      -> "E A D A",
 "A B"                    -> "B",
 "A B"                    -> "B A",
 "A B B A"                -> "B A"

)

tests.foreach{case (input, using) =>

 val done = order(input.split(" "), using.split(" "))
 println(f"""Data M: $input%-24s Order N: $using%-9s -> Result M': ${done mkString " "}""")

}</lang>

Output:
Data M: the cat sat on the mat   Order N: mat cat   -> Result M': the mat sat on the cat
Data M: the cat sat on the mat   Order N: cat mat   -> Result M': the cat sat on the mat
Data M: A B C A B C A B C        Order N: C A C A   -> Result M': C B A C B A A B C
Data M: A B C A B D A B E        Order N: E A D A   -> Result M': E B C A B D A B A
Data M: A B                      Order N: B         -> Result M': A B
Data M: A B                      Order N: B A       -> Result M': B A
Data M: A B B A                  Order N: B A       -> Result M': B A B A

Sidef

Translation of: Perl

<lang ruby>func dsort(m, n) {

   var h = Hash.new -> default(0);
   n.each {|item| h[item]++ };
   m.map  {|item| h[item]-- > 0 ? n.shift : item};

}

<<'EOT'.lines.each { |line|

       the cat sat on the mat  | mat cat
       the cat sat on the mat  | cat mat
       A B C A B C A B C       | C A C A
       A B C A B D A B E       | E A D A
       A B                     | B
       A B                     | B A
       A B B A                 | B A

EOT

       var (a, b) = line.split('|').map{.words}...;
       say "#{a} | #{b} -> #{dsort(a.copy, b.copy)}";

}</lang>

Output:
the cat sat on the mat | mat cat -> the mat sat on the cat
the cat sat on the mat | cat mat -> the cat sat on the mat
A B C A B C A B C | C A C A -> C B A C B A A B C
A B C A B D A B E | E A D A -> E B C A B D A B A
A B | B -> A B
A B | B A -> B A
A B B A | B A -> B A B A

Tcl

This is a simple version that assumes that all items in the order list are present in the list to be arranged: <lang tcl>proc orderDisjoint {theList theOrderList} {

   foreach item $theOrderList {incr n($item)}
   set is {}
   set i 0
   foreach item $theList {

if {[info exist n($item)] && [incr n($item) -1] >= 0} { lappend is $i } incr i

   }
   foreach item $theOrderList i $is {lset theList $i $item}
   return $theList

}</lang> This is a more sophisticated version that handles items in the order list not being present in the list to be arranged: <lang tcl>proc orderDisjoint {theList theOrderList} {

   foreach item $theOrderList {incr n($item)}
   set is -
   set i 0
   foreach item $theList {

if {[info exist n($item)] && [incr n($item) -1] >= 0} { lappend is $i } incr i

   }
   set i 0
   foreach item $theOrderList {

if {[incr n($item)] <= 1} { lset theList [lindex $is [incr i]] $item }

   }
   return $theList

}</lang> Demonstration code (produces the same output from both implementations): <lang tcl>foreach {items order} {

   "the cat sat on the mat" "mat cat"
   "the cat sat on the mat" "cat mat"
   "A B C A B C A B C"      "C A C A"
   "A B C A B D A B E"      "E A D A"
   "A B"                    "B"
   "A B"                    "B A"
   "A B B A"                "B A"

} {

   puts "'$items' with '$order' => '[orderDisjoint $items $order]'"

}</lang>

Output:
'the cat sat on the mat' with 'mat cat' => 'the mat sat on the cat'
'the cat sat on the mat' with 'cat mat' => 'the cat sat on the mat'
'A B C A B C A B C' with 'C A C A' => 'C B A C B A A B C'
'A B C A B D A B E' with 'E A D A' => 'E B C A B D A B A'
'A B' with 'B' => 'A B'
'A B' with 'B A' => 'B A'
'A B B A' with 'B A' => 'B A B A'

zkl

<lang zkl>fcn disOrder(sm,sn){

  M:=sm.split(" ");
  N:=sn.split(" "); nc:=Utils.Helpers.cycle(Utils.Helpers.listUnique(N));
  dn:=D(); N.pump(Void,'wrap(w){ dn[w] = dn.find(w,0) + 1; });
  M.pump(String,'wrap(w){ 
     if (Void==(n:=dn.find(w))) return(w); // not replaced
     if (n) { dn[w]=n-1; nc.next(); } // swaps left--
     else   { nc.next(); w }	       // exhausted
  }, String.fp(" ") )[1,*]	// remove leading blank

}</lang> A dictionary is used to hold count of the words in N, which is decremented as the words are used up. A cycle of the words is consumed to track the replacement values. It is assumed that there are no leading/trailing/consecutive spaces (easy to cover with a .filter()). <lang zkl>sets:=T(T("the cat sat on the mat","mat cat"),

       T("the cat sat on the mat","cat mat"),
       T("A B C A B C A B C","C A C A"),
       T("A B C A B D A B E","E A D A"),
       T("A B","B"), T("A B","B A"), T("A B B A","B A") );

foreach m,n in (sets){

  m.println(" / ",n," --> ",disOrder(m,n));

}</lang>

Output:
the cat sat on the mat / mat cat --> the mat sat on the cat
the cat sat on the mat / cat mat --> the cat sat on the mat
A B C A B C A B C / C A C A --> C B A C B A A B C
A B C A B D A B E / E A D A --> E B C A B D A B A
A B / B --> A B
A B / B A --> B A
A B B A / B A --> B A B A