Order disjoint list items: Difference between revisions

From Rosetta Code
Content added Content deleted
m (→‎{{header|REXX}}: added more comments, streamlined a DO group.)
(→‎{{header|Perl 6}}: add examples requested by ledrug)
Line 189: Line 189:
A B B A
A B B A
A B B A B A
A B B A B A
X X Y Y
A X Y A
---
---
-> $m, $n { say "\n$m ==> $n\n", order-disjoint-list-items($m, $n) }</lang>
-> $m, $n { say "\n$m ==> $n\n", order-disjoint-list-items($m, $n) }</lang>
Line 211: Line 213:


A B B A ==> B A
A B B A ==> B A
B A B A</pre>
B A B A

X X Y ==> Y
X X Y

A X ==> Y A
Y X</pre>


=={{header|Python}}==
=={{header|Python}}==

Revision as of 04:27, 13 May 2014

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.

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

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

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>

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

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                       Y
   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 ==> Y
X X Y

A X ==> Y A
Y X

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

<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.*/ @. = /*placeholder indicates e─o─array*/ @.1 = " the cat sat on the mat | mat cat " /*string.*/ @.2 = " the cat sat on the mat | cat mat " /*string.*/ @.3 = " A B C A B C A B C | C A C A " /*string.*/ @.4 = " A B C A B D A B E | E A D A " /*string.*/ @.5 = " A B | B " /*string.*/ @.6 = " A B | B A " /*string.*/ @.7 = " A B B A | B A " /*string.*/ @.8 = " | " /*string.*/ @.9 = " A | A " /*string.*/ @.10 = " A B | " /*string.*/ @.11 = " A B B A | A B " /*string.*/ @.12 = " A B A B | A B " /*string.*/ @.13 = " A B A B | B A B A " /*string.*/ @.14 = " A B C C B A | A C A C " /*string.*/ @.15 = " A B C C B A | C A C A " /*string.*/ 

                                      /* [↓]  process each input string*/
 do j=1  while  @.j\==;   r.=       /*nullify the replacement string.*/
 parse var @.j m '|' n                /*parse input string into  M & N.*/
 mw=words(m);   do i=mw for mw by -1;   x=word(m,i);  !.i=x;  $.x=i;  end
                                      /* [↑]  build  ! and $  arrays.  */
   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 & replacement*/
   p1=wordpos(_,m);  p2=wordpos(v,m)  /*positions of word & replacement*/
   if p1==0 | p2==0  then iterate     /*if either not found, skip 'em. */
   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.*/
   !.p1=used; !.p2=used;  m=                            /*mark as used.*/
             do i=1  for mw;  m=m !.i; x=word(m,i);  !.i=x;  $.x=i;  end
   end   /*k*/                        /* [↑]  rebuild the ! & $ arrays.*/
 mp=                                  /*the  MP  (M')  string (so far).*/
      do q=1  for mw;   if !.q==used  then mp=mp r.q   /*use original. */
                                      else mp=mp !.q   /*use substitute*/
      end   /*q*/                     /* [↑]  re-build the (output) str*/
                                      /*═══════════════════════════════*/
 say @.j  '───►'  space(mp)           /*display the new text reordered.*/
 end      /*j*/                       /* [↑]  end of processing N words*/
                                      /*stick a fork in it, we're 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

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'
Retrieved from "https://rosettacode.org/wiki/Order_disjoint_list_items?oldid=246627"