Set consolidation: Difference between revisions

<br>Given N sets of items where N>2 then the result is the same as repeatedly replacing all combinations of two sets by their consolidation until no further consolidation between set pairs is possible.

'''See also:'''

We start with specifying a generic package Set_Cons that provides the neccessary tools, such as contructing and manipulating sets, truning them, ectetc.:

<langsyntaxhighlight Adalang="ada">generic

end Set_Cons;</langsyntaxhighlight>

<langsyntaxhighlight Adalang="ada">package body Set_Cons is

end Set_Cons;</langsyntaxhighlight>

<langsyntaxhighlight Adalang="ada">with Ada.Text_IO, Set_Cons;

end Set_Consolidation;</langsyntaxhighlight>

for (integer i;, record r in l) {

o_text(si ? ", {" : "{");

sfor =(u ",in ";r) {

o_text o_("{"v, u);

r v = l_q_record(l", i)";

for (integer i;, record r in l) {

rj = l_q_record(l, i) - ~l;

iwhile (j += 1;) {

j = i; if (intersect(r, l[j])) {

while r.wcall(r_add, 1, 2, l[j]) {;

record u l.delete(i);

return l;

display(consolidate(Llist(R("A", "B"), R("C", "D"))));

display(consolidate(Llist(R("A", "B"), R("B", "D"))));

display(consolidate(Llist(R("A", "B"), R("C", "D"), R("D", "B"))));

display(consolidate(Llist(R("H", "I", "K"), R("A", "B"), R("C", "D"),

R("D", "B"), R("F", "G", "K"))));

return 0;

}</langsyntaxhighlight>

<langsyntaxhighlight lang="bracmat">( ( consolidate

);</langsyntaxhighlight>

<langsyntaxhighlight lang="c">#include <stdio.h>

}</langsyntaxhighlight>

<langsyntaxhighlight lang="c">#include <stdio.h>

}</langsyntaxhighlight>

<langsyntaxhighlight lang="lisp">(defun consolidate (ss)

(reduce #'comb ss :initial-value nil)))</langsyntaxhighlight>

<langsyntaxhighlight lang="d">import std.stdio, std.algorithm, std.array;

dchar[][] consolidate(dchar[][] sets) @safe {

set.sort();

void main() @safe {

}</langsyntaxhighlight>

<langsyntaxhighlight lang="d">import std.stdio, std.algorithm, std.array;

dchar[][] consolidate(dchar[][] sets) @safe {

set.sort();

void main() @safe {

}</langsyntaxhighlight>

<langsyntaxhighlight lang="egison">

<langsyntaxhighlight lang="egison">

<langsyntaxhighlight lang="ela">open list

| else = conso (r ++ [y]) ys</langsyntaxhighlight>

<langsyntaxhighlight lang="ela">open consolemonad io

[#MapSet<[:A, :B]>, #MapSet<[:C, :D]>]</pre =>

<langsyntaxhighlight lang="fsharp">let (|SeqNode|SeqEmpty|) s =

0</langsyntaxhighlight>

<langsyntaxhighlight lang="go">package main

}</langsyntaxhighlight>

<syntaxhighlight lang Haskell="haskell">import qualified Data.SetList as(intersperse, Sintercalate)

consolidate :: Ord a => [S.Set a] -> [S.Set a]

where comb=> [S.Set a] s' =-> [s'S.Set a]

consolidate = foldr comb (s:ss) s'[]

<langsyntaxhighlight Jlang="j">consolidate=:4 :0/

)</langsyntaxhighlight>

<langsyntaxhighlight Jlang="j"> consolidate 'ab';'cd'

└─────┴────┘</langsyntaxhighlight>

<langsyntaxhighlight lang="java">import java.util.*;

}</langsyntaxhighlight>

=={{header|MathematicaJavaScript}}==

<langsyntaxhighlight lang="ocaml">let join a b =

;;</langsyntaxhighlight>

<langsyntaxhighlight lang="oorexx">/* REXX ***************************************************************

Return strip(ol)</langsyntaxhighlight>

<langsyntaxhighlight lang="parigp">cons(V)={

};</langsyntaxhighlight>

=={{header|Perl 6}}==

<pre>set(A,### B)Example set(C,1: D)[

### ==> set(C, D) set(A, B) [

### ==> set(A, B, D) 'B'

### ==> set(A, B, C, D) [

### ==> set(A, B, C, D) set(H, I, K, F, G)</pre> 'D'

<langsyntaxhighlight PicoLisplang="picolisp">(de consolidate (S)

R ) ) )</langsyntaxhighlight>

<langsyntaxhighlight PicoLisplang="picolisp">: (consolidate '((A B) (C D)))

-> ((F G H I K) (D B C A))</langsyntaxhighlight>

<langsyntaxhighlight PLlang="pl/Ii">Set: procedure options (main); /* 13 November 2013 */

end Set;</langsyntaxhighlight>

<langsyntaxhighlight lang="python">def consolidate(sets):

return [s for s in setlist if s]</langsyntaxhighlight>

<langsyntaxhighlight lang="python">def conso(s):

return r</langsyntaxhighlight>

<langsyntaxhighlight lang="python">def _test(consolidate=consolidate):

_test(conso)</langsyntaxhighlight>

<langsyntaxhighlight lang="racket">

<langsyntaxhighlight lang="racket">

<langsyntaxhighlight lang="rexx">/*REXX program showsdemonstrates howa tomethod consolidateof a sample bunch of sets.set consolidating using some sample sets. */

sets@.=; /*assign all SETS@.1 = '{A,B} to null. */{C,D}'

sets @.12 = '"{A,B} {CB,D}'"

sets @.23 = "'{A,B} {BC,D}" {D,B}'

sets @.34 = '{H,I,K} {A,B} {C,D} {D,B} {F,G,H}'

sets.4 = '{H,I,K} {A,B} {C,D} @.5 = '{Dsnow,Bice,slush,frost,fog} {icebergs,icecubes} {Frain,Gfog,Hsleet}'

do j=1 while sets@.j\=='' /*traipse through theeach of sample sets. */

call SETcomboSETconsolidate sets@.j /*have the other guyfunction do the heavy work. */

end /*j*/

exit 0 /*stick a fork in it, we're all done. */

do k=1 for n# /* [↓] change all commas to a blank. */

@ !.k= translate( word(bunchold, k), , '},{') /*create a list of words (=aka, a set).*/

end end /*k*/ /*... [↑] ··· and also remove the braces.*/

do until \changed; changed= 0 /*consolidate some sets (well, maybe).*/

do set=1 for n#-1

do item=1 for words(@!.set); x= word(@!.set, item)

do other=set+1 to n#

if isIn(x,@ !.other) then do; changed= 1 /*it's changed*/

@ !.set=@ !.set @!.other; @ !.other=

iterate set

end

end /*other*/

end /*item */

end /*set */

end /*until ¬changed*/

do set=1 for n#; new $= /*remove duplicates in a set. /*elide dups*/

do items=1 for words(@!.set); x= word(!.set, items)

x=word(@.set,items); if x==',' then iterate; if x=='' then leave

new $=new $ x /*start building the new set. /*build new.*/

do forever; until if \isIn(x,@ !.set); then leave _= wordpos(x, !.set)

_= wordpos(x,@ !.set)

@ !.set= subword(@!.set, 1, _-1) ',' subword(@!.set, _+1) /*purify set.*/

end end /*foreveruntil ¬isIn ··· */

end /*items*/

@ !.set= translate( strip(new$), ',', " ")

end /*set*/

do newi=1 for n#; if @!.newi=='' then iterate /*ignore any set that is a null set. */

end /*newi*/

say ' the new setsset=' newBunch new; say

the old setsset= {A,B} {B,D}

the new setsset= {A,B,D}

the old setsset= {A,B} {C,D} {D,B}

the new setsset= {A,B,D,C}

the old setsset= {H,I,K} {A,B} {C,D} {D,B} {F,G,H}

the new setsset= {H,I,K,F,G} {A,B,D,C}

the old setsset= {snow,ice,slush,frost,fog} {iceburgsicebergs,icecubes} {rain,fog,sleet}

the new setsset= {snow,ice,slush,frost,fog,rain,sleet} {iceburgsicebergs,icecubes}

<langsyntaxhighlight lang="ruby">require 'set'

tests = [[[':A', ':B'], [':C',':D']],

[[':A',':B'], [':B',':D']],

[[':A',':B'], [':C',':D'], [':D',':B']],

[[':H',':I',':K'], [':A',':B'], [':C',':D'], [':D',':B'], [':F',':G',':H']]]

tests = tests.map!{|sets| sets.map(&:to_set)}

tests.mapeach do |sets|

loop until sets.combination(2).none? do {|a,b| a.merge(b) && sets.delete(b) if a.intersect?(b)}

<langsyntaxhighlight lang="tcl">package require struct::set

}</langsyntaxhighlight>

<langsyntaxhighlight lang="tcl">puts 1:[consolidate {{A B} {C D}}]

puts 4:[consolidate {{H I K} {A B} {C D} {D B} {F G H}}]</langsyntaxhighlight>

(defun fnd (p x) (if (eq [p x] x) x (fnd p [p x])))

(defun uni (p x y)

(let ((xr (fnd p x)) (yr (fnd p y)))

(set [p xr] yr)))

(defun consoli (sets)

(let ((p (hash)))

(each ((s sets))

(each ((e s))

(mkset p e)

(uni p e (car s))))

(hash-values

[group-by (op fnd p) (hash-keys

[group-by identity (flatten sets)])])))

;; tests

(each ((test '(((a b) (c d))

((a b) (b d))

((a b) (c d) (d b))

((h i k) (a b) (c d) (d b) (f g h)))))

(format t "~s -> ~s\n" test (consoli test))))</langsyntaxhighlight>

((h i k) (a b) (c d) (d b) (f g h)) -> ((d c b a) (g f k i h) (d c b a))</pre>

=={{transheader|RacketVBA}}==