Order disjoint list items: Difference between revisions
(Added Kotlin) |
m (→{{header|Wren}}: Minor tidy) |
||
(37 intermediate revisions by 17 users not shown) | |||
Line 1: | Line 1: | ||
{{task}} |
{{task|Sorting Algorithms}} |
||
[[Category:Sorting]] |
|||
{{Sorting Algorithm}} |
|||
Given <code>M</code> as a list of items and another list <code>N</code> of items chosen from <code>M</code>, create <code>M'</code> 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 <code>M</code> but in the order given by their order in <code>N</code>. |
Given <code>M</code> as a list of items and another list <code>N</code> of items chosen from <code>M</code>, create <code>M'</code> 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 <code>M</code> but in the order given by their order in <code>N</code>. |
||
Line 40: | Line 42: | ||
* [[Sort disjoint sublist]] |
* [[Sort disjoint sublist]] |
||
<br><br> |
<br><br> |
||
=={{header|11l}}== |
|||
{{trans|Python}} |
|||
<syntaxhighlight lang="11l">F order_disjoint_list_items(&data, items) |
|||
[Int] itemindices |
|||
L(item) Set(items) |
|||
V itemcount = items.count(item) |
|||
V lastindex = [-1] |
|||
L(i) 0 .< itemcount |
|||
lastindex.append(data.index(item, lastindex.last + 1)) |
|||
itemindices [+]= lastindex[1..] |
|||
itemindices.sort() |
|||
L(index, item) zip(itemindices, items) |
|||
data[index] = item |
|||
F slist(s) |
|||
R Array(s).map(String) |
|||
F tostring(l) |
|||
R ‘'’l.join(‘ ’)‘'’ |
|||
L(data, items) [(‘the cat sat on the mat’.split(‘ ’), (‘mat cat’).split(‘ ’)), |
|||
(‘the cat sat on the mat’.split(‘ ’), (‘cat mat’).split(‘ ’)), |
|||
(slist(‘ABCABCABC’), slist(‘CACA’)), |
|||
(slist(‘ABCABDABE’), slist(‘EADA’)), |
|||
(slist(‘AB’), slist(‘B’)), |
|||
(slist(‘AB’), slist(‘BA’)), |
|||
(slist(‘ABBA’), slist(‘BA’)), |
|||
(slist(‘’), slist(‘’)), |
|||
(slist(‘A’), slist(‘A’)), |
|||
(slist(‘AB’), slist(‘’)), |
|||
(slist(‘ABBA’), slist(‘AB’)), |
|||
(slist(‘ABAB’), slist(‘AB’)), |
|||
(slist(‘ABAB’), slist(‘BABA’)), |
|||
(slist(‘ABCCBA’), slist(‘ACAC’)), |
|||
(slist(‘ABCCBA’), slist(‘CACA’))] |
|||
print(‘Data M: #<24 Order N: #<9’.format(tostring(data), tostring(items)), end' ‘ ’) |
|||
order_disjoint_list_items(&data, items) |
|||
print(‘-> M' #.’.format(tostring(data)))</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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' |
|||
</pre> |
|||
=={{header|Aime}}== |
|||
<syntaxhighlight lang="aime">order(list a, b) |
|||
{ |
|||
integer j; |
|||
record r; |
|||
text s; |
|||
a.ucall(o_, 0, " "); |
|||
o_("| "); |
|||
for (, s in b) { |
|||
r[s] += 1; |
|||
o_(s, " "); |
|||
} |
|||
o_("->"); |
|||
j = -1; |
|||
for (, s in a) { |
|||
if ((r[s] -= 1) < 0) { |
|||
o_(" ", s); |
|||
} else { |
|||
o_(" ", b[j += 1]); |
|||
} |
|||
} |
|||
o_newline(); |
|||
} |
|||
main(void) |
|||
{ |
|||
order(list("the", "cat", "sat", "on", "the", "mat"), list("mat", "cat")); |
|||
order(list("the", "cat", "sat", "on", "the", "mat"), list("cat", "mat")); |
|||
order(list("A", "B", "C", "A", "B", "C", "A", "B", "C"), list("C", "A", "C", "A")); |
|||
order(list("A", "B", "C", "A", "B", "D", "A", "B", "E"), list("E", "A", "D", "A")); |
|||
order(list("A", "B"), list("B")); |
|||
order(list("A", "B"), list("B", "A")); |
|||
order(list("A", "B", "B", "A"), list("B", "A")); |
|||
0; |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>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</pre> |
|||
=={{header|AppleScript}}== |
=={{header|AppleScript}}== |
||
===Functional=== |
|||
{{Trans|JavaScript}} |
{{Trans|JavaScript}} |
||
Accumulate a segmentation of M over a fold/reduce, and zip with N: |
Accumulate a segmentation of M over a fold/reduce, and zip with N: |
||
<syntaxhighlight lang="applescript">---------------------- DISJOINT ORDER -------------------- |
|||
<lang AppleScript>-- disjointOrder :: String -> String -> String |
|||
-- disjointOrder :: String -> String -> String |
|||
on disjointOrder(m, n) |
on disjointOrder(m, n) |
||
set {ms, ns} to map(my |words|, {m, n}) |
set {ms, ns} to map(my |words|, {m, n}) |
||
Line 52: | Line 166: | ||
unwords(flatten(zip(segments(ms, ns), ns & ""))) |
unwords(flatten(zip(segments(ms, ns), ns & ""))) |
||
end disjointOrder |
end disjointOrder |
||
-- segments :: [String] -> [String] -> [String] |
-- segments :: [String] -> [String] -> [String] |
||
on segments(ms, ns) |
on segments(ms, ns) |
||
script segmentation |
script segmentation |
||
on |
on |λ|(a, x) |
||
set wds to |words| of a |
set wds to |words| of a |
||
if wds contains x then |
if wds contains x then |
||
{parts:(parts of a) & |
{parts:(parts of a) & ¬ |
||
[current of a], current:[], |words|:deleteFirst(x, wds)} ¬ |
|||
else |
else |
||
{parts:(parts of a), current:(current of a) & x, |words|:wds} |
{parts:(parts of a), current:(current of a) & x, |words|:wds} |
||
end if |
end if |
||
end |
end |λ| |
||
end script |
end script |
||
Line 73: | Line 190: | ||
--------------------------- TEST ------------------------- |
|||
on run |
on run |
||
script order |
script order |
||
on |
on |λ|(rec) |
||
tell rec |
tell rec |
||
[its m, its n, my disjointOrder(its m, its n)] |
[its m, its n, my disjointOrder(its m, its n)] |
||
end tell |
end tell |
||
end |
end |λ| |
||
end script |
end script |
||
arrowTable(map(order, [¬ |
arrowTable(map(order, [¬ |
||
Line 90: | Line 208: | ||
{m:"A B", n:"B"}, {m:"A B", n:"B A"}, ¬ |
{m:"A B", n:"B"}, {m:"A B", n:"B A"}, ¬ |
||
{m:"A B B A", n:"B A"}])) |
{m:"A B B A", n:"B A"}])) |
||
-- 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 |
||
end run |
end run |
||
------------------------ FORMATTING ---------------------- |
|||
-- Formatting test results |
|||
-- arrowTable :: [[String]] -> String |
-- arrowTable :: [[String]] -> String |
||
Line 111: | Line 227: | ||
script leftAligned |
script leftAligned |
||
script width |
script width |
||
on |
on |λ|(a, b) |
||
(length of a) - (length of b) |
(length of a) - (length of b) |
||
end |
end |λ| |
||
end script |
end script |
||
on |
on |λ|(col) |
||
set widest to length of maximumBy(width, col) |
set widest to length of maximumBy(width, col) |
||
script padding |
script padding |
||
on |
on |λ|(s) |
||
justifyLeft(widest, space, s) |
justifyLeft(widest, space, s) |
||
end |
end |λ| |
||
end script |
end script |
||
map(padding, col) |
map(padding, col) |
||
end |
end |λ| |
||
end script |
end script |
||
script arrows |
script arrows |
||
on |
on |λ|(row) |
||
intercalate(" -> ", row) |
intercalate(" -> ", row) |
||
end |
end |λ| |
||
end script |
end script |
||
Line 138: | Line 254: | ||
map(arrows, ¬ |
map(arrows, ¬ |
||
transpose(map(leftAligned, transpose(rows))))) |
transpose(map(leftAligned, transpose(rows))))) |
||
end arrowTable |
end arrowTable |
||
-- transpose :: [[a]] -> [[a]] |
|||
-------------------- GENERIC FUNCTIONS ------------------- |
|||
on transpose(xss) |
|||
script column |
|||
-- concatMap :: (a -> [b]) -> [a] -> [b] |
|||
on lambda(_, iCol) |
|||
on concatMap(f, xs) |
|||
script row |
|||
script append |
|||
on lambda(xs) |
|||
on |λ|(a, b) |
|||
a & b |
|||
end |λ| |
|||
map(row, xss) |
|||
end lambda |
|||
end script |
end script |
||
foldl(append, {}, map(f, xs)) |
|||
end |
end concatMap |
||
-- deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a] |
|||
on deleteBy(fnEq, x, xs) |
|||
if length of xs > 0 then |
|||
set {h, t} to uncons(xs) |
|||
if |λ|(x, h) of mReturn(fnEq) then |
|||
t |
|||
else |
|||
{h} & deleteBy(fnEq, x, t) |
|||
end if |
|||
else |
|||
{} |
|||
end if |
|||
end deleteBy |
|||
-- deleteFirst :: a -> [a] -> [a] |
|||
on deleteFirst(x, xs) |
|||
script Eq |
|||
on |λ|(a, b) |
|||
a = b |
|||
end |λ| |
|||
end script |
|||
deleteBy(Eq, x, xs) |
|||
end deleteFirst |
|||
-- flatten :: Tree a -> [a] |
|||
on flatten(t) |
|||
if class of t is list then |
|||
concatMap(my flatten, t) |
|||
else |
|||
t |
|||
end if |
|||
end flatten |
|||
-- foldl :: (a -> b -> a) -> a -> [b] -> a |
|||
on foldl(f, startValue, xs) |
|||
tell mReturn(f) |
|||
set v to startValue |
|||
set lng to length of xs |
|||
repeat with i from 1 to lng |
|||
set v to |λ|(v, item i of xs, i, xs) |
|||
end repeat |
|||
return v |
|||
end tell |
|||
end foldl |
|||
-- intercalate :: Text -> [Text] -> Text |
|||
on intercalate(strText, lstText) |
|||
set {dlm, my text item delimiters} to {my text item delimiters, strText} |
|||
set strJoined to lstText as text |
|||
set my text item delimiters to dlm |
|||
return strJoined |
|||
end intercalate |
|||
-- justifyLeft :: Int -> Char -> Text -> Text |
-- justifyLeft :: Int -> Char -> Text -> Text |
||
Line 167: | Line 339: | ||
end justifyLeft |
end justifyLeft |
||
-- maximumBy :: (a -> a -> Ordering) -> [a] -> a |
|||
on maximumBy(f, xs) |
|||
set cmp to mReturn(f) |
|||
script max |
|||
on lambda(a, b) |
|||
if a is missing value or cmp's lambda(a, b) < 0 then |
|||
b |
|||
else |
|||
a |
|||
end if |
|||
end lambda |
|||
end script |
|||
foldl(max, missing value, xs) |
|||
end maximumBy |
|||
-- Egyptian multiplication - progressively doubling a list, appending |
|||
-- stages of doubling to an accumulator where needed for binary |
|||
-- assembly of a target length |
|||
-- replicate :: Int -> a -> [a] |
|||
on replicate(n, a) |
|||
set out to {} |
|||
if n < 1 then return out |
|||
set dbl to {a} |
|||
repeat while (n > 1) |
|||
if (n mod 2) > 0 then set out to out & dbl |
|||
set n to (n div 2) |
|||
set dbl to (dbl & dbl) |
|||
end repeat |
|||
return out & dbl |
|||
end replicate |
|||
-- List functions |
|||
-- map :: (a -> b) -> [a] -> [b] |
-- map :: (a -> b) -> [a] -> [b] |
||
Line 209: | Line 346: | ||
set lst to {} |
set lst to {} |
||
repeat with i from 1 to lng |
repeat with i from 1 to lng |
||
set end of lst to |
set end of lst to |λ|(item i of xs, i, xs) |
||
end repeat |
end repeat |
||
return lst |
return lst |
||
Line 215: | Line 352: | ||
end map |
end map |
||
-- foldl :: (a -> b -> a) -> a -> [b] -> a |
|||
on foldl(f, startValue, xs) |
|||
tell mReturn(f) |
|||
set v to startValue |
|||
set lng to length of xs |
|||
repeat with i from 1 to lng |
|||
set v to lambda(v, item i of xs, i, xs) |
|||
end repeat |
|||
return v |
|||
end tell |
|||
end foldl |
|||
-- |
-- maximumBy :: (a -> a -> Ordering) -> [a] -> a |
||
on |
on maximumBy(f, xs) |
||
set cmp to mReturn(f) |
|||
script pair |
|||
script max |
|||
on lambda(x, i) |
|||
on |λ|(a, b) |
|||
if a is missing value or cmp's |λ|(a, b) < 0 then |
|||
end lambda |
|||
b |
|||
else |
|||
a |
|||
end if |
|||
end |λ| |
|||
end script |
end script |
||
foldl(max, missing value, xs) |
|||
map(pair, items 1 thru minimum([length of xs, length of ys]) of xs) |
|||
end |
end maximumBy |
||
-- flatten :: Tree a -> [a] |
|||
on flatten(t) |
|||
if class of t is list then |
|||
concatMap(my flatten, t) |
|||
else |
|||
t |
|||
end if |
|||
end flatten |
|||
-- |
-- minimum :: [a] -> a |
||
on |
on minimum(xs) |
||
script |
script min |
||
on |
on |λ|(a, x) |
||
a |
if x < a or a is missing value then |
||
x |
|||
else |
|||
a |
|||
end if |
|||
end |λ| |
|||
end script |
end script |
||
foldl( |
foldl(min, missing value, xs) |
||
end |
end minimum |
||
-- Lift 2nd class handler function into 1st class script wrapper |
-- Lift 2nd class handler function into 1st class script wrapper |
||
Line 265: | Line 393: | ||
else |
else |
||
script |
script |
||
property |
property |λ| : f |
||
end script |
end script |
||
end if |
end if |
||
end mReturn |
end mReturn |
||
-- deleteFirst :: a -> [a] -> [a] |
|||
-- Egyptian multiplication - progressively doubling a list, appending |
|||
on deleteFirst(x, xs) |
|||
-- stages of doubling to an accumulator where needed for binary |
|||
script Eq |
|||
-- assembly of a target length |
|||
on lambda(a, b) |
|||
a = b |
|||
-- replicate :: Int -> a -> [a] |
|||
end lambda |
|||
on replicate(n, a) |
|||
end script |
|||
set out to {} |
|||
if n < 1 then return out |
|||
set dbl to {a} |
|||
repeat while (n > 1) |
|||
if (n mod 2) > 0 then set out to out & dbl |
|||
end deleteFirst |
|||
set n to (n div 2) |
|||
set dbl to (dbl & dbl) |
|||
end repeat |
|||
return out & dbl |
|||
end replicate |
|||
-- minimum :: [a] -> a |
|||
-- transpose :: [[a]] -> [[a]] |
|||
on minimum(xs) |
|||
on transpose(xss) |
|||
script min |
|||
script column |
|||
on lambda(a, x) |
|||
on |λ|(_, iCol) |
|||
if x < a or a is missing value then |
|||
script row |
|||
on |λ|(xs) |
|||
item iCol of xs |
|||
end |
end |λ| |
||
end |
end script |
||
map(row, xss) |
|||
end |λ| |
|||
end script |
end script |
||
map(column, item 1 of xss) |
|||
end |
end transpose |
||
-- deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a] |
|||
on deleteBy(fnEq, x, xs) |
|||
if length of xs > 0 then |
|||
set {h, t} to uncons(xs) |
|||
if lambda(x, h) of mReturn(fnEq) then |
|||
t |
|||
else |
|||
{h} & deleteBy(fnEq, x, t) |
|||
end if |
|||
else |
|||
{} |
|||
end if |
|||
end deleteBy |
|||
-- uncons :: [a] -> Maybe (a, [a]) |
-- uncons :: [a] -> Maybe (a, [a]) |
||
Line 318: | Line 444: | ||
end if |
end if |
||
end uncons |
end uncons |
||
-- unwords :: [String] -> String |
-- unwords :: [String] -> String |
||
Line 324: | Line 451: | ||
end unwords |
end unwords |
||
-- intercalate :: Text -> [Text] -> Text |
|||
on intercalate(strText, lstText) |
|||
set {dlm, my text item delimiters} to {my text item delimiters, strText} |
|||
set strJoined to lstText as text |
|||
set my text item delimiters to dlm |
|||
return strJoined |
|||
end intercalate |
|||
-- words :: String -> [String] |
-- words :: String -> [String] |
||
on |words|(s) |
on |words|(s) |
||
words of s |
words of s |
||
end |words| |
end |words| |
||
-- zip :: [a] -> [b] -> [(a, b)] |
|||
on zip(xs, ys) |
|||
script pair |
|||
on |λ|(x, i) |
|||
[x, item i of ys] |
|||
end |λ| |
|||
end script |
|||
map(pair, items 1 thru minimum([length of xs, length of ys]) of xs) |
|||
end zip</syntaxhighlight> |
|||
{{Out}} |
{{Out}} |
||
<pre>the cat sat on the mat -> mat cat -> the mat sat on the cat |
<pre>the cat sat on the mat -> mat cat -> the mat sat on the cat |
||
Line 345: | Line 476: | ||
A B -> B A -> B A |
A B -> B A -> B A |
||
A B B A -> B A -> B A B A </pre> |
A B B A -> B A -> B A B A </pre> |
||
---- |
|||
===Idiomatic=== |
|||
<syntaxhighlight lang="applescript">(* |
|||
The task description talks about items in lists, but the examples are space-delimited substrings of strings. |
|||
The handler here deals with items in lists and leaves it to the calling code to sort out the rest. |
|||
*) |
|||
on odli(m, n) |
|||
-- Use shallow copies of the lists in case the calling process wants the passed originals to remain intact. |
|||
set m to m's items |
|||
set n_source to n's items |
|||
set n_check to n's items |
|||
repeat with i from 1 to (count m) |
|||
set thisItem to item i of m |
|||
if ({thisItem} is in n_check) then |
|||
set item i of m to beginning of n_source |
|||
set n_source to rest of n_source |
|||
if (n_source is {}) then exit repeat |
|||
repeat with j from 1 to (count n_check) |
|||
if (item j of n_check is thisItem) then |
|||
set item j of n_check to beginning of n_check |
|||
set n_check to rest of n_check |
|||
exit repeat |
|||
end if |
|||
end repeat |
|||
end if |
|||
end repeat |
|||
return m |
|||
end odli |
|||
-- Task code: |
|||
set textPairs to {{"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"}} |
|||
set output to {} |
|||
set astid to AppleScript's text item delimiters |
|||
set AppleScript's text item delimiters to space |
|||
repeat with thisPair in textPairs |
|||
set {m, n} to thisPair |
|||
set spiel to "Data M: '" & m & "'\tOrder N: '" & n & "'\t--> '" |
|||
set end of output to spiel & odli(m's text items, n's text items) & "'" |
|||
end repeat |
|||
set AppleScript's text item delimiters to linefeed |
|||
set output to output as text |
|||
set AppleScript's text item delimiters to astid |
|||
return output</syntaxhighlight> |
|||
{{output}} |
|||
<syntaxhighlight lang="applescript">"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'"</syntaxhighlight> |
|||
Or with, say, lists instead of substrings: |
|||
<syntaxhighlight lang="applescript">set listOfLists1 to {{1, 2, 3, 4, 5}, {5, 4, 3, 2, 1}, {"aardvark", "duck-billed platypus", "banana"}} |
|||
set listOfLists2 to {{"aardvark", "duck-billed platypus", "banana"}, {1, 2, 3, 4, 5}} |
|||
return odli(listOfLists1, listOfLists2)</syntaxhighlight> |
|||
{{output}} |
|||
<syntaxhighlight lang="applescript">{{"aardvark", "duck-billed platypus", "banana"}, {5, 4, 3, 2, 1}, {1, 2, 3, 4, 5}}</syntaxhighlight> |
|||
=={{header|Arturo}}== |
|||
{{trans|Nim}} |
|||
<syntaxhighlight lang="rebol">orderDisjoint: function [m,n][ |
|||
ms: split.words m |
|||
ns: split.words n |
|||
indexes: new [] |
|||
loop ns 'item [ |
|||
idx: index ms item |
|||
unless null? idx [ |
|||
'indexes ++ idx |
|||
ms\[idx]: "" |
|||
] |
|||
] |
|||
sort 'indexes |
|||
loop.with:'i indexes 'idx -> |
|||
ms\[idx]: ns\[i] |
|||
return join.with:" " ms |
|||
] |
|||
process: function [a,b][ |
|||
print [a "|" b "->" orderDisjoint a b] |
|||
] |
|||
process "the cat sat on the mat" "mat cat" |
|||
process "the cat sat on the mat" "cat mat" |
|||
process "A B C A B C A B C" "C A C A" |
|||
process "A B C A B D A B E" "E A D A" |
|||
process "A B" "B" |
|||
process "A B" "B A" |
|||
process "A B B A" "B A"</syntaxhighlight> |
|||
{{out}} |
|||
<pre>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</pre> |
|||
=={{header|AutoHotkey}}== |
=={{header|AutoHotkey}}== |
||
{{works with|AutoHotkey 1.1}} |
{{works with|AutoHotkey 1.1}} |
||
< |
<syntaxhighlight lang="autohotkey">Data := [ {M: "the cat sat on the mat", N: "mat cat"} |
||
, {M: "the cat sat on the mat", N: "cat mat"} |
, {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 C A B C", N: "C A C A"} |
||
Line 368: | Line 611: | ||
Result .= (ItemsN[A_LoopField]-- > 0 ? N.Remove(1) : A_LoopField) " " |
Result .= (ItemsN[A_LoopField]-- > 0 ? N.Remove(1) : A_LoopField) " " |
||
return RTrim(Result) |
return RTrim(Result) |
||
}</ |
}</syntaxhighlight> |
||
{{Output}} |
{{Output}} |
||
<pre>the cat sat on the mat :: mat cat -> the mat sat on the cat |
<pre>the cat sat on the mat :: mat cat -> the mat sat on the cat |
||
Line 379: | Line 622: | ||
=={{header|Bracmat}}== |
=={{header|Bracmat}}== |
||
< |
<syntaxhighlight lang="bracmat">( ( odli |
||
= M N NN item A Z R |
= M N NN item A Z R |
||
. !arg:(?M.?N) |
. !arg:(?M.?N) |
||
Line 413: | Line 656: | ||
& out$(\t odli$(!M.!N)) |
& out$(\t odli$(!M.!N)) |
||
) |
) |
||
);</ |
);</syntaxhighlight> |
||
Output: |
Output: |
||
<pre>Data M: the cat sat on the mat Order N: mat cat the mat sat on the cat |
<pre>Data M: the cat sat on the mat Order N: mat cat the mat sat on the cat |
||
Line 422: | Line 665: | ||
Data M: A B Order N: B A B A |
Data M: A B Order N: B A B A |
||
Data M: A B B A Order N: B A B A B A</pre> |
Data M: A B B A Order N: B A B A B A</pre> |
||
=={{header|C++}}== |
|||
<syntaxhighlight lang="cpp"> |
|||
#include <iostream> |
|||
#include <vector> |
|||
#include <algorithm> |
|||
#include <string> |
|||
template <typename T> |
|||
void print(const std::vector<T> v) { |
|||
std::cout << "{ "; |
|||
for (const auto& e : v) { |
|||
std::cout << e << " "; |
|||
} |
|||
std::cout << "}"; |
|||
} |
|||
template <typename T> |
|||
auto orderDisjointArrayItems(std::vector<T> M, std::vector<T> N) { |
|||
std::vector<T*> M_p(std::size(M)); |
|||
for (auto i = 0; i < std::size(M_p); ++i) { |
|||
M_p[i] = &M[i]; |
|||
} |
|||
for (auto e : N) { |
|||
auto i = std::find_if(std::begin(M_p), std::end(M_p), [e](auto c) -> bool { |
|||
if (c != nullptr) { |
|||
if (*c == e) return true; |
|||
} |
|||
return false; |
|||
}); |
|||
if (i != std::end(M_p)) { |
|||
*i = nullptr; |
|||
} |
|||
} |
|||
for (auto i = 0; i < std::size(N); ++i) { |
|||
auto j = std::find_if(std::begin(M_p), std::end(M_p), [](auto c) -> bool { |
|||
return c == nullptr; |
|||
}); |
|||
if (j != std::end(M_p)) { |
|||
*j = &M[std::distance(std::begin(M_p), j)]; |
|||
**j = N[i]; |
|||
} |
|||
} |
|||
return M; |
|||
} |
|||
int main() { |
|||
std::vector<std::vector<std::vector<std::string>>> l = { |
|||
{ { "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" } } |
|||
}; |
|||
for (const auto& e : l) { |
|||
std::cout << "M: "; |
|||
print(e[0]); |
|||
std::cout << ", N: "; |
|||
print(e[1]); |
|||
std::cout << ", M': "; |
|||
auto res = orderDisjointArrayItems<std::string>(e[0], e[1]); |
|||
print(res); |
|||
std::cout << std::endl; |
|||
} |
|||
std::cin.ignore(); |
|||
std::cin.get(); |
|||
return 0; |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>M: { the cat sat on the mat }, N: { mat cat }, M': { the mat sat on the cat } |
|||
M: { the cat sat on the mat }, N: { cat mat }, M': { the cat sat on the mat } |
|||
M: { A B C A B C A B C }, N: { C A C A }, M': { C B A C B A A B C } |
|||
M: { A B C A B D A B E }, N: { E A D A }, M': { E B C A B D A B A } |
|||
M: { A B }, N: { B }, M': { A B } |
|||
M: { A B }, N: { B A }, M': { B A } |
|||
M: { A B B A }, N: { B A }, M': { B A B A }</pre> |
|||
=={{header|Common Lisp}}== |
=={{header|Common Lisp}}== |
||
< |
<syntaxhighlight lang="lisp">(defun order-disjoint (data order) |
||
(let ((order-b (make-hash-table :test 'equal))) |
(let ((order-b (make-hash-table :test 'equal))) |
||
(loop :for n :in order :do (incf (gethash n order-b 0))) |
(loop :for n :in order :do (incf (gethash n order-b 0))) |
||
Line 431: | Line 753: | ||
(decf (gethash m order-b)) |
(decf (gethash m order-b)) |
||
(pop order)) |
(pop order)) |
||
(t m)))))</ |
(t m)))))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>CL-USER> (order-disjoint '(the cat sat on the mat) '(mat cat)) |
<pre>CL-USER> (order-disjoint '(the cat sat on the mat) '(mat cat)) |
||
Line 451: | Line 773: | ||
{{trans|Python}} |
{{trans|Python}} |
||
This version is not efficient. |
This version is not efficient. |
||
< |
<syntaxhighlight lang="d">import std.stdio, std.string, std.algorithm, std.array, std.range, |
||
std.conv; |
std.conv; |
||
Line 501: | Line 823: | ||
orderDisjointArrayItems(a, b)); |
orderDisjointArrayItems(a, b)); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>the cat sat on the mat | mat cat -> the mat sat on the cat |
<pre>the cat sat on the mat | mat cat -> the mat sat on the cat |
||
Line 520: | Line 842: | ||
=={{header|EchoLisp}}== |
=={{header|EchoLisp}}== |
||
< |
<syntaxhighlight lang="scheme"> |
||
(lib 'list) ;; for list-delete |
(lib 'list) ;; for list-delete |
||
Line 552: | Line 874: | ||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 568: | Line 890: | ||
=={{header|Elixir}}== |
=={{header|Elixir}}== |
||
< |
<syntaxhighlight lang="elixir">defmodule Order do |
||
def disjoint(m,n) do |
def disjoint(m,n) do |
||
IO.write "#{Enum.join(m," ")} | #{Enum.join(n," ")} -> " |
IO.write "#{Enum.join(m," ")} | #{Enum.join(n," ")} -> " |
||
Line 606: | Line 928: | ||
|> Enum.each(fn {m,n} -> |
|> Enum.each(fn {m,n} -> |
||
Order.disjoint(String.split(m),String.split(n)) |
Order.disjoint(String.split(m),String.split(n)) |
||
end)</ |
end)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 617: | Line 939: | ||
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 |
||
</pre> |
|||
=={{header|Factor}}== |
|||
This solution is a tad bit whimsical (and a testament to the flexibility of the language that it allows something like this). <code>make-slots</code> replaces elements from ''M'' with <code>_</code> from the <code>fry</code> vocabulary according to the elements in ''N''. For example, |
|||
<syntaxhighlight lang="factor">qw{ the cat sat on the mat } qw{ mat cat } make-slots</syntaxhighlight> |
|||
produces <code>{ "the" _ "sat" "on" "the" _ }</code>. Then, <code>reorder</code> fries elements from ''N'' into the sequence. This is much like a regular fried quotation. |
|||
We must directly call <code>fry</code> on the sequence we've been building, because it's not a literal/static quotation. <code>fry</code> does not call anything directly; it produces a quotation which must be called later. Since we must use <code>call</code> on this runtime-computed value, we must provide a stack effect, but there's a problem. Because there can be any number of inputs to <code>fry</code>, our stack effect must be computed at run time. Luckily for us, we can do that with the <code>effects</code> vocabulary. |
|||
Finally, <code>input<sequence</code> is a smart combinator (a combinator that infers the stack effect of one or more of its inputs) that takes a sequence and a quotation and makes it so that from inside the quotation, you can think of sequence elements as though they were data stack objects. This is precisely what we want so that we can fry them. |
|||
<syntaxhighlight lang="factor">USING: assocs combinators combinators.smart effects formatting |
|||
fry kernel qw sequences ; |
|||
IN: rosetta-code.order-disjoint-list |
|||
: make-slot ( seq elt -- ) |
|||
dupd [ = ] curry find drop swap [ \ _ ] 2dip set-nth ; |
|||
: make-slots ( seq elts -- seq' ) dupd [ make-slot ] with each ; |
|||
: reorder ( seq elts -- seq' ) |
|||
tuck make-slots [ ] like over { "x" } <effect> |
|||
'[ _ fry _ call-effect ] input<sequence ; inline |
|||
: show-reordering ( seq elts -- ) |
|||
2dup [ clone ] dip reorder [ " " join ] tri@ |
|||
"M: %-23s N: %-8s M': %s\n" printf ; inline |
|||
{ |
|||
{ qw{ the cat sat on the mat } qw{ mat cat } } |
|||
{ qw{ the cat sat on the mat } qw{ cat mat } } |
|||
{ qw{ A B C A B C A B C } qw{ C A C A } } |
|||
{ qw{ A B C A B D A B E } qw{ E A D A } } |
|||
{ qw{ A B } qw{ B } } |
|||
{ qw{ A B } qw{ B A } } |
|||
{ qw{ A B B A } qw{ B A } } |
|||
} |
|||
[ show-reordering ] assoc-each</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
M: the cat sat on the mat N: mat cat M': the mat sat on the cat |
|||
M: the cat sat on the mat N: cat mat M': the cat sat on the mat |
|||
M: A B C A B C A B C N: C A C A M': C B A C B A A B C |
|||
M: A B C A B D A B E N: E A D A M': E B C A B D A B A |
|||
M: A B N: B M': A B |
|||
M: A B N: B A M': B A |
|||
M: A B B A N: B A M': B A B A |
|||
</pre> |
</pre> |
||
=={{header|Go}}== |
=={{header|Go}}== |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 676: | Line 1,045: | ||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 688: | Line 1,057: | ||
A B B A → B A » B A B A |
A B B A → B A » B A B A |
||
</pre> |
</pre> |
||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
< |
<syntaxhighlight lang="haskell">import Data.List (mapAccumL, sort) |
||
order |
order |
||
Line 721: | Line 1,091: | ||
, ["A B", "B A"] |
, ["A B", "B A"] |
||
, ["A B B A", "B A"] |
, ["A B B A", "B A"] |
||
]</ |
]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 737: | Line 1,107: | ||
{{Trans|JavaScript}} |
{{Trans|JavaScript}} |
||
<lang |
<syntaxhighlight lang="haskell">import Control.Monad (join) |
||
import Data.Bifunctor (bimap) |
|||
import Prelude hiding (unlines, unwords, words, length) |
|||
import Data.List (delete, transpose) |
import Data.List (delete, transpose) |
||
import Data.Text |
import Data.Text hiding |
||
( concat, |
|||
hiding (concat, zipWith, foldl, transpose, maximum) |
|||
foldl, |
|||
maximum, |
|||
transpose, |
|||
zipWith, |
|||
) |
|||
import Prelude hiding (length, unlines, unwords, words) |
|||
disjointOrder |
disjointOrder :: |
||
Eq a => |
|||
[a] -> |
|||
[a] -> |
|||
disjointOrder m n = concat $ zipWith (++) ms ns |
|||
[a] |
|||
disjointOrder m n = concat $ zipWith (<>) ms ns |
|||
where |
where |
||
ms = segments m n |
ms = segments m n |
||
-- As a list of lists, lengthened by 1 |
|||
ns = ((: []) <$> n) <> [[]] |
|||
segments |
|||
segments :: |
|||
Eq a => |
|||
[a] -> |
|||
[a] -> |
|||
[[a]] |
|||
segments m n = _m <> [_acc] |
|||
where |
where |
||
(_m, _, _acc) = foldl split ([], n, []) m |
(_m, _, _acc) = foldl split ([], n, []) m |
||
split |
split :: |
||
Eq a => |
|||
([[a]], [a], [a]) -> |
|||
a -> |
|||
([[a]], [a], [a]) |
|||
split (ms, ns, acc) x |
split (ms, ns, acc) x |
||
| x `elem` ns = (ms |
| x `elem` ns = (ms <> [acc], delete x ns, []) |
||
| otherwise = (ms, ns, acc |
| otherwise = (ms, ns, acc <> [x]) |
||
--------------------------- TEST ------------------------- |
|||
tests :: [(Text, Text)] |
tests :: [(Text, Text)] |
||
tests = |
tests = |
||
join bimap pack |
|||
[ ("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") |
|||
] |
] |
||
table :: Text -> [[Text]] -> Text |
table :: Text -> [[Text]] -> Text |
||
table delim rows = |
table delim rows = |
||
unlines $ |
unlines $ |
||
intercalate delim |
intercalate delim |
||
transpose |
<$> transpose |
||
((\col -> |
( ( \col -> |
||
let width = (length $ maximum col) |
let width = (length $ maximum col) |
||
in justifyLeft width ' ' <$> col |
in justifyLeft width ' ' <$> col |
||
) |
|||
<$> transpose rows |
|||
) |
|||
main :: IO () |
main :: IO () |
||
main = |
main = |
||
putStr $ |
(putStr . unpack) $ |
||
table (pack " -> ") $ |
|||
unpack $ |
|||
( \(m, n) -> |
|||
[ m, |
|||
(\(m, n) -> [m, n, unwords (disjointOrder (words m) (words n))]) <$> tests</lang> |
|||
n, |
|||
unwords (disjointOrder (words m) (words n)) |
|||
] |
|||
) |
|||
<$> tests</syntaxhighlight> |
|||
{{Out}} |
{{Out}} |
||
<pre>the cat sat on the mat -> mat cat -> the mat sat on the cat |
<pre>the cat sat on the mat -> mat cat -> the mat sat on the cat |
||
Line 806: | Line 1,195: | ||
Works in both languages. Assumes a single blank separates items: |
Works in both languages. Assumes a single blank separates items: |
||
< |
<syntaxhighlight 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","mat cat")) |
||
every write(" -> ",odli("the cat sat on the mat","cat mat")) |
every write(" -> ",odli("the cat sat on the mat","cat mat")) |
||
Line 828: | Line 1,217: | ||
} |
} |
||
return Mp |
return Mp |
||
end</ |
end</syntaxhighlight> |
||
Output: |
Output: |
||
Line 847: | Line 1,236: | ||
Implementation: |
Implementation: |
||
< |
<syntaxhighlight lang="j">disjorder=:3 :0&.;: |
||
: |
: |
||
clusters=. (</. i.@#) x |
clusters=. (</. i.@#) x |
||
Line 855: | Line 1,244: | ||
to=. ;need {.!._ each order{clusters |
to=. ;need {.!._ each order{clusters |
||
(from{x) to} x |
(from{x) to} x |
||
)</ |
)</syntaxhighlight> |
||
Task examples: |
Task examples: |
||
< |
<syntaxhighlight lang="j"> 'the cat sat on the mat' disjorder 'mat cat' |
||
the mat sat on the cat |
the mat sat on the cat |
||
'the cat sat on the mat' disjorder 'cat mat' |
'the cat sat on the mat' disjorder 'cat mat' |
||
Line 872: | Line 1,261: | ||
B A |
B A |
||
'A B B A' disjorder 'B A' |
'A B B A' disjorder 'B A' |
||
B A B A</ |
B A B A</syntaxhighlight> |
||
=={{header|Java}}== |
=={{header|Java}}== |
||
Doesn't handle the case when an item of N is not a member of M. |
Doesn't handle the case when an item of N is not a member of M. |
||
< |
<syntaxhighlight lang="java">import java.util.Arrays; |
||
import java.util.BitSet; |
import java.util.BitSet; |
||
import org.apache.commons.lang3.ArrayUtils; |
import org.apache.commons.lang3.ArrayUtils; |
||
Line 925: | Line 1,314: | ||
return m; |
return m; |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
Output: |
Output: |
||
Line 944: | Line 1,333: | ||
Accumulating a segmentation of M over a fold/reduce, and zipping with N: |
Accumulating a segmentation of M over a fold/reduce, and zipping with N: |
||
< |
<syntaxhighlight lang="javascript">(() => { |
||
"use strict"; |
|||
// ------------ ORDER DISJOINT LIST ITEMS ------------ |
|||
// GENERIC FUNCTIONS |
|||
// disjointOrder :: [String] -> [String] -> [String] |
|||
const disjointOrder = ms => |
|||
ns => zipWith( |
|||
a => b => [...a, b] |
|||
)( |
|||
segments(ms)(ns) |
|||
)( |
|||
ns.concat("") |
|||
) |
|||
.flat(); |
|||
// segments :: [String] -> [String] -> [String] |
|||
const segments = ms => |
|||
ns => { |
|||
const dct = ms.reduce((a, x) => { |
|||
const |
|||
wds = a.words, |
|||
found = wds.indexOf(x) !== -1; |
|||
return { |
|||
parts: [ |
|||
...a.parts, |
|||
...(found ? [a.current] : []) |
|||
], |
|||
current: found ? [] : [...a.current, x], |
|||
words: found ? deleteFirst(x)(wds) : wds |
|||
}; |
|||
}, { |
|||
words: ns, |
|||
parts: [], |
|||
current: [] |
|||
}); |
|||
return [...dct.parts, dct.current]; |
|||
}; |
|||
// ---------------------- TEST ----------------------- |
|||
const main = () => |
|||
transpose(transpose([{ |
|||
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" |
|||
}].map(dct => [ |
|||
dct.M, dct.N, |
|||
unwords( |
|||
disjointOrder( |
|||
words(dct.M) |
|||
)( |
|||
words(dct.N) |
|||
) |
|||
) |
|||
])) |
|||
.map(col => { |
|||
const |
|||
w = maximumBy( |
|||
comparing(x => x.length) |
|||
)(col).length; |
|||
return col.map(justifyLeft(w)(" ")); |
|||
})) |
|||
.map( |
|||
([a, b, c]) => `${a} -> ${b} -> ${c}` |
|||
) |
|||
.join("\n"); |
|||
// ---------------- GENERIC FUNCTIONS ---------------- |
|||
// comparing :: (a -> b) -> (a -> a -> Ordering) |
|||
const comparing = f => |
|||
// The ordering of f(x) and f(y) as a value |
|||
// drawn from {-1, 0, 1}, representing {LT, EQ, GT}. |
|||
x => y => { |
|||
const |
|||
a = f(x), |
|||
b = f(y); |
|||
return a < b ? -1 : (a > b ? 1 : 0); |
|||
}; |
|||
// concatMap :: (a -> [b]) -> [a] -> [b] |
|||
const concatMap = (f, xs) => [].concat.apply([], xs.map(f)); |
|||
// deleteFirst :: a -> [a] -> [a] |
// deleteFirst :: a -> [a] -> [a] |
||
const deleteFirst = |
const deleteFirst = x => { |
||
xs |
const go = xs => Boolean(xs.length) ? ( |
||
x === xs[0] ? ( |
x === xs[0] ? ( |
||
xs.slice(1) |
xs.slice(1) |
||
) : [xs[0]].concat( |
) : [xs[0]].concat(go(xs.slice(1))) |
||
) : []; |
) : []; |
||
return go; |
|||
}; |
|||
const flatten = t => (t instanceof Array ? concatMap(flatten, t) : [t]); |
|||
// unwords :: [String] -> String |
// unwords :: [String] -> String |
||
const unwords = xs => |
const unwords = xs => |
||
// A space-separated string derived |
|||
// from a list of words. |
|||
xs.join(" "); |
|||
// words :: String -> [String] |
// words :: String -> [String] |
||
const words = s => |
const words = s => |
||
// List of space-delimited sub-strings. |
|||
s.split(/\s+/u); |
|||
// zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] |
|||
const zipWith = (f, xs, ys) => { |
|||
const ny = ys.length; |
|||
return (xs.length <= ny ? xs : xs.slice(0, ny)) |
|||
.map((x, i) => f(x, ys[i])); |
|||
}; |
|||
// zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] |
|||
//------------------------------------------------------------------------ |
|||
const zipWith = f => |
|||
// A list constructed by zipping with a |
|||
// ORDER DISJOINT LIST ITEMS |
|||
// custom function, rather than with the |
|||
// default tuple constructor. |
|||
// disjointOrder :: [String] -> [String] -> [String] |
|||
xs => ys => xs.map( |
|||
(x, i) => f(x)(ys[i]) |
|||
).slice( |
|||
0, Math.min(xs.length, ys.length) |
|||
segments(ms, ns), |
|||
ns.concat('') |
|||
) |
|||
); |
); |
||
// ---------------- FORMATTING OUTPUT ---------------- |
|||
// segments :: [String] -> [String] -> [String] |
|||
const segments = (ms, ns) => { |
|||
const dct = ms.reduce((a, x) => { |
|||
const wds = a.words, |
|||
blnFound = wds.indexOf(x) !== -1; |
|||
// justifyLeft :: Int -> Char -> String -> String |
|||
const justifyLeft = n => |
|||
parts: a.parts.concat(blnFound ? [a.current] : []), |
|||
// The string s, followed by enough padding (with |
|||
current: blnFound ? [] : a.current.concat(x), |
|||
// the character c) to reach the string length n. |
|||
words: blnFound ? deleteFirst(x, wds) : wds, |
|||
c => s => n > s.length ? ( |
|||
s.padEnd(n, c) |
|||
) : s; |
|||
parts: [], |
|||
current: [] |
|||
}); |
|||
return dct.parts.concat([dct.current]); |
|||
}; |
|||
// ----------------------------------------------------------------------- |
|||
// FORMATTING TEST OUTPUT |
|||
// transpose :: [[a]] -> [[a]] |
|||
const transpose = xs => |
|||
xs[0].map((_, iCol) => xs.map((row) => row[iCol])); |
|||
// maximumBy :: (a -> a -> Ordering) -> [a] -> a |
// maximumBy :: (a -> a -> Ordering) -> [a] -> a |
||
const maximumBy = |
const maximumBy = f => |
||
xs |
xs => Boolean(xs.length) ? ( |
||
xs.slice(1).reduce( |
|||
(a, x) => 0 < f(x)(a) ? ( |
|||
x |
|||
) : a, |
|||
xs[0] |
|||
) |
|||
) : undefined; |
|||
// 2 or more arguments |
|||
// curry :: Function -> Function |
|||
const curry = (f, ...args) => { |
|||
const intArgs = f.length, |
|||
go = xs => |
|||
xs.length >= intArgs ? ( |
|||
f.apply(null, xs) |
|||
) : function () { |
|||
return go(xs.concat([].slice.apply(arguments))); |
|||
}; |
|||
return go([].slice.call(args, 1)); |
|||
}; |
|||
// |
// transpose :: [[a]] -> [[a]] |
||
const |
const transpose = rows => |
||
// The columns of a matrix of consistent row length, |
|||
n > strText.length ? ( |
|||
// transposed into corresponding rows. |
|||
(strText + replicateS(n, cFiller)) |
|||
Boolean(rows.length) ? rows[0].map( |
|||
) |
(_, i) => rows.flatMap( |
||
v => v[i] |
|||
) |
|||
) : []; |
|||
// replicateS :: Int -> String -> String |
|||
const replicateS = (n, s) => { |
|||
let v = s, |
|||
o = ''; |
|||
if (n < 1) return o; |
|||
while (n > 1) { |
|||
if (n & 1) o = o.concat(v); |
|||
n >>= 1; |
|||
v = v.concat(v); |
|||
} |
|||
return o.concat(v); |
|||
}; |
|||
// MAIN --- |
|||
// ----------------------------------------------------------------------- |
|||
return main(); |
|||
})();</syntaxhighlight> |
|||
// TEST |
|||
return transpose(transpose([{ |
|||
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' |
|||
}].map(dct => [ |
|||
dct.M, dct.N, |
|||
unwords(disjointOrder(words(dct.M), words(dct.N))) |
|||
])) |
|||
.map(col => { |
|||
const width = maximumBy((a, b) => a.length > b.length, col) |
|||
.length; |
|||
return col.map(curry(justifyLeft)(width, ' ')); |
|||
})) |
|||
.map( |
|||
([a, b, c]) => a + ' -> ' + b + ' -> ' + c |
|||
) |
|||
.join('\n'); |
|||
})();</lang> |
|||
{{Out}} |
{{Out}} |
||
Line 1,108: | Line 1,525: | ||
Usage: <tt>M | disjoint_order(N)</tt> |
Usage: <tt>M | disjoint_order(N)</tt> |
||
< |
<syntaxhighlight lang="jq">def disjoint_order(N): |
||
# The helper function, indices, ensures that successive occurrences |
# The helper function, indices, ensures that successive occurrences |
||
# of a particular value in N are matched by successive occurrences |
# of a particular value in N are matched by successive occurrences |
||
Line 1,122: | Line 1,539: | ||
. as $in |
. as $in |
||
| (indices | sort) as $sorted |
| (indices | sort) as $sorted |
||
| reduce range(0; N|length) as $i ($in; .[$sorted[$i]] = N[$i] ) ;</ |
| reduce range(0; N|length) as $i ($in; .[$sorted[$i]] = N[$i] ) ;</syntaxhighlight> |
||
'''Examples''': |
'''Examples''': |
||
Line 1,128: | Line 1,545: | ||
(scrollable) |
(scrollable) |
||
<div style="overflow:scroll; height:400px;"> |
<div style="overflow:scroll; height:400px;"> |
||
< |
<syntaxhighlight lang="jq">["the", "cat", "sat", "on", "the", "mat"] | indices( ["mat", "cat"] ) |
||
#=> ["the","mat","sat","on","the","cat"]</ |
#=> ["the","mat","sat","on","the","cat"]</syntaxhighlight> |
||
< |
<syntaxhighlight lang="jq">["the", "cat", "sat", "on", "the", "mat"] | disjoint_order( ["cat", "mat"] ) |
||
#=> ["the","cat","sat","on","the","mat"]</ |
#=> ["the","cat","sat","on","the","mat"]</syntaxhighlight> |
||
< |
<syntaxhighlight lang="jq">["A", "B", "C", "A", "B", "C", "A", "B", "C"] | disjoint_order( ["C", "A", "C", "A"] ) |
||
#=> ["C","B","A","C","B","A","A","B","C"]</ |
#=> ["C","B","A","C","B","A","A","B","C"]</syntaxhighlight> |
||
< |
<syntaxhighlight lang="jq">["A", "B", "C", "A", "B", "D", "A", "B", "E"] | disjoint_order( ["E", "A", "D", "A"] ) |
||
#=> ["E","B","C","A","B","D","A","B","A"]</ |
#=> ["E","B","C","A","B","D","A","B","A"]</syntaxhighlight> |
||
< |
<syntaxhighlight lang="jq">["A", "B"] | disjoint_order( ["B"] ) |
||
#=> ["A","B"]</ |
#=> ["A","B"]</syntaxhighlight> |
||
< |
<syntaxhighlight lang="jq">["A", "B"] | disjoint_order( ["B", "A"] ) |
||
#=> ["B","A"]</ |
#=> ["B","A"]</syntaxhighlight> |
||
< |
<syntaxhighlight lang="jq">["A", "B", "B", "A"] | disjoint_order( ["B", "A"] ) |
||
#=> ["B","A","B","A"]</ |
#=> ["B","A","B","A"]</syntaxhighlight> |
||
< |
<syntaxhighlight lang="jq">["X", "X", "Y"] | disjoint_order(["X"]) |
||
#=> [X, X, Y]</ |
#=> [X, X, Y]</syntaxhighlight> |
||
</div> |
</div> |
||
Line 1,157: | Line 1,574: | ||
'''Function''' |
'''Function''' |
||
<syntaxhighlight lang="julia"> |
|||
<lang Julia> |
|||
function order_disjoint{T<:AbstractArray}(m::T, n::T) |
function order_disjoint{T<:AbstractArray}(m::T, n::T) |
||
rlen = length(n) |
rlen = length(n) |
||
Line 1,176: | Line 1,593: | ||
return p |
return p |
||
end |
end |
||
</syntaxhighlight> |
|||
</lang> |
|||
'''Main''' |
'''Main''' |
||
<syntaxhighlight lang="julia"> |
|||
<lang Julia> |
|||
testm = {["the", "cat", "sat", "on", "the", "mat"], |
testm = {["the", "cat", "sat", "on", "the", "mat"], |
||
["the", "cat", "sat", "on", "the", "mat"], |
["the", "cat", "sat", "on", "the", "mat"], |
||
Line 1,203: | Line 1,620: | ||
println(" (", m, ", ", n, ") => ", p) |
println(" (", m, ", ", n, ") => ", p) |
||
end |
end |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 1,217: | Line 1,634: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
< |
<syntaxhighlight lang="scala">// version 1.0.6 |
||
const val NULL = "\u0000" |
const val NULL = "\u0000" |
||
Line 1,255: | Line 1,672: | ||
for (i in 0 until m.size) |
for (i in 0 until m.size) |
||
println("${m[i].padEnd(22)} -> ${n[i].padEnd(7)} -> ${orderDisjointList(m[i], n[i])}") |
println("${m[i].padEnd(22)} -> ${n[i].padEnd(7)} -> ${orderDisjointList(m[i], n[i])}") |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,269: | Line 1,686: | ||
=={{header|Lua}}== |
=={{header|Lua}}== |
||
< |
<syntaxhighlight lang="lua">-- Split str on any space characters and return as a table |
||
function split (str) |
function split (str) |
||
local t = {} |
local t = {} |
||
Line 1,310: | Line 1,727: | ||
for _, example in pairs(testCases) do |
for _, example in pairs(testCases) do |
||
print(table.concat(orderList(unpack(example)), " ")) |
print(table.concat(orderList(unpack(example)), " ")) |
||
end</ |
end</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>the mat sat on the cat |
<pre>the mat sat on the cat |
||
Line 1,319: | Line 1,736: | ||
B A |
B A |
||
B A B A</pre> |
B A B A</pre> |
||
=={{header|M2000 Interpreter}}== |
|||
===Simple=== |
|||
<syntaxhighlight lang="m2000 interpreter"> |
|||
Function Checkit$ { |
|||
Document Ret$ |
|||
Flush |
|||
Data "the cat sat on the mat", "mat cat" |
|||
Data "the cat sat on the mat","cat mat"' |
|||
Data "A B C A B C A B C", "C A C A" |
|||
Data "A B C A B D A B E", "E A D A" |
|||
Data "A B", "B" |
|||
Data "A B", "B A" |
|||
Data "A B B A","B A" |
|||
Dim A$() |
|||
while not empty |
|||
read m$, n$ |
|||
A$()=piece$(m$, " ") |
|||
Let w=piece$(n$, " ") |
|||
Let z=A$() |
|||
x=each(w) |
|||
while x |
|||
y=z#pos(array$(x)) |
|||
if y>-1 then a$(y)="" |
|||
end while |
|||
p=0 |
|||
x=each(w) |
|||
while x |
|||
while a$(p)<>"" : p++: end while |
|||
a$(p)=array$(x) |
|||
end while |
|||
ret$=m$+" | "+n$+" -> "+z#str$()+{ |
|||
} |
|||
end while |
|||
=ret$ |
|||
} |
|||
Report Checkit$() |
|||
Clipboard Checkit$() |
|||
</syntaxhighlight> |
|||
===Using a third array, sorted=== |
|||
<syntaxhighlight lang="m2000 interpreter"> |
|||
Function Checkit2$ { |
|||
Document Ret$ |
|||
Flush |
|||
Data "the cat sat on the mat", "mat cat" |
|||
Data "the cat sat on the mat","cat mat"' |
|||
Data "A B C A B C A B C", "C A C A" |
|||
Data "A B C A B D A B E", "E A D A" |
|||
Data "A B", "B" |
|||
Data "A B", "B A" |
|||
Data "A B B A","B A" |
|||
Dim A$() |
|||
while not empty |
|||
read m$, n$ |
|||
A$()=piece$(m$, " ") |
|||
Let w=piece$(n$, " ") |
|||
Let z=A$() |
|||
dim p(len(w)) |
|||
x=each(w) |
|||
p=0 |
|||
while x |
|||
y=z#pos(array$(x)) |
|||
if y>-1 then a$(y)="": p(p)=y : p++ |
|||
end while |
|||
u=p()#Sort() |
|||
x=each(u) |
|||
while x |
|||
a$(array(x))=w#val$(x^) |
|||
end while |
|||
ret$=m$+" | "+n$+" -> "+z#str$()+{ |
|||
} |
|||
end while |
|||
=ret$ |
|||
} |
|||
Report Checkit2$() |
|||
Clipboard Checkit2$() |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|Mathematica}}== |
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
||
< |
<syntaxhighlight lang="mathematica">order[m_, n_] := |
||
ReplacePart[m, |
ReplacePart[m, |
||
MapThread[ |
MapThread[ |
||
Line 1,339: | Line 1,842: | ||
Print[StringRiffle[order[{"A", "B"}, {"B"}]]]; |
Print[StringRiffle[order[{"A", "B"}, {"B"}]]]; |
||
Print[StringRiffle[order[{"A", "B"}, {"B", "A"}]]]; |
Print[StringRiffle[order[{"A", "B"}, {"B", "A"}]]]; |
||
Print[StringRiffle[order[{"A", "B", "B", "A"}, {"B", "A"}]]];</ |
Print[StringRiffle[order[{"A", "B", "B", "A"}, {"B", "A"}]]];</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>the mat sat on the cat |
<pre>the mat sat on the cat |
||
Line 1,348: | Line 1,851: | ||
B A |
B A |
||
B A B A</pre> |
B A B A</pre> |
||
=={{header|Nim}}== |
|||
<syntaxhighlight lang="nim">import algorithm, strutils |
|||
proc orderDisjoint(m, n: string): string = |
|||
# Build the list of items. |
|||
var m = m.splitWhitespace() |
|||
let n = n.splitWhitespace() |
|||
# Find the indexes of items to replace. |
|||
var indexes: seq[int] |
|||
for item in n: |
|||
let idx = m.find(item) |
|||
if idx >= 0: |
|||
indexes.add idx |
|||
m[idx] = "" # Set to empty string for next searches. |
|||
indexes.sort() |
|||
# Do the replacements. |
|||
for i, idx in indexes: |
|||
m[idx] = n[i] |
|||
result = m.join(" ") |
|||
when isMainModule: |
|||
template process(a, b: string) = |
|||
echo a, " | ", b, " → ", orderDisjoint(a, b) |
|||
process("the cat sat on the mat", "mat cat") |
|||
process("the cat sat on the mat", "cat mat") |
|||
process("A B C A B C A B C", "C A C A") |
|||
process("A B C A B D A B E", "E A D A") |
|||
process("A B", "B") |
|||
process("A B", "B A") |
|||
process("A B B A", "B A")</syntaxhighlight> |
|||
{{out}} |
|||
<pre>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</pre> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
< |
<syntaxhighlight lang="perl">sub dsort { |
||
my ($m, $n) = @_; |
my ($m, $n) = @_; |
||
my %h; |
my %h; |
||
Line 1,370: | Line 1,921: | ||
my ($a, $b) = map([split], split '\|'); |
my ($a, $b) = map([split], split '\|'); |
||
print "@$a | @$b -> @{[dsort($a, $b)]}\n"; |
print "@$a | @$b -> @{[dsort($a, $b)]}\n"; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,382: | Line 1,933: | ||
A B B A | B A -> B A B A |
A B B A | B A -> B A B A |
||
</pre> |
</pre> |
||
=={{header|Perl 6}}== |
|||
{{works with|rakudo|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> |
|||
{{out}} |
|||
<pre>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</pre> |
|||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
{{Trans|Julia}} |
{{Trans|Julia}} |
||
Modified to support/skip missing elements |
Modified to support/skip missing elements |
||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
<lang Phix>function order_disjoint(sequence m, sequence n) |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
integer rlen = length(n) |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">order_disjoint</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
|||
sequence rdis = repeat(0,rlen) |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">rlen</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
|||
for i=1 to rlen do |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">rdis</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rlen</span><span style="color: #0000FF;">)</span> |
|||
object e = n[i] |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">rlen</span> <span style="color: #008080;">do</span> |
|||
integer j = find(e,m) |
|||
<span style="color: #004080;">object</span> <span style="color: #000000;">e</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> |
|||
while j!=0 and find(j,rdis) do |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">j</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">e</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)</span> |
|||
j = find(e,m,j+1) |
|||
<span style="color: #008080;">while</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">and</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">j</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rdis</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
end while |
|||
<span style="color: #000000;">j</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">e</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">,</span><span style="color: #000000;">j</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> |
|||
rdis[i] = j |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
end for |
|||
<span style="color: #000000;">rdis</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">j</span> |
|||
rdis = sort(rdis) |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
while rlen and rdis[1]=0 do |
|||
<span style="color: #000000;">rdis</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rdis</span><span style="color: #0000FF;">)</span> |
|||
rdis = rdis[2..$] |
|||
<span style="color: #008080;">while</span> <span style="color: #000000;">rlen</span> <span style="color: #008080;">and</span> <span style="color: #000000;">rdis</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">0</span> <span style="color: #008080;">do</span> |
|||
rlen -= 1 |
|||
<span style="color: #000000;">rdis</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rdis</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">..$]</span> |
|||
end while |
|||
<span style="color: #000000;">rlen</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span> |
|||
for i=1 to rlen do |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
m[rdis[i]]=n[i] |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">rlen</span> <span style="color: #008080;">do</span> |
|||
end for |
|||
<span style="color: #000000;">m</span><span style="color: #0000FF;">[</span><span style="color: #000000;">rdis</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]]=</span><span style="color: #000000;">n</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> |
|||
return join(m) |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
end function |
|||
<span style="color: #008080;">return</span> <span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
sequence tests = {{"the cat sat on the mat","mat cat"}, |
|||
{"the cat sat on the mat","cat mat"}, |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">tests</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #008000;">"the cat sat on the mat"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"mat cat"</span><span style="color: #0000FF;">},</span> |
|||
{"A B C A B C A B C","C A C A"}, |
|||
<span style="color: #0000FF;">{</span><span style="color: #008000;">"the cat sat on the mat"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"cat mat"</span><span style="color: #0000FF;">},</span> |
|||
{"A B C A B D A B E","E A D A"}, |
|||
<span style="color: #0000FF;">{</span><span style="color: #008000;">"A B C A B C A B C"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"C A C A"</span><span style="color: #0000FF;">},</span> |
|||
{"A B","B"}, |
|||
<span style="color: #0000FF;">{</span><span style="color: #008000;">"A B C A B D A B E"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"E A D A"</span><span style="color: #0000FF;">},</span> |
|||
{"A B","B A"}, |
|||
<span style="color: #0000FF;">{</span><span style="color: #008000;">"A B"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"B"</span><span style="color: #0000FF;">},</span> |
|||
{"A B B A","B A"}, |
|||
<span style="color: #0000FF;">{</span><span style="color: #008000;">"A B"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"B A"</span><span style="color: #0000FF;">},</span> |
|||
{"",""}, |
|||
<span style="color: #0000FF;">{</span><span style="color: #008000;">"A B B A"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"B A"</span><span style="color: #0000FF;">},</span> |
|||
{"A","A"}, |
|||
<span style="color: #0000FF;">{</span><span style="color: #008000;">""</span><span style="color: #0000FF;">,</span><span style="color: #008000;">""</span><span style="color: #0000FF;">},</span> |
|||
{"A B",""}, |
|||
<span style="color: #0000FF;">{</span><span style="color: #008000;">"A"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"A"</span><span style="color: #0000FF;">},</span> |
|||
{"A B B A","A B"}, |
|||
<span style="color: #0000FF;">{</span><span style="color: #008000;">"A B"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">""</span><span style="color: #0000FF;">},</span> |
|||
{"A B A B","A B"}, |
|||
<span style="color: #0000FF;">{</span><span style="color: #008000;">"A B B A"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"A B"</span><span style="color: #0000FF;">},</span> |
|||
{"A B A B","B A B A"}, |
|||
<span style="color: #0000FF;">{</span><span style="color: #008000;">"A B A B"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"A B"</span><span style="color: #0000FF;">},</span> |
|||
{"A B C C B A","A C A C"}, |
|||
<span style="color: #0000FF;">{</span><span style="color: #008000;">"A B A B"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"B A B A"</span><span style="color: #0000FF;">},</span> |
|||
{"A B C C B A","C A C A"}, |
|||
<span style="color: #0000FF;">{</span><span style="color: #008000;">"A B C C B A"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"A C A C"</span><span style="color: #0000FF;">},</span> |
|||
{"A X","Y A"}, |
|||
<span style="color: #0000FF;">{</span><span style="color: #008000;">"A B C C B A"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"C A C A"</span><span style="color: #0000FF;">},</span> |
|||
{"A X","Y A X"}, |
|||
<span style="color: #0000FF;">{</span><span style="color: #008000;">"A X"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Y A"</span><span style="color: #0000FF;">},</span> |
|||
{"A X","Y X A"}} |
|||
<span style="color: #0000FF;">{</span><span style="color: #008000;">"A X"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Y A X"</span><span style="color: #0000FF;">},</span> |
|||
<span style="color: #0000FF;">{</span><span style="color: #008000;">"A X"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Y X A"</span><span style="color: #0000FF;">}}</span> |
|||
for i=1 to length(tests) do |
|||
string {m,n} = tests[i] |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
printf(1,"\"%s\",\"%s\" => \"%s\"\n",{m,n,order_disjoint(split(m),split(n))}) |
|||
<span style="color: #004080;">string</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">m</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> |
|||
end for </lang> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\"%s\",\"%s\" => \"%s\"\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">m</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">order_disjoint</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">split</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">split</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">))})</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<!--</syntaxhighlight>--> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,503: | Line 2,008: | ||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |
||
< |
<syntaxhighlight lang="picolisp">(de orderDisjoint (M N) |
||
(for S N |
(for S N |
||
(and (memq S M) (set @ NIL)) ) |
(and (memq S M) (set @ NIL)) ) |
||
(mapcar |
(mapcar |
||
'((S) (or S (pop 'N))) |
'((S) (or S (pop 'N))) |
||
M ) )</ |
M ) )</syntaxhighlight> |
||
Test: |
Test: |
||
< |
<syntaxhighlight lang="picolisp">: (orderDisjoint '(the cat sat on the mat) '(mat cat)) |
||
-> (the mat sat on the cat) |
-> (the mat sat on the cat) |
||
Line 1,529: | Line 2,034: | ||
: (orderDisjoint '(A B B A) '(B A)) |
: (orderDisjoint '(A B B A) '(B A)) |
||
-> (B A B A)</ |
-> (B A B A)</syntaxhighlight> |
||
=={{header|PowerShell}}== |
=={{header|PowerShell}}== |
||
<syntaxhighlight lang="powershell"> |
|||
<lang PowerShell> |
|||
function sublistsort($M, $N) { |
function sublistsort($M, $N) { |
||
$arr = $M.Split(' ') |
$arr = $M.Split(' ') |
||
Line 1,579: | Line 2,084: | ||
sublistsort $M6 $N6 |
sublistsort $M6 $N6 |
||
sublistsort $M7 $N7 |
sublistsort $M7 $N7 |
||
</syntaxhighlight> |
|||
</lang> |
|||
<b>Output:</b> |
<b>Output:</b> |
||
<pre> |
<pre> |
||
Line 1,594: | Line 2,099: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
< |
<syntaxhighlight lang="python">from __future__ import print_function |
||
def order_disjoint_list_items(data, items): |
def order_disjoint_list_items(data, items): |
||
Line 1,630: | Line 2,135: | ||
print('Data M: %-24r Order N: %-9r' % (tostring(data), tostring(items)), end=' ') |
print('Data M: %-24r Order N: %-9r' % (tostring(data), tostring(items)), end=' ') |
||
order_disjoint_list_items(data, items) |
order_disjoint_list_items(data, items) |
||
print("-> M' %r" % tostring(data))</ |
print("-> M' %r" % tostring(data))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,650: | Line 2,155: | ||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
< |
<syntaxhighlight lang="racket">#lang racket |
||
(define disjorder |
(define disjorder |
||
(match-lambda** |
(match-lambda** |
||
Line 1,686: | Line 2,191: | ||
(report-disjorder '(A B A B) '(B A B A)) |
(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) '(A C A C)) |
||
(report-disjorder '(A B C C B A) '(C A C A))</ |
(report-disjorder '(A B C C B A) '(C A C A))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,704: | Line 2,209: | ||
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: (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)</pre> |
Data M: (A B C C B A) Order N: (C A C A) -> (C B A C B A)</pre> |
||
=={{header|Raku}}== |
|||
(formerly Perl 6) |
|||
{{works with|Rakudo|2018.03}} |
|||
<syntaxhighlight lang="raku" line>sub order-disjoint-list-items(\M, \N) { |
|||
my \bag = N.BagHash; |
|||
M.map: { bag{$_}-- ?? N.shift !! $_ } |
|||
} |
|||
# Testing: |
|||
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) }</syntaxhighlight> |
|||
{{out}} |
|||
<pre>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</pre> |
|||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
Note: items in <big>'''N'''</big> needn't be in <big>'''M'''</big>. |
|||
< |
<syntaxhighlight 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*/ |
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. |
@.1 = " the cat sat on the mat | mat cat " /*a string.*/ |
||
@.2 = " the cat sat on the mat | cat mat " /*" " |
@.2 = " the cat sat on the mat | cat mat " /*" " */ |
||
@.3 = " A B C A B C A B C | C A C A " /*" " |
@.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 " /*" " |
@.4 = " A B C A B D A B E | E A D A " /*" " */ |
||
@.5 = " A B | B " /*" " |
@.5 = " A B | B " /*" " */ |
||
@.6 = " A B | B A " /*" " |
@.6 = " A B | B A " /*" " */ |
||
@.7 = " A B B A | B A " /*" " |
@.7 = " A B B A | B A " /*" " */ |
||
@.8 = " | " /*" " |
@.8 = " | " /*" " */ |
||
@.9 = " A | A " /*" " |
@.9 = " A | A " /*" " */ |
||
@.10 = " A B | " /*" " |
@.10 = " A B | " /*" " */ |
||
@.11 = " A B B A | A B " /*" " |
@.11 = " A B B A | A B " /*" " */ |
||
@.12 = " A B A B | A B " /*" " |
@.12 = " A B A B | A B " /*" " */ |
||
@.13 = " A B A B | B A B A " /*" " |
@.13 = " A B A B | B A B A " /*" " */ |
||
@.14 = " A B C C B A | A C A C " /*" " |
@.14 = " A B C C B A | A C A C " /*" " */ |
||
@.15 = " A B C C B A | C A C A " /*" " |
@.15 = " A B C C B A | C A C A " /*" " */ |
||
/* ════════════M═══════════ ════N════ */ |
/* ════════════M═══════════ ════N════ */ |
||
do j=1 while @.j\=='' /* [↓] process each input string (@.).*/ |
do j=1 while @.j\=='' /* [↓] process each input string (@.).*/ |
||
parse var @.j m '|' n |
parse var @.j m '|' n /*parse input string into M and N. */ |
||
#=words(m) |
#= words(m) /*#: number of words in the M list.*/ |
||
do i=# for # by -1 /*process list items in reverse order. */ |
|||
_= word(m, i); !.i= _; $._= i /*construct the !. and $. arrays.*/ |
|||
end /*i*/ |
|||
r.= /*nullify the replacement string [R.] */ |
r.= /*nullify the replacement string [R.] */ |
||
do k=1 by 2 for |
do k=1 by 2 for words(n)%2 /* [↓] process the N array. */ |
||
_=word(n, k); v=word(n, k+1) |
_= word(n, k); v= word(n, k+1) /*get an order word and the replacement*/ |
||
p1=wordpos(_, m); p2=wordpos(v, m) |
p1= wordpos(_, m); p2= wordpos(v, m) /*positions of " " " " */ |
||
if p1==0 | p2==0 then iterate /*if either not found, then skip them. */ |
if p1==0 | p2==0 then iterate /*if either not found, then skip them. */ |
||
if $._>>$.v then do; r.p2=!.p1; r.p1=!.p2; |
if $._>>$.v then do; r.p2= !.p1; r.p1= !.p2; end /*switch the words.*/ |
||
else do; r.p1=!.p1; r.p2=!.p2; |
else do; r.p1= !.p1; r.p2= !.p2; end /*don't switch. */ |
||
!.p1=used; !.p2= |
!.p1= used; !.p2= used /*mark 'em as used.*/ |
||
m= |
m= |
||
do i=1 for #; m=m !.i; _=word(m, i); !.i=_; $._= |
do i=1 for #; m= m !.i; _= word(m, i); !.i= _; $._= i |
||
end /*i*/ |
|||
end /*k*/ /* [↑] rebuild the !. and $. arrays.*/ |
end /*k*/ /* [↑] rebuild the !. and $. arrays.*/ |
||
mp= /*the MP (aka M') string (so far). */ |
mp= /*the MP (aka M') string (so far). */ |
||
do q=1 for #; if !.q==used then mp=mp r.q |
do q=1 for #; if !.q==used then mp= mp r.q /*use the original.*/ |
||
else mp=mp !.q |
else mp= mp !.q /*use substitute. */ |
||
end /*q*/ /* [↑] re─build the (output) string. */ |
end /*q*/ /* [↑] re─build the (output) string. */ |
||
say @.j ' ────► ' space(mp) |
say @.j ' ────► ' space(mp) /*display new re─ordered text ──► term.*/ |
||
end /*j*/ /* [↑] end of processing for N words*/ |
end /*j*/ /* [↑] end of processing for N words*/ |
||
/*stick a fork in it, we're all done. */</ |
/*stick a fork in it, we're all done. */</syntaxhighlight> |
||
{{out|output|text= when using the internal default inputs:}} |
|||
<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 |
||
Line 1,772: | Line 2,328: | ||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
< |
<syntaxhighlight lang="ruby">def order_disjoint(m,n) |
||
print "#{m} | #{n} -> " |
print "#{m} | #{n} -> " |
||
m, n = m.split, n.split |
m, n = m.split, n.split |
||
Line 1,796: | Line 2,352: | ||
['A B' , 'B A' ], |
['A B' , 'B A' ], |
||
['A B B A' , 'B A' ] |
['A B B A' , 'B A' ] |
||
].each {|m,n| order_disjoint(m,n)}</ |
].each {|m,n| order_disjoint(m,n)}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,807: | Line 2,363: | ||
A B B A | B A -> B A B A |
A B B A | B A -> B A B A |
||
</pre> |
</pre> |
||
===sprintf version=== |
|||
<syntaxhighlight lang="ruby">ar = [ |
|||
['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' ] |
|||
] |
|||
res = ar.map do |m,n| |
|||
mm = m.dup |
|||
nn = n.split |
|||
nn.each {|item| mm.sub!(item, "%s")} #sub! only subs the first match |
|||
mm % nn #"the %s sat on the %s" % [mat", "cat"] #does what you hope it does. |
|||
end |
|||
puts res |
|||
</syntaxhighlight> |
|||
=={{header|Scala}}== |
=={{header|Scala}}== |
||
< |
<syntaxhighlight 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 |
if (input.isEmpty || used.size >= using.size) input |
||
else if (using diff used contains input.head) |
else if (using diff used contains input.head) |
||
using(used.size) +: order(input.tail, using, used :+ input.head) |
using(used.size) +: order(input.tail, using, used :+ input.head) |
||
else input.head +: order(input.tail, using, used)</ |
else input.head +: order(input.tail, using, used)</syntaxhighlight> |
||
'''Test:''' |
'''Test:''' |
||
< |
<syntaxhighlight lang="scala">val tests = List( |
||
"the cat sat on the mat" -> "mat cat", |
"the cat sat on the mat" -> "mat cat", |
||
"the cat sat on the mat" -> "cat mat", |
"the cat sat on the mat" -> "cat mat", |
||
Line 1,828: | Line 2,404: | ||
val done = order(input.split(" "), using.split(" ")) |
val done = order(input.split(" "), using.split(" ")) |
||
println(f"""Data M: $input%-24s Order N: $using%-9s -> Result M': ${done mkString " "}""") |
println(f"""Data M: $input%-24s Order N: $using%-9s -> Result M': ${done mkString " "}""") |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Data M: the cat sat on the mat Order N: mat cat -> Result M': the mat sat on the cat |
<pre>Data M: the cat sat on the mat Order N: mat cat -> Result M': the mat sat on the cat |
||
Line 1,840: | Line 2,416: | ||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
{{trans|Perl}} |
{{trans|Perl}} |
||
< |
<syntaxhighlight lang="ruby">func dsort(m, n) { |
||
var h = Hash() |
var h = Hash() |
||
n.each {|item| h{item} := 0 ++ } |
n.each {|item| h{item} := 0 ++ } |
||
Line 1,856: | Line 2,432: | ||
EOT |
EOT |
||
var (a, b) = line.split('|').map{.words}... |
var (a, b) = line.split('|').map{.words}... |
||
say "#{a. |
say "#{a.join(' ')} | #{b.join(' ')} -> #{dsort(a.clone, b.clone).join(' ')}" |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,868: | Line 2,444: | ||
A B B A | B A -> B A B A |
A B B A | B A -> B A B A |
||
</pre> |
</pre> |
||
=={{header|Swift}}== |
|||
<syntaxhighlight lang="swift">func disjointOrder<T: Hashable>(m: [T], n: [T]) -> [T] { |
|||
let replaceCounts = n.reduce(into: [T: Int](), { $0[$1, default: 0] += 1 }) |
|||
let reduced = m.reduce(into: ([T](), n, replaceCounts), {cur, el in |
|||
cur.0.append(cur.2[el, default: 0] > 0 ? cur.1.removeFirst() : el) |
|||
cur.2[el]? -= 1 |
|||
}) |
|||
return reduced.0 |
|||
} |
|||
print(disjointOrder(m: ["the", "cat", "sat", "on", "the", "mat"], n: ["mat", "cat"])) |
|||
print(disjointOrder(m: ["the", "cat", "sat", "on", "the", "mat"], n: ["cat", "mat"])) |
|||
print(disjointOrder(m: ["A", "B", "C", "A", "B", "C", "A", "B", "C"], n: ["C", "A", "C", "A"])) |
|||
print(disjointOrder(m: ["A", "B", "C", "A", "B", "D", "A", "B", "E"], n: ["E", "A", "D", "A"])) |
|||
print(disjointOrder(m: ["A", "B"], n: ["B"])) |
|||
print(disjointOrder(m: ["A", "B"], n: ["B", "A"])) |
|||
print(disjointOrder(m: ["A", "B", "B", "A"], n: ["B", "A"]))</syntaxhighlight> |
|||
{{out}} |
|||
<pre>["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", "A"] |
|||
["A", "B"] |
|||
["B", "A"] |
|||
["B", "A", "B", "A"]</pre> |
|||
=={{header|Tcl}}== |
=={{header|Tcl}}== |
||
This is a simple version that assumes that ''all'' items in the order list are present in the list to be arranged: |
This is a simple version that assumes that ''all'' items in the order list are present in the list to be arranged: |
||
< |
<syntaxhighlight lang="tcl">proc orderDisjoint {theList theOrderList} { |
||
foreach item $theOrderList {incr n($item)} |
foreach item $theOrderList {incr n($item)} |
||
set is {} |
set is {} |
||
Line 1,883: | Line 2,488: | ||
foreach item $theOrderList i $is {lset theList $i $item} |
foreach item $theOrderList i $is {lset theList $i $item} |
||
return $theList |
return $theList |
||
}</ |
}</syntaxhighlight> |
||
This is a more sophisticated version that handles items in the order list not being present in the list to be arranged: |
This is a more sophisticated version that handles items in the order list not being present in the list to be arranged: |
||
< |
<syntaxhighlight lang="tcl">proc orderDisjoint {theList theOrderList} { |
||
foreach item $theOrderList {incr n($item)} |
foreach item $theOrderList {incr n($item)} |
||
set is - |
set is - |
||
Line 1,902: | Line 2,507: | ||
} |
} |
||
return $theList |
return $theList |
||
}</ |
}</syntaxhighlight> |
||
Demonstration code (produces the same output from both implementations): |
Demonstration code (produces the same output from both implementations): |
||
< |
<syntaxhighlight lang="tcl">foreach {items order} { |
||
"the cat sat on the mat" "mat cat" |
"the cat sat on the mat" "mat cat" |
||
"the cat sat on the mat" "cat mat" |
"the cat sat on the mat" "cat mat" |
||
Line 1,914: | Line 2,519: | ||
} { |
} { |
||
puts "'$items' with '$order' => '[orderDisjoint $items $order]'" |
puts "'$items' with '$order' => '[orderDisjoint $items $order]'" |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,924: | Line 2,529: | ||
'A B' with 'B A' => 'B A' |
'A B' with 'B A' => 'B A' |
||
'A B B A' with 'B A' => 'B A B A' |
'A B B A' with 'B A' => 'B A B A' |
||
</pre> |
|||
=={{header|Wren}}== |
|||
{{trans|Kotlin}} |
|||
{{libheader|Wren-fmt}} |
|||
<syntaxhighlight lang="wren">import "./fmt" for Fmt |
|||
var NULL = "\0" |
|||
var orderDisjointList = Fn.new { |m, n| |
|||
var nList = n.split(" ") |
|||
// first replace the first occurrence of items of 'n' in 'm' with the NULL character |
|||
// which we can safely assume won't occur in 'm' naturally |
|||
for (item in nList) { |
|||
var ix = m.indexOf(item) |
|||
if (ix >= 0) { |
|||
var le = item.count |
|||
m = m[0...ix] + NULL + m[ix + le..-1] |
|||
} |
|||
} |
|||
// now successively replace the NULLs with items from nList |
|||
var mList = m.split(NULL) |
|||
var sb = "" |
|||
for (i in 0...nList.count) sb = sb + mList[i] + nList[i] |
|||
return sb + mList[-1] |
|||
} |
|||
var ma = [ |
|||
"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" |
|||
] |
|||
var na = [ |
|||
"mat cat", |
|||
"cat mat", |
|||
"C A C A", |
|||
"E A D A", |
|||
"B", |
|||
"B A", |
|||
"B A" |
|||
] |
|||
for (i in 0...ma.count) { |
|||
Fmt.print("$-22s -> $-7s -> $s", ma[i], na[i], orderDisjointList.call(ma[i], na[i])) |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
</pre> |
||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
< |
<syntaxhighlight lang="zkl">fcn disOrder(sm,sn){ |
||
M:=sm.split(" "); |
M:=sm.split(" "); |
||
N:=sn.split(" "); nc:=Walker.cycle(Utils.Helpers.listUnique(N)); |
N:=sn.split(" "); nc:=Walker.cycle(Utils.Helpers.listUnique(N)); |
||
Line 1,936: | Line 2,601: | ||
else { nc.next(); w } // exhausted |
else { nc.next(); w } // exhausted |
||
}, String.fp(" ") )[1,*] // remove leading blank |
}, String.fp(" ") )[1,*] // remove leading blank |
||
}</ |
}</syntaxhighlight> |
||
A dictionary is used to hold count of the words in N, which is decremented as the words are used up. |
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. |
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()). |
It is assumed that there are no leading/trailing/consecutive spaces (easy to cover with a .filter()). |
||
< |
<syntaxhighlight lang="zkl">sets:=T(T("the cat sat on the mat","mat cat"), |
||
T("the cat sat on the mat","cat mat"), |
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 C A B C","C A C A"), |
||
Line 1,947: | Line 2,612: | ||
foreach m,n in (sets){ |
foreach m,n in (sets){ |
||
m.println(" / ",n," --> ",disOrder(m,n)); |
m.println(" / ",n," --> ",disOrder(m,n)); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
Latest revision as of 09:55, 9 January 2024
You are encouraged to solve this task according to the task description, using any language you may know.
Sorting Algorithm
This is a sorting algorithm. It may be applied to a set of data in order to sort it.
For comparing various sorts, see compare sorts.
For other sorting algorithms, see sorting algorithms, or:
Heap sort | Merge sort | Patience sort | Quick sort
O(n log2n) sorts
Shell Sort
O(n2) sorts
Bubble sort |
Cocktail sort |
Cocktail sort with shifting bounds |
Comb sort |
Cycle sort |
Gnome sort |
Insertion sort |
Selection sort |
Strand sort
other sorts
Bead sort |
Bogo sort |
Common sorted list |
Composite structures sort |
Custom comparator sort |
Counting sort |
Disjoint sublist sort |
External sort |
Jort sort |
Lexicographical sort |
Natural sorting |
Order by pair comparisons |
Order disjoint list items |
Order two numerical lists |
Object identifier (OID) sort |
Pancake sort |
Quickselect |
Permutation sort |
Radix sort |
Ranking methods |
Remove duplicate elements |
Sleep sort |
Stooge sort |
[Sort letters of a string] |
Three variable sort |
Topological sort |
Tree sort
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
11l
F order_disjoint_list_items(&data, items)
[Int] itemindices
L(item) Set(items)
V itemcount = items.count(item)
V lastindex = [-1]
L(i) 0 .< itemcount
lastindex.append(data.index(item, lastindex.last + 1))
itemindices [+]= lastindex[1..]
itemindices.sort()
L(index, item) zip(itemindices, items)
data[index] = item
F slist(s)
R Array(s).map(String)
F tostring(l)
R ‘'’l.join(‘ ’)‘'’
L(data, items) [(‘the cat sat on the mat’.split(‘ ’), (‘mat cat’).split(‘ ’)),
(‘the cat sat on the mat’.split(‘ ’), (‘cat mat’).split(‘ ’)),
(slist(‘ABCABCABC’), slist(‘CACA’)),
(slist(‘ABCABDABE’), slist(‘EADA’)),
(slist(‘AB’), slist(‘B’)),
(slist(‘AB’), slist(‘BA’)),
(slist(‘ABBA’), slist(‘BA’)),
(slist(‘’), slist(‘’)),
(slist(‘A’), slist(‘A’)),
(slist(‘AB’), slist(‘’)),
(slist(‘ABBA’), slist(‘AB’)),
(slist(‘ABAB’), slist(‘AB’)),
(slist(‘ABAB’), slist(‘BABA’)),
(slist(‘ABCCBA’), slist(‘ACAC’)),
(slist(‘ABCCBA’), slist(‘CACA’))]
print(‘Data M: #<24 Order N: #<9’.format(tostring(data), tostring(items)), end' ‘ ’)
order_disjoint_list_items(&data, items)
print(‘-> M' #.’.format(tostring(data)))
- 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'
Aime
order(list a, b)
{
integer j;
record r;
text s;
a.ucall(o_, 0, " ");
o_("| ");
for (, s in b) {
r[s] += 1;
o_(s, " ");
}
o_("->");
j = -1;
for (, s in a) {
if ((r[s] -= 1) < 0) {
o_(" ", s);
} else {
o_(" ", b[j += 1]);
}
}
o_newline();
}
main(void)
{
order(list("the", "cat", "sat", "on", "the", "mat"), list("mat", "cat"));
order(list("the", "cat", "sat", "on", "the", "mat"), list("cat", "mat"));
order(list("A", "B", "C", "A", "B", "C", "A", "B", "C"), list("C", "A", "C", "A"));
order(list("A", "B", "C", "A", "B", "D", "A", "B", "E"), list("E", "A", "D", "A"));
order(list("A", "B"), list("B"));
order(list("A", "B"), list("B", "A"));
order(list("A", "B", "B", "A"), list("B", "A"));
0;
}
- 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
AppleScript
Functional
Accumulate a segmentation of M over a fold/reduce, and zip with N:
---------------------- DISJOINT ORDER --------------------
-- disjointOrder :: String -> String -> String
on disjointOrder(m, n)
set {ms, ns} to map(my |words|, {m, n})
unwords(flatten(zip(segments(ms, ns), ns & "")))
end disjointOrder
-- segments :: [String] -> [String] -> [String]
on segments(ms, ns)
script segmentation
on |λ|(a, x)
set wds to |words| of a
if wds contains x then
{parts:(parts of a) & ¬
[current of a], current:[], |words|:deleteFirst(x, wds)} ¬
else
{parts:(parts of a), current:(current of a) & x, |words|:wds}
end if
end |λ|
end script
tell foldl(segmentation, {|words|:ns, parts:[], current:[]}, ms)
(parts of it) & [current of it]
end tell
end segments
--------------------------- TEST -------------------------
on run
script order
on |λ|(rec)
tell rec
[its m, its n, my disjointOrder(its m, its n)]
end tell
end |λ|
end script
arrowTable(map(order, [¬
{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"}]))
-- 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
end run
------------------------ FORMATTING ----------------------
-- arrowTable :: [[String]] -> String
on arrowTable(rows)
script leftAligned
script width
on |λ|(a, b)
(length of a) - (length of b)
end |λ|
end script
on |λ|(col)
set widest to length of maximumBy(width, col)
script padding
on |λ|(s)
justifyLeft(widest, space, s)
end |λ|
end script
map(padding, col)
end |λ|
end script
script arrows
on |λ|(row)
intercalate(" -> ", row)
end |λ|
end script
intercalate(linefeed, ¬
map(arrows, ¬
transpose(map(leftAligned, transpose(rows)))))
end arrowTable
-------------------- GENERIC FUNCTIONS -------------------
-- concatMap :: (a -> [b]) -> [a] -> [b]
on concatMap(f, xs)
script append
on |λ|(a, b)
a & b
end |λ|
end script
foldl(append, {}, map(f, xs))
end concatMap
-- deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a]
on deleteBy(fnEq, x, xs)
if length of xs > 0 then
set {h, t} to uncons(xs)
if |λ|(x, h) of mReturn(fnEq) then
t
else
{h} & deleteBy(fnEq, x, t)
end if
else
{}
end if
end deleteBy
-- deleteFirst :: a -> [a] -> [a]
on deleteFirst(x, xs)
script Eq
on |λ|(a, b)
a = b
end |λ|
end script
deleteBy(Eq, x, xs)
end deleteFirst
-- flatten :: Tree a -> [a]
on flatten(t)
if class of t is list then
concatMap(my flatten, t)
else
t
end if
end flatten
-- foldl :: (a -> b -> a) -> a -> [b] -> a
on foldl(f, startValue, xs)
tell mReturn(f)
set v to startValue
set lng to length of xs
repeat with i from 1 to lng
set v to |λ|(v, item i of xs, i, xs)
end repeat
return v
end tell
end foldl
-- intercalate :: Text -> [Text] -> Text
on intercalate(strText, lstText)
set {dlm, my text item delimiters} to {my text item delimiters, strText}
set strJoined to lstText as text
set my text item delimiters to dlm
return strJoined
end intercalate
-- justifyLeft :: Int -> Char -> Text -> Text
on justifyLeft(n, cFiller, strText)
if n > length of strText then
text 1 thru n of (strText & replicate(n, cFiller))
else
strText
end if
end justifyLeft
-- map :: (a -> b) -> [a] -> [b]
on map(f, xs)
tell mReturn(f)
set lng to length of xs
set lst to {}
repeat with i from 1 to lng
set end of lst to |λ|(item i of xs, i, xs)
end repeat
return lst
end tell
end map
-- maximumBy :: (a -> a -> Ordering) -> [a] -> a
on maximumBy(f, xs)
set cmp to mReturn(f)
script max
on |λ|(a, b)
if a is missing value or cmp's |λ|(a, b) < 0 then
b
else
a
end if
end |λ|
end script
foldl(max, missing value, xs)
end maximumBy
-- minimum :: [a] -> a
on minimum(xs)
script min
on |λ|(a, x)
if x < a or a is missing value then
x
else
a
end if
end |λ|
end script
foldl(min, missing value, xs)
end minimum
-- Lift 2nd class handler function into 1st class script wrapper
-- mReturn :: Handler -> Script
on mReturn(f)
if class of f is script then
f
else
script
property |λ| : f
end script
end if
end mReturn
-- Egyptian multiplication - progressively doubling a list, appending
-- stages of doubling to an accumulator where needed for binary
-- assembly of a target length
-- replicate :: Int -> a -> [a]
on replicate(n, a)
set out to {}
if n < 1 then return out
set dbl to {a}
repeat while (n > 1)
if (n mod 2) > 0 then set out to out & dbl
set n to (n div 2)
set dbl to (dbl & dbl)
end repeat
return out & dbl
end replicate
-- transpose :: [[a]] -> [[a]]
on transpose(xss)
script column
on |λ|(_, iCol)
script row
on |λ|(xs)
item iCol of xs
end |λ|
end script
map(row, xss)
end |λ|
end script
map(column, item 1 of xss)
end transpose
-- uncons :: [a] -> Maybe (a, [a])
on uncons(xs)
if length of xs > 0 then
{item 1 of xs, rest of xs}
else
missing value
end if
end uncons
-- unwords :: [String] -> String
on unwords(xs)
intercalate(space, xs)
end unwords
-- words :: String -> [String]
on |words|(s)
words of s
end |words|
-- zip :: [a] -> [b] -> [(a, b)]
on zip(xs, ys)
script pair
on |λ|(x, i)
[x, item i of ys]
end |λ|
end script
map(pair, items 1 thru minimum([length of xs, length of ys]) of xs)
end zip
- 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
Idiomatic
(*
The task description talks about items in lists, but the examples are space-delimited substrings of strings.
The handler here deals with items in lists and leaves it to the calling code to sort out the rest.
*)
on odli(m, n)
-- Use shallow copies of the lists in case the calling process wants the passed originals to remain intact.
set m to m's items
set n_source to n's items
set n_check to n's items
repeat with i from 1 to (count m)
set thisItem to item i of m
if ({thisItem} is in n_check) then
set item i of m to beginning of n_source
set n_source to rest of n_source
if (n_source is {}) then exit repeat
repeat with j from 1 to (count n_check)
if (item j of n_check is thisItem) then
set item j of n_check to beginning of n_check
set n_check to rest of n_check
exit repeat
end if
end repeat
end if
end repeat
return m
end odli
-- Task code:
set textPairs to {{"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"}}
set output to {}
set astid to AppleScript's text item delimiters
set AppleScript's text item delimiters to space
repeat with thisPair in textPairs
set {m, n} to thisPair
set spiel to "Data M: '" & m & "'\tOrder N: '" & n & "'\t--> '"
set end of output to spiel & odli(m's text items, n's text items) & "'"
end repeat
set AppleScript's text item delimiters to linefeed
set output to output as text
set AppleScript's text item delimiters to astid
return output
- 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'"
Or with, say, lists instead of substrings:
set listOfLists1 to {{1, 2, 3, 4, 5}, {5, 4, 3, 2, 1}, {"aardvark", "duck-billed platypus", "banana"}}
set listOfLists2 to {{"aardvark", "duck-billed platypus", "banana"}, {1, 2, 3, 4, 5}}
return odli(listOfLists1, listOfLists2)
- Output:
{{"aardvark", "duck-billed platypus", "banana"}, {5, 4, 3, 2, 1}, {1, 2, 3, 4, 5}}
Arturo
orderDisjoint: function [m,n][
ms: split.words m
ns: split.words n
indexes: new []
loop ns 'item [
idx: index ms item
unless null? idx [
'indexes ++ idx
ms\[idx]: ""
]
]
sort 'indexes
loop.with:'i indexes 'idx ->
ms\[idx]: ns\[i]
return join.with:" " ms
]
process: function [a,b][
print [a "|" b "->" orderDisjoint a b]
]
process "the cat sat on the mat" "mat cat"
process "the cat sat on the mat" "cat mat"
process "A B C A B C A B C" "C A C A"
process "A B C A B D A B E" "E A D A"
process "A B" "B"
process "A B" "B A"
process "A B B A" "B A"
- 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
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)
}
- 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
( ( 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))
)
);
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
C++
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
template <typename T>
void print(const std::vector<T> v) {
std::cout << "{ ";
for (const auto& e : v) {
std::cout << e << " ";
}
std::cout << "}";
}
template <typename T>
auto orderDisjointArrayItems(std::vector<T> M, std::vector<T> N) {
std::vector<T*> M_p(std::size(M));
for (auto i = 0; i < std::size(M_p); ++i) {
M_p[i] = &M[i];
}
for (auto e : N) {
auto i = std::find_if(std::begin(M_p), std::end(M_p), [e](auto c) -> bool {
if (c != nullptr) {
if (*c == e) return true;
}
return false;
});
if (i != std::end(M_p)) {
*i = nullptr;
}
}
for (auto i = 0; i < std::size(N); ++i) {
auto j = std::find_if(std::begin(M_p), std::end(M_p), [](auto c) -> bool {
return c == nullptr;
});
if (j != std::end(M_p)) {
*j = &M[std::distance(std::begin(M_p), j)];
**j = N[i];
}
}
return M;
}
int main() {
std::vector<std::vector<std::vector<std::string>>> l = {
{ { "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" } }
};
for (const auto& e : l) {
std::cout << "M: ";
print(e[0]);
std::cout << ", N: ";
print(e[1]);
std::cout << ", M': ";
auto res = orderDisjointArrayItems<std::string>(e[0], e[1]);
print(res);
std::cout << std::endl;
}
std::cin.ignore();
std::cin.get();
return 0;
}
- Output:
M: { the cat sat on the mat }, N: { mat cat }, M': { the mat sat on the cat } M: { the cat sat on the mat }, N: { cat mat }, M': { the cat sat on the mat } M: { A B C A B C A B C }, N: { C A C A }, M': { C B A C B A A B C } M: { A B C A B D A B E }, N: { E A D A }, M': { E B C A B D A B A } M: { A B }, N: { B }, M': { A B } M: { A B }, N: { B A }, M': { B A } M: { A B B A }, N: { B A }, M': { B A B A }
Common Lisp
(defun order-disjoint (data order)
(let ((order-b (make-hash-table :test 'equal)))
(loop :for n :in order :do (incf (gethash n order-b 0)))
(loop :for m :in data :collect
(cond ((< 0 (gethash m order-b 0))
(decf (gethash m order-b))
(pop order))
(t m)))))
- Output:
CL-USER> (order-disjoint '(the cat sat on the mat) '(mat cat)) (THE MAT SAT ON THE CAT) CL-USER> (order-disjoint '(the cat sat on the mat) '(cat mat)) (THE CAT SAT ON THE MAT) CL-USER> (order-disjoint '(a b c a b c a b c) '(c a c a)) (C B A C B A A B C) CL-USER> (order-disjoint '(a b c a b d a b e) '(e a d a)) (E B C A B D A B A) CL-USER> (order-disjoint '(a b) '(b)) (A B) CL-USER> (order-disjoint '(a b) '(b a)) (B A) CL-USER> (order-disjoint '(a b b a) '(b a)) (B A B A)
D
This version is not efficient.
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));
}
}
- 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
EchoLisp
(lib 'list) ;; for list-delete
(define dataM
'((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)))
(define orderM
'((mat cat)
(cat mat)
(C A C A)
(E A D A)
(B)
(B A)
(B A)))
(define (order-disjoint M N)
(define R (append N null)) ;; tmp copy of N : delete w when used
(for/list [(w M)]
(if
(not (member w R)) w ;; output as is
(begin0
(first N) ;; replacer
(set! N (rest N))
(set! R (list-delete R w))))))
- Output:
(for [(m dataM) (n orderM)] (writeln 'M m 'Order n '→ (order-disjoint m n))) M (the cat sat on the mat) Order (mat cat) → (the mat sat on the cat) M (the cat sat on the mat) Order (cat mat) → (the cat sat on the mat) M (A B C A B C A B C) Order (C A C A) → (C B A C B A A B C) M (A B C A B D A B E) Order (E A D A) → (E B C A B D A B A) M (A B) Order (B) → (A B) M (A B) Order (B A) → (B A) M (A B B A) Order (B A) → (B A B A)
Elixir
defmodule Order do
def disjoint(m,n) do
IO.write "#{Enum.join(m," ")} | #{Enum.join(n," ")} -> "
Enum.chunk(n,2)
|> Enum.reduce({m,0}, fn [x,y],{m,from} ->
md = Enum.drop(m, from)
if x > y and x in md and y in md do
if Enum.find_index(md,&(&1==x)) > Enum.find_index(md,&(&1==y)) do
new_from = max(Enum.find_index(m,&(&1==x)), Enum.find_index(m,&(&1==y))) + 1
m = swap(m,from,x,y)
from = new_from
end
end
{m,from}
end)
|> elem(0)
|> Enum.join(" ")
|> IO.puts
end
defp swap(m,from,x,y) do
ix = Enum.find_index(m,&(&1==x)) + from
iy = Enum.find_index(m,&(&1==y)) + from
vx = Enum.at(m,ix)
vy = Enum.at(m,iy)
m |> List.replace_at(ix,vy) |> List.replace_at(iy,vx)
end
end
[ {"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"} ]
|> Enum.each(fn {m,n} ->
Order.disjoint(String.split(m),String.split(n))
end)
- 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
Factor
This solution is a tad bit whimsical (and a testament to the flexibility of the language that it allows something like this). make-slots
replaces elements from M with _
from the fry
vocabulary according to the elements in N. For example,
qw{ the cat sat on the mat } qw{ mat cat } make-slots
produces { "the" _ "sat" "on" "the" _ }
. Then, reorder
fries elements from N into the sequence. This is much like a regular fried quotation.
We must directly call fry
on the sequence we've been building, because it's not a literal/static quotation. fry
does not call anything directly; it produces a quotation which must be called later. Since we must use call
on this runtime-computed value, we must provide a stack effect, but there's a problem. Because there can be any number of inputs to fry
, our stack effect must be computed at run time. Luckily for us, we can do that with the effects
vocabulary.
Finally, input<sequence
is a smart combinator (a combinator that infers the stack effect of one or more of its inputs) that takes a sequence and a quotation and makes it so that from inside the quotation, you can think of sequence elements as though they were data stack objects. This is precisely what we want so that we can fry them.
USING: assocs combinators combinators.smart effects formatting
fry kernel qw sequences ;
IN: rosetta-code.order-disjoint-list
: make-slot ( seq elt -- )
dupd [ = ] curry find drop swap [ \ _ ] 2dip set-nth ;
: make-slots ( seq elts -- seq' ) dupd [ make-slot ] with each ;
: reorder ( seq elts -- seq' )
tuck make-slots [ ] like over { "x" } <effect>
'[ _ fry _ call-effect ] input<sequence ; inline
: show-reordering ( seq elts -- )
2dup [ clone ] dip reorder [ " " join ] tri@
"M: %-23s N: %-8s M': %s\n" printf ; inline
{
{ qw{ the cat sat on the mat } qw{ mat cat } }
{ qw{ the cat sat on the mat } qw{ cat mat } }
{ qw{ A B C A B C A B C } qw{ C A C A } }
{ qw{ A B C A B D A B E } qw{ E A D A } }
{ qw{ A B } qw{ B } }
{ qw{ A B } qw{ B A } }
{ qw{ A B B A } qw{ B A } }
}
[ show-reordering ] assoc-each
- Output:
M: the cat sat on the mat N: mat cat M': the mat sat on the cat M: the cat sat on the mat N: cat mat M': the cat sat on the mat M: A B C A B C A B C N: C A C A M': C B A C B A A B C M: A B C A B D A B E N: E A D A M': E B C A B D A B A M: A B N: B M': A B M: A B N: B A M': B A M: A B B A N: B A M': B A B A
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)
}
}
- 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
Haskell
import Data.List (mapAccumL, sort)
order
:: Ord a
=> [[a]] -> [a]
order [ms, ns] = snd . mapAccumL yu ls $ ks
where
ks = zip ms [(0 :: Int) ..]
ls = zip ns . sort . snd . foldl go (sort ns, []) . sort $ ks
yu ((u, v):us) (_, y)
| v == y = (us, u)
yu ys (x, _) = (ys, x)
go (u:us, ys) (x, y)
| u == x = (us, y : ys)
go ts _ = ts
task :: [String] -> IO ()
task ls@[ms, ns] =
putStrLn $
"M: " ++ ms ++ " | N: " ++ ns ++ " |> " ++ (unwords . order . map words $ ls)
main :: IO ()
main =
mapM_
task
[ ["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"]
]
- Output:
M: the cat sat on the mat | N: mat cat |> the mat sat on the cat M: the cat sat on the mat | N: cat mat |> the cat sat on the mat M: A B C A B C A B C | N: C A C A |> C B A C B A A B C M: A B C A B D A B E | N: E A D A |> E B C A B D A B A M: A B | N: B |> A B M: A B | N: B A |> B A M: A B B A | N: B A |> B A B A
Or, accumulating a segmentation of M over a fold, and zipping with N:
import Control.Monad (join)
import Data.Bifunctor (bimap)
import Data.List (delete, transpose)
import Data.Text hiding
( concat,
foldl,
maximum,
transpose,
zipWith,
)
import Prelude hiding (length, unlines, unwords, words)
disjointOrder ::
Eq a =>
[a] ->
[a] ->
[a]
disjointOrder m n = concat $ zipWith (<>) ms ns
where
ms = segments m n
-- As a list of lists, lengthened by 1
ns = ((: []) <$> n) <> [[]]
segments ::
Eq a =>
[a] ->
[a] ->
[[a]]
segments m n = _m <> [_acc]
where
(_m, _, _acc) = foldl split ([], n, []) m
split ::
Eq a =>
([[a]], [a], [a]) ->
a ->
([[a]], [a], [a])
split (ms, ns, acc) x
| x `elem` ns = (ms <> [acc], delete x ns, [])
| otherwise = (ms, ns, acc <> [x])
--------------------------- TEST -------------------------
tests :: [(Text, Text)]
tests =
join bimap pack
<$> [ ("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")
]
table :: Text -> [[Text]] -> Text
table delim rows =
unlines $
intercalate delim
<$> transpose
( ( \col ->
let width = (length $ maximum col)
in justifyLeft width ' ' <$> col
)
<$> transpose rows
)
main :: IO ()
main =
(putStr . unpack) $
table (pack " -> ") $
( \(m, n) ->
[ m,
n,
unwords (disjointOrder (words m) (words n))
]
)
<$> tests
- 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
Icon and Unicon
Works in both languages. Assumes a single blank separates items:
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
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:
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
)
Task examples:
'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
Java
Doesn't handle the case when an item of N is not a member of M.
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;
}
}
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]
JavaScript
ES6
Accumulating a segmentation of M over a fold/reduce, and zipping with N:
(() => {
"use strict";
// ------------ ORDER DISJOINT LIST ITEMS ------------
// disjointOrder :: [String] -> [String] -> [String]
const disjointOrder = ms =>
ns => zipWith(
a => b => [...a, b]
)(
segments(ms)(ns)
)(
ns.concat("")
)
.flat();
// segments :: [String] -> [String] -> [String]
const segments = ms =>
ns => {
const dct = ms.reduce((a, x) => {
const
wds = a.words,
found = wds.indexOf(x) !== -1;
return {
parts: [
...a.parts,
...(found ? [a.current] : [])
],
current: found ? [] : [...a.current, x],
words: found ? deleteFirst(x)(wds) : wds
};
}, {
words: ns,
parts: [],
current: []
});
return [...dct.parts, dct.current];
};
// ---------------------- TEST -----------------------
const main = () =>
transpose(transpose([{
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"
}].map(dct => [
dct.M, dct.N,
unwords(
disjointOrder(
words(dct.M)
)(
words(dct.N)
)
)
]))
.map(col => {
const
w = maximumBy(
comparing(x => x.length)
)(col).length;
return col.map(justifyLeft(w)(" "));
}))
.map(
([a, b, c]) => `${a} -> ${b} -> ${c}`
)
.join("\n");
// ---------------- GENERIC FUNCTIONS ----------------
// comparing :: (a -> b) -> (a -> a -> Ordering)
const comparing = f =>
// The ordering of f(x) and f(y) as a value
// drawn from {-1, 0, 1}, representing {LT, EQ, GT}.
x => y => {
const
a = f(x),
b = f(y);
return a < b ? -1 : (a > b ? 1 : 0);
};
// deleteFirst :: a -> [a] -> [a]
const deleteFirst = x => {
const go = xs => Boolean(xs.length) ? (
x === xs[0] ? (
xs.slice(1)
) : [xs[0]].concat(go(xs.slice(1)))
) : [];
return go;
};
// unwords :: [String] -> String
const unwords = xs =>
// A space-separated string derived
// from a list of words.
xs.join(" ");
// words :: String -> [String]
const words = s =>
// List of space-delimited sub-strings.
s.split(/\s+/u);
// zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
const zipWith = f =>
// A list constructed by zipping with a
// custom function, rather than with the
// default tuple constructor.
xs => ys => xs.map(
(x, i) => f(x)(ys[i])
).slice(
0, Math.min(xs.length, ys.length)
);
// ---------------- FORMATTING OUTPUT ----------------
// justifyLeft :: Int -> Char -> String -> String
const justifyLeft = n =>
// The string s, followed by enough padding (with
// the character c) to reach the string length n.
c => s => n > s.length ? (
s.padEnd(n, c)
) : s;
// maximumBy :: (a -> a -> Ordering) -> [a] -> a
const maximumBy = f =>
xs => Boolean(xs.length) ? (
xs.slice(1).reduce(
(a, x) => 0 < f(x)(a) ? (
x
) : a,
xs[0]
)
) : undefined;
// transpose :: [[a]] -> [[a]]
const transpose = rows =>
// The columns of a matrix of consistent row length,
// transposed into corresponding rows.
Boolean(rows.length) ? rows[0].map(
(_, i) => rows.flatMap(
v => v[i]
)
) : [];
// MAIN ---
return main();
})();
- 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
jq
Usage: M | disjoint_order(N)
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] ) ;
Examples:
(scrollable)
["the", "cat", "sat", "on", "the", "mat"] | indices( ["mat", "cat"] )
#=> ["the","mat","sat","on","the","cat"]
["the", "cat", "sat", "on", "the", "mat"] | disjoint_order( ["cat", "mat"] )
#=> ["the","cat","sat","on","the","mat"]
["A", "B", "C", "A", "B", "C", "A", "B", "C"] | disjoint_order( ["C", "A", "C", "A"] )
#=> ["C","B","A","C","B","A","A","B","C"]
["A", "B", "C", "A", "B", "D", "A", "B", "E"] | disjoint_order( ["E", "A", "D", "A"] )
#=> ["E","B","C","A","B","D","A","B","A"]
["A", "B"] | disjoint_order( ["B"] )
#=> ["A","B"]
["A", "B"] | disjoint_order( ["B", "A"] )
#=> ["B","A"]
["A", "B", "B", "A"] | disjoint_order( ["B", "A"] )
#=> ["B","A","B","A"]
["X", "X", "Y"] | disjoint_order(["X"])
#=> [X, X, Y]
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
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
Main
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
- 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
Kotlin
// version 1.0.6
const val NULL = "\u0000"
fun orderDisjointList(m: String, n: String): String {
val nList = n.split(' ')
// first replace the first occurrence of items of 'n' in 'm' with the NULL character
// which we can safely assume won't occur in 'm' naturally
var p = m
for (item in nList) p = p.replaceFirst(item, NULL)
// now successively replace the NULLs with items from nList
val mList = p.split(NULL)
val sb = StringBuilder()
for (i in 0 until nList.size) sb.append(mList[i], nList[i])
return sb.append(mList.last()).toString()
}
fun main(args: Array<String>) {
val m = arrayOf(
"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"
)
val n = arrayOf(
"mat cat",
"cat mat",
"C A C A",
"E A D A",
"B",
"B A",
"B A"
)
for (i in 0 until m.size)
println("${m[i].padEnd(22)} -> ${n[i].padEnd(7)} -> ${orderDisjointList(m[i], n[i])}")
}
- 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
Lua
-- Split str on any space characters and return as a table
function split (str)
local t = {}
for word in str:gmatch("%S+") do table.insert(t, word) end
return t
end
-- Order disjoint list items
function orderList (dataStr, orderStr)
local data, order = split(dataStr), split(orderStr)
for orderPos, orderWord in pairs(order) do
for dataPos, dataWord in pairs(data) do
if dataWord == orderWord then
data[dataPos] = false
break
end
end
end
local orderPos = 1
for dataPos, dataWord in pairs(data) do
if not dataWord then
data[dataPos] = order[orderPos]
orderPos = orderPos + 1
if orderPos > #order then return data end
end
end
return data
end
-- Main procedure
local testCases = {
{'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'}
}
for _, example in pairs(testCases) do
print(table.concat(orderList(unpack(example)), " "))
end
- 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 A A B B A B A B A
M2000 Interpreter
Simple
Function Checkit$ {
Document Ret$
Flush
Data "the cat sat on the mat", "mat cat"
Data "the cat sat on the mat","cat mat"'
Data "A B C A B C A B C", "C A C A"
Data "A B C A B D A B E", "E A D A"
Data "A B", "B"
Data "A B", "B A"
Data "A B B A","B A"
Dim A$()
while not empty
read m$, n$
A$()=piece$(m$, " ")
Let w=piece$(n$, " ")
Let z=A$()
x=each(w)
while x
y=z#pos(array$(x))
if y>-1 then a$(y)=""
end while
p=0
x=each(w)
while x
while a$(p)<>"" : p++: end while
a$(p)=array$(x)
end while
ret$=m$+" | "+n$+" -> "+z#str$()+{
}
end while
=ret$
}
Report Checkit$()
Clipboard Checkit$()
Using a third array, sorted
Function Checkit2$ {
Document Ret$
Flush
Data "the cat sat on the mat", "mat cat"
Data "the cat sat on the mat","cat mat"'
Data "A B C A B C A B C", "C A C A"
Data "A B C A B D A B E", "E A D A"
Data "A B", "B"
Data "A B", "B A"
Data "A B B A","B A"
Dim A$()
while not empty
read m$, n$
A$()=piece$(m$, " ")
Let w=piece$(n$, " ")
Let z=A$()
dim p(len(w))
x=each(w)
p=0
while x
y=z#pos(array$(x))
if y>-1 then a$(y)="": p(p)=y : p++
end while
u=p()#Sort()
x=each(u)
while x
a$(array(x))=w#val$(x^)
end while
ret$=m$+" | "+n$+" -> "+z#str$()+{
}
end while
=ret$
}
Report Checkit2$()
Clipboard Checkit2$()
- 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/Wolfram Language
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"}]]];
- 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
Nim
import algorithm, strutils
proc orderDisjoint(m, n: string): string =
# Build the list of items.
var m = m.splitWhitespace()
let n = n.splitWhitespace()
# Find the indexes of items to replace.
var indexes: seq[int]
for item in n:
let idx = m.find(item)
if idx >= 0:
indexes.add idx
m[idx] = "" # Set to empty string for next searches.
indexes.sort()
# Do the replacements.
for i, idx in indexes:
m[idx] = n[i]
result = m.join(" ")
when isMainModule:
template process(a, b: string) =
echo a, " | ", b, " → ", orderDisjoint(a, b)
process("the cat sat on the mat", "mat cat")
process("the cat sat on the mat", "cat mat")
process("A B C A B C A B C", "C A C A")
process("A B C A B D A B E", "E A D A")
process("A B", "B")
process("A B", "B A")
process("A B B A", "B A")
- 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
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";
}
- 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
Phix
Modified to support/skip missing elements
with javascript_semantics function order_disjoint(sequence m, sequence n) integer rlen = length(n) sequence rdis = repeat(0,rlen) for i=1 to rlen do object e = n[i] integer j = find(e,m) while j!=0 and find(j,rdis) do j = find(e,m,j+1) end while rdis[i] = j end for rdis = sort(rdis) while rlen and rdis[1]=0 do rdis = rdis[2..$] rlen -= 1 end while for i=1 to rlen do m[rdis[i]]=n[i] end for return join(m) end function sequence tests = {{"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"}, {"A X","Y A"}, {"A X","Y A X"}, {"A X","Y X A"}} for i=1 to length(tests) do string {m,n} = tests[i] printf(1,"\"%s\",\"%s\" => \"%s\"\n",{m,n,order_disjoint(split(m),split(n))}) end for
- 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" "A X","Y A" => "Y X" "A X","Y A X" => "Y A" "A X","Y X A" => "Y X"
PicoLisp
(de orderDisjoint (M N)
(for S N
(and (memq S M) (set @ NIL)) )
(mapcar
'((S) (or S (pop 'N)))
M ) )
Test:
: (orderDisjoint '(the cat sat on the mat) '(mat cat))
-> (the mat sat on the cat)
: (orderDisjoint '(the cat sat on the mat) '(cat mat))
-> (the cat sat on the mat)
: (orderDisjoint '(A B C A B C A B C) '(C A C A))
-> (C B A C B A A B C)
: (orderDisjoint '(A B C A B D A B E) '(E A D A))
-> (E B C A B D A B A)
: (orderDisjoint '(A B) '(B))
-> (A B)
: (orderDisjoint '(A B) '(B A))
-> (B A)
: (orderDisjoint '(A B B A) '(B A))
-> (B A B A)
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
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
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))
- 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
(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))
- 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)
Raku
(formerly Perl 6)
sub order-disjoint-list-items(\M, \N) {
my \bag = N.BagHash;
M.map: { bag{$_}-- ?? N.shift !! $_ }
}
# Testing:
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) }
- 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
REXX
Note: items in N needn't be in M.
/*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════ */
do j=1 while @.j\=='' /* [↓] process each input string (@.).*/
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); !.i= _; $._= i /*construct the !. and $. arrays.*/
end /*i*/
r.= /*nullify the replacement string [R.] */
do k=1 by 2 for words(n)%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 /*i*/
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. */
- output when using the internal default inputs:
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
def order_disjoint(m,n)
print "#{m} | #{n} -> "
m, n = m.split, n.split
from = 0
n.each_slice(2) do |x,y|
next unless y
sd = m[from..-1]
if x > y && (sd.include? x) && (sd.include? y) && (sd.index(x) > sd.index(y))
new_from = m.index(x)+1
m[m.index(x)+from], m[m.index(y)+from] = m[m.index(y)+from], m[m.index(x)+from]
from = new_from
end
end
puts m.join(' ')
end
[
['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 {|m,n| order_disjoint(m,n)}
- 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
sprintf version
ar = [
['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' ]
]
res = ar.map do |m,n|
mm = m.dup
nn = n.split
nn.each {|item| mm.sub!(item, "%s")} #sub! only subs the first match
mm % nn #"the %s sat on the %s" % [mat", "cat"] #does what you hope it does.
end
puts res
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)
Test:
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 " "}""")
}
- 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
func dsort(m, n) {
var h = Hash()
n.each {|item| h{item} := 0 ++ }
m.map {|item| h{item} := 0 -- > 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.join(' ')} | #{b.join(' ')} -> #{dsort(a.clone, b.clone).join(' ')}"
}
- 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
Swift
func disjointOrder<T: Hashable>(m: [T], n: [T]) -> [T] {
let replaceCounts = n.reduce(into: [T: Int](), { $0[$1, default: 0] += 1 })
let reduced = m.reduce(into: ([T](), n, replaceCounts), {cur, el in
cur.0.append(cur.2[el, default: 0] > 0 ? cur.1.removeFirst() : el)
cur.2[el]? -= 1
})
return reduced.0
}
print(disjointOrder(m: ["the", "cat", "sat", "on", "the", "mat"], n: ["mat", "cat"]))
print(disjointOrder(m: ["the", "cat", "sat", "on", "the", "mat"], n: ["cat", "mat"]))
print(disjointOrder(m: ["A", "B", "C", "A", "B", "C", "A", "B", "C"], n: ["C", "A", "C", "A"]))
print(disjointOrder(m: ["A", "B", "C", "A", "B", "D", "A", "B", "E"], n: ["E", "A", "D", "A"]))
print(disjointOrder(m: ["A", "B"], n: ["B"]))
print(disjointOrder(m: ["A", "B"], n: ["B", "A"]))
print(disjointOrder(m: ["A", "B", "B", "A"], n: ["B", "A"]))
- 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", "A"] ["A", "B"] ["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:
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
}
This is a more sophisticated version that handles items in the order list not being present in the list to be arranged:
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
}
Demonstration code (produces the same output from both implementations):
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]'"
}
- 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'
Wren
import "./fmt" for Fmt
var NULL = "\0"
var orderDisjointList = Fn.new { |m, n|
var nList = n.split(" ")
// first replace the first occurrence of items of 'n' in 'm' with the NULL character
// which we can safely assume won't occur in 'm' naturally
for (item in nList) {
var ix = m.indexOf(item)
if (ix >= 0) {
var le = item.count
m = m[0...ix] + NULL + m[ix + le..-1]
}
}
// now successively replace the NULLs with items from nList
var mList = m.split(NULL)
var sb = ""
for (i in 0...nList.count) sb = sb + mList[i] + nList[i]
return sb + mList[-1]
}
var ma = [
"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"
]
var na = [
"mat cat",
"cat mat",
"C A C A",
"E A D A",
"B",
"B A",
"B A"
]
for (i in 0...ma.count) {
Fmt.print("$-22s -> $-7s -> $s", ma[i], na[i], orderDisjointList.call(ma[i], na[i]))
}
- 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
zkl
fcn disOrder(sm,sn){
M:=sm.split(" ");
N:=sn.split(" "); nc:=Walker.cycle(Utils.Helpers.listUnique(N));
dn:=Dictionary(); 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
}
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()).
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));
}
- 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