Order disjoint list items: Difference between revisions

 

Given &nbsp; <code>M</code> &nbsp; as a list of items and another list &nbsp; <code>N</code> &nbsp; of items chosen from &nbsp; <code>M</code>, &nbsp; create &nbsp; <code>M'</code> &nbsp; as a list with the ''first'' occurrences of items from &nbsp; N &nbsp; sorted to be in one of the set of indices of their original occurrence in &nbsp; <code>M</code> &nbsp; but in the order given by their order in &nbsp; <code>N</code>.

* [[Sort disjoint sublist]]

<br><br>

 

=={{header|Aime}}==

{

integer j;

 

0;

{{out}}

<pre>the cat sat on the mat | mat cat -> the mat sat on the cat

 

=={{header|AppleScript}}==

{{Trans|JavaScript}}

 

Accumulate a segmentation of M over a fold/reduce, and zip with N:

 

-- disjointOrder :: String -> String -> String

unwords(flatten(zip(segments(ms, ns), ns & "")))

end disjointOrder

 

-- segments :: [String] -> [String] -> [String]

 

 

on run

script order

end |λ|

end script

arrowTable(map(order, [¬

 

 

 

-- arrowTable :: [[String]] -> String

transpose(map(leftAligned, transpose(rows)))))

end arrowTable

 

-- concatMap :: (a -> [b]) -> [a] -> [b]

foldl(append, {}, map(f, xs))

end concatMap

 

-- deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a]

end if

end deleteBy

 

-- deleteFirst :: a -> [a] -> [a]

deleteBy(Eq, x, xs)

end deleteFirst

 

-- flatten :: Tree a -> [a]

end if

end flatten

 

-- foldl :: (a -> b -> a) -> a -> [b] -> a

end tell

end foldl

 

-- intercalate :: Text -> [Text] -> Text

return strJoined

end intercalate

 

-- justifyLeft :: Int -> Char -> Text -> Text

end if

end justifyLeft

 

-- map :: (a -> b) -> [a] -> [b]

end tell

end map

 

-- maximumBy :: (a -> a -> Ordering) -> [a] -> a

foldl(max, missing value, xs)

end maximumBy

 

-- minimum :: [a] -> a

foldl(min, missing value, xs)

end minimum

 

-- Lift 2nd class handler function into 1st class script wrapper

end if

end mReturn

 

-- Egyptian multiplication - progressively doubling a list, appending

return out & dbl

end replicate

 

-- transpose :: [[a]] -> [[a]]

map(column, item 1 of xss)

end transpose

 

-- uncons :: [a] -> Maybe (a, [a])

end if

end uncons

 

-- unwords :: [String] -> String

words of s

end |words|

 

-- zip :: [a] -> [b] -> [(a, b)]

map(pair, items 1 thru minimum([length of xs, length of ys]) of xs)

{{Out}}

<pre>the cat sat on the mat -> mat cat -> the mat sat on the cat

A B -> B A -> B A

A B B A -> B A -> B A B A </pre>

 

=={{header|AutoHotkey}}==

{{works with|AutoHotkey 1.1}}

, {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"}

Result .= (ItemsN[A_LoopField]-- > 0 ? N.Remove(1) : A_LoopField) " "

return RTrim(Result)

{{Output}}

<pre>the cat sat on the mat :: mat cat -> the mat sat on the cat

 

=={{header|Bracmat}}==

= M N NN item A Z R

. !arg:(?M.?N)

& out$(\t odli$(!M.!N))

)

Output:

<pre>Data M: the cat sat on the mat Order N: mat cat the mat sat on the cat

 

=={{header|C++}}==

#include <iostream>

#include <vector>

std::cin.get();

return 0;

 

{{out}}

 

=={{header|Common Lisp}}==

(let ((order-b (make-hash-table :test 'equal)))

(loop :for n :in order :do (incf (gethash n order-b 0)))

(decf (gethash m order-b))

(pop order))

{{out}}

<pre>CL-USER> (order-disjoint '(the cat sat on the mat) '(mat cat))

{{trans|Python}}

This version is not efficient.

std.conv;

 

orderDisjointArrayItems(a, b));

}

{{out}}

<pre>the cat sat on the mat | mat cat -> the mat sat on the cat

 

=={{header|EchoLisp}}==

(lib 'list) ;; for list-delete

 

 

{{out}}

<pre>

 

=={{header|Elixir}}==

def disjoint(m,n) do

IO.write "#{Enum.join(m," ")} | #{Enum.join(n," ")} -> "

|> Enum.each(fn {m,n} ->

Order.disjoint(String.split(m),String.split(n))

 

{{out}}

=={{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,

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.

 

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.

 

fry kernel qw sequences ;

IN: rosetta-code.order-disjoint-list

{ qw{ A B B A } qw{ B A } }

}

{{out}}

<pre>

 

=={{header|Go}}==

 

import (

}

 

{{out}}

<pre>

A B B A → B A » B A B A

</pre>

=={{header|Haskell}}==

 

order

, ["A B", "B A"]

, ["A B B A", "B A"]

{{out}}

<pre>

{{Trans|JavaScript}}

 

import Data.List (delete, transpose)

 

where

ms = segments m n

where

(_m, _, _acc) = foldl split ([], n, []) m

split (ms, ns, acc) x

 

tests :: [(Text, Text)]

tests =

 

table :: Text -> [[Text]] -> Text

table delim rows =

unlines $

 

main :: IO ()

main =

{{Out}}

<pre>the cat sat on the mat -> mat cat -> the mat sat on the cat

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

 

every write(" -> ",odli("the cat sat on the mat","mat cat"))

every write(" -> ",odli("the cat sat on the mat","cat mat"))

}

return Mp

 

Output:

Implementation:

 

:

clusters=. (</. i.@#) x

to=. ;need {.!._ each order{clusters

(from{x) to} x

 

Task examples:

 

the mat sat on the cat

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

B A

'A B B A' disjorder 'B A'

 

=={{header|Java}}==

Doesn't handle the case when an item of N is not a member of M.

import java.util.BitSet;

import org.apache.commons.lang3.ArrayUtils;

return m;

}

 

Output:

Accumulating a segmentation of M over a fold/reduce, and zipping with N:

 

 

 

 

// deleteFirst :: a -> [a] -> [a]

x === xs[0] ? (

xs.slice(1)

) : [];

 

 

// unwords :: [String] -> String

 

// words :: String -> [String]

 

 

);

 

 

 

 

// maximumBy :: (a -> a -> Ordering) -> [a] -> a

 

 

 

 

 

{{Out}}

 

Usage: <tt>M | disjoint_order(N)</tt>

# The helper function, indices, ensures that successive occurrences

# of a particular value in N are matched by successive occurrences

. as $in

| (indices | sort) as $sorted

 

'''Examples''':

(scrollable)

<div style="overflow:scroll; height:400px;">

 

 

 

 

 

 

 

</div>

 

 

'''Function'''

function order_disjoint{T<:AbstractArray}(m::T, n::T)

rlen = length(n)

return p

end

'''Main'''

testm = {["the", "cat", "sat", "on", "the", "mat"],

["the", "cat", "sat", "on", "the", "mat"],

println(" (", m, ", ", n, ") => ", p)

end

 

{{out}}

 

=={{header|Kotlin}}==

 

const val NULL = "\u0000"

for (i in 0 until m.size)

println("${m[i].padEnd(22)} -> ${n[i].padEnd(7)} -> ${orderDisjointList(m[i], n[i])}")

 

{{out}}

 

=={{header|Lua}}==

function split (str)

local t = {}

for _, example in pairs(testCases) do

print(table.concat(orderList(unpack(example)), " "))

{{out}}

<pre>the mat sat on the cat

B A

B A B A</pre>

 

ReplacePart[m,

MapThread[

Print[StringRiffle[order[{"A", "B"}, {"B"}]]];

Print[StringRiffle[order[{"A", "B"}, {"B", "A"}]]];

{{out}}

<pre>the mat sat on the cat

B A

B A B A</pre>

 

=={{header|Perl}}==

my ($m, $n) = @_;

my %h;

my ($a, $b) = map([split], split '\|');

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

{{out}}

<pre>

A B B A | B A -> B A B A

</pre>

 

=={{header|Phix}}==

{{Trans|Julia}}

Modified to support/skip missing elements

{{out}}

<pre>

 

=={{header|PicoLisp}}==

(for S N

(and (memq S M) (set @ NIL)) )

(mapcar

'((S) (or S (pop 'N)))

Test:

-> (the mat sat on the cat)

 

 

: (orderDisjoint '(A B B A) '(B A))

 

=={{header|PowerShell}}==

function sublistsort($M, $N) {

$arr = $M.Split(' ')

sublistsort $M6 $N6

sublistsort $M7 $N7

<b>Output:</b>

<pre>

 

=={{header|Python}}==

 

def order_disjoint_list_items(data, items):

print('Data M: %-24r Order N: %-9r' % (tostring(data), tostring(items)), end=' ')

order_disjoint_list_items(data, items)

 

{{out}}

 

=={{header|Racket}}==

(define disjorder

(match-lambda**

(report-disjorder '(A B A B) '(B A B A))

(report-disjorder '(A B C C B A) '(A C A C))

 

{{out}}

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>

 

=={{header|REXX}}==

Note: &nbsp; items in &nbsp; <big>'''N'''</big> &nbsp; needn't be in &nbsp; <big>'''M'''</big>.

used = '0'x /*indicates that a word has been parsed*/

@. = /*placeholder indicates end─of─array, */

say @.j ' ────► ' space(mp) /*display new re─ordered text ──► term.*/

end /*j*/ /* [↑] end of processing for N words*/

<pre>

the cat sat on the mat | mat cat ───► the mat sat on the cat

 

=={{header|Ruby}}==

print "#{m} | #{n} -> "

m, n = m.split, n.split

['A B' , 'B A' ],

['A B B A' , 'B A' ]

{{out}}

<pre>

A B B A | B A -> B A B A

</pre>

 

=={{header|Scala}}==

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)

'''Test:'''

"the cat sat on the mat" -> "mat cat",

"the cat sat on the mat" -> "cat mat",

val done = order(input.split(" "), using.split(" "))

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

{{out}}

<pre>Data M: the cat sat on the mat Order N: mat cat -> Result M': the mat sat on the cat

=={{header|Sidef}}==

{{trans|Perl}}

var h = Hash()

n.each {|item| h{item} := 0 ++ }

EOT

var (a, b) = line.split('|').map{.words}...

{{out}}

<pre>

=={{header|Swift}}==

 

let replaceCounts = n.reduce(into: [T: Int](), { $0[$1, default: 0] += 1 })

let reduced = m.reduce(into: ([T](), n, replaceCounts), {cur, el in

print(disjointOrder(m: ["A", "B"], n: ["B"]))

print(disjointOrder(m: ["A", "B"], n: ["B", "A"]))

 

{{out}}

=={{header|Tcl}}==

This is a simple version that assumes that ''all'' items in the order list are present in the list to be arranged:

foreach item $theOrderList {incr n($item)}

set is {}

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:

foreach item $theOrderList {incr n($item)}

set is -

}

return $theList

Demonstration code (produces the same output from both implementations):

"the cat sat on the mat" "mat cat"

"the cat sat on the mat" "cat mat"

} {

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

{{out}}

<pre>

'A B' with 'B A' => 'B A'

'A B B A' with 'B A' => 'B A B A'

</pre>

 

=={{header|zkl}}==

M:=sm.split(" ");

N:=sn.split(" "); nc:=Walker.cycle(Utils.Helpers.listUnique(N));

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()).

T("the cat sat on the mat","cat mat"),

T("A B C A B C A B C","C A C A"),

foreach m,n in (sets){

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

{{out}}

<pre>