Order disjoint list items

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.

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 their 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

Sort disjoint sublist

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

Perl

<lang perl>sub dsort { my ($x, $tmpl) = @_; my (%cx, %ct); # element counts

++$cx{$_} for @$x;

my @out = @$x; my @repl = grep { --$cx{$_} >= 0 && ++$ct{$_} } @$tmpl; my @idx = grep { --$ct{$x->[$_]} >= 0 } 0 .. $#$x;

@out[@idx] = @repl; \@out }

for (split "\n", <<'IN') the cat sat on the mat | mat cat 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 '\|'); say "@$a | @$b -> @{dsort($a, $b)}"; }</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
 |  ->

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'