Set consolidation: Difference between revisions

'''See also'''

* [[wp:Connected component (graph theory)|Connected component (graph theory)]]

<br><br>

=={{header|Ada}}==

 

 

type Element is (<>);

with function Image(E: Element) return String;

type Set is array(Element) of Boolean;

 

 

Here is the implementation of Set_Cons:

 

 

function "+"(E: Element) return Set is

end Image;

 

 

Given that package, the task is easy:

 

 

procedure Set_Consolidation is

Ada.Text_IO.Put_Line

(Image(Consolidate((H+I+K) & (A+B) & (C+D) & (D+B) & (F+G+H))));

 

{{out}}

 

=={{header|Aime}}==

{

text u, v;

 

}

o_text("}");

}

 

}

 

intersect(record r, record u)

{

}

 

consolidate(list l)

{

integer j;

 

break;

}

}

 

}

 

R(...)

{

}

 

main(void)

{

 

{{out}}

<pre>{A, B}, {C, D}

{A, B, C, D}

{A, B, C, D}, {F, G, H, I, K}</pre>

 

=={{header|Bracmat}}==

= a m z mm za zm zz

. ( removeNumFactors

& test$(A+B C+D D+B)

& test$(H+I+K A+B C+D D+B F+G+H)

{{out}}

<pre>A+B C+D ==> A+B C+D

 

=={{header|C}}==

 

#define s(x) (1U << ((x) - 'A'))

puts("\nAfter:"); show_sets(x, consolidate(x, len));

return 0;

 

The above is O(N²) in terms of number of input sets. If input is large (many sets or huge number of elements), here's an O(N) method, where N is the sum of the sizes of all input sets:

#include <stdlib.h>

#include <string.h>

 

return 0;

 

=={{header|C sharp}}==

using System.Linq;

using System.Collections.Generic;

IEqualityComparer<T> comparer = null)

{

foreach (var set in sets) {

Node<T> top = null;

foreach (var set in currentSets) yield return set.Select(value => value);

}

{{out}}

<pre>

Sets consolidated using Set operations:

{H, I, K, F, G}, {A, B, D, C}</pre>

 

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

{{trans|Racket}}

(labels ((comb (cs s)

(cond ((null s) cs)

(cons (first cs) (comb (rest cs) s)))

((consolidate (cons (union s (first cs)) (rest cs)))))))

 

{{Out}}

=={{header|D}}==

{{trans|Go}}

 

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

[['H','I','K'], ['A','B'], ['C','D'],

['D','B'], ['F','G','H']].consolidate.writeln;

{{out}}

<pre>["AB", "CD"]

 

'''Recursive version''', as described on talk page.

 

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

[['H','I','K'], ['A','B'], ['C','D'],

['D','B'], ['F','G','H']].consolidate.writeln;

<pre>["AB", "CD"]

["ABD"]

["ABCD"]

["FGHIK", "ABCD"]</pre>

 

=={{header|EchoLisp}}==

;; utility : make a set of sets from a list

(define (make-set* s)

→ { { a b c d } { f g h i k } }

 

=={{header|Egison}}==

 

(define $consolidate

(lambda [$xss]

 

(test (consolidate {{'H' 'I' 'K'} {'A' 'B'} {'C' 'D'} {'D' 'B'} {'F' 'G' 'H'}}))

{{out}}

{"DBAC" "HIKFG"}

 

=={{header|Ela}}==

This solution emulate sets using linked lists:

 

merge [] ys = ys

where conso xs [] = xs

conso (x::xs)@r (y::ys) | intersect x y <> [] = conso ((merge x y)::xs) ys

Usage:

 

:::IO

putLn x

y <- return $ consolidate [['A','B'], ['B','D']]

 

Output:<pre>[['K','I','F','G','H'],['A','C','D','B']]

 

=={{header|Elixir}}==

def set_consolidate(sets, result\\[])

def set_consolidate([], result), do: result

IO.write "#{inspect sets} =>\n\t"

IO.inspect RC.set_consolidate(sets)

 

{{out}}

 

=={{header|F_Sharp|F#}}==

if Seq.isEmpty s then SeqEmpty

else SeqNode ((Seq.head s), Seq.skip 1 s)

[["H";"I";"K"]; ["A";"B"]; ["C";"D"]; ["D";"B"]; ["F";"G";"H"]]

]

{{out}}

<pre>seq [set ["C"; "D"]; set ["A"; "B"]]

seq [set ["A"; "B"; "C"; "D"]]

seq [set ["A"; "B"; "C"; "D"]; set ["F"; "G"; "H"; "I"; "K"]]</pre>

 

=={{header|Go}}==

{{trans|Python}}

 

import "fmt"

}

return true

{{out}}

<pre>

=={{header|Haskell}}==

 

 

 

{{Out}}

 

=={{header|J}}==

 

b=. y 1&e.@e.&> x

(1,-.b)#(~.;x,b#y);y

 

Examples:

 

┌──┬──┐

│ab│cd│

┌─────┬────┐

│hijfg│abcd│

 

=={{header|Java}}==

{{trans|D}}

{{works with|Java|7}}

 

public class SetConsolidation {

return r;

}

<pre>[A, B] [D, C]

[D, A, B]

[D, A, B, C]

[F, G, H, I, K] [D, A, B, C]</pre>

 

=={{header|jq}}==

 

Currently, jq does not have a "Set" library, so to save space here, we will use simple but inefficient implementations of set-oriented functions as they are fast for sets of moderate size. Nevertheless, we will represent sets as sorted arrays.

 

def union(A; B): (A + B) | unique;

# boolean

def intersect(A;B):

'''Consolidation''':

 

For clarity, the helper functions are presented as top-level functions, but they could be defined as inner functions of the main function, consolidate/0.

 

# Return [i,j] for a pair that can be combined, else null

def combinable:

end

end;

'''Examples''':

[["A", "B"], ["C","D"]],

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

tests | to_set | consolidate;

 

{{Out}}

[["A","B"],["C","D"]]

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

[["A","B","C","D"]]

 

=={{header|Julia}}==

 

Here I assume that the data are contained in a list of sets. Perhaps a recursive solution would be more elegant, but in this case playing games with a stack works well enough.

function consolidate{T}(a::Array{Set{T},1})

1 < length(a) || return a

return c

end

 

'''Main'''

p = Set(["A", "B"])

q = Set(["C", "D"])

println("consolidate([p, q, r, s, t]) =\n ",

consolidate([p, q, r, s, t]))

 

{{out}}

 

=={{header|Kotlin}}==

 

fun<T : Comparable<T>> consolidateSets(sets: Array<Set<T>>): Set<Set<T>> {

)

for (sets in unconsolidatedSets) println(consolidateSets(sets))

 

{{out}}

</pre>

 

Block[{pairs, unique},

pairs =

unique = Complement[Range@Length@x, Flatten@pairs];

Join[Union[Flatten[x[[#]]]] & /@ pairs, x[[unique]]]]

<pre>consolidate[{a, b}, {c, d}]

-> {{a, b}, {c, d}}

consolidate[{a, b}, {b, d}]

-> {{a, b, d}}

consolidate[{a, b}, {c, d}, {d, b}]

-> {{a, b, c, d}}

consolidate[{h, i, k}, {a, b}, {c, d}, {d, b}, {f, g, h}]

-> {{a,b,c,d},{f,g,h,i,k}}</pre>

 

=={{header|OCaml}}==

 

List.fold_left (fun acc v ->

if List.mem v acc then acc else v::acc

print_sets (consolidate [["H";"I";"K"]; ["A";"B"]; ["C";"D"]; ["D";"B"];

["F";"G";"H"]]);

 

{{out}}

 

=={{header|ooRexx}}==

* 04.08.2013 Walter Pachl using ooRexx features

* (maybe not in the best way -improvements welcome!)

End

End

{{out}}

<pre>

 

=={{header|PARI/GP}}==

my(v,u,s);

for(i=1,#V,

V=select(v->#v,V);

if(s,cons(V),V)

 

=={{header|Perl}}==

We implement the key data structure, a set of sets, as an array containing references to arrays of scalars.

use English;

use Smart::Comments;

}

return @result;

{{out}}

<pre>### Example 1: [

### ]</pre>

 

{{out}}

 

=={{header|PicoLisp}}==

{{trans|Python}}

(when S

(let R (cons (car S))

(set R (uniq (conc X (car R))))

(conc R (cons X)) ) )

Test:

-> ((A B) (C D))

: (consolidate '((A B) (B D)))

-> ((D B C A))

: (consolidate '((H I K) (A B) (C D) (D B) (F G H)))

 

=={{header|PL/I}}==

declare set(20) character (200) varying;

declare e character (1);

end print;

 

<pre>

The original sets: {A,B}

Results: {A,B,E,F,G,H} {C,D}

</pre>

 

=={{header|Python}}==

===Python: Iterative===

setlist = [s for s in sets if s]

for i, s1 in enumerate(setlist):

s1.clear()

s1 = s2

 

===Python: Recursive===

if len(s) < 2: return s

if r[0].intersection(x): r[0].update(x)

else: r.append(x)

 

===Python: Testing===

The <code>_test</code> function contains solutions to all the examples as well as a check to show the order-independence of the sets given to the consolidate function.

def freze(list_of_sets):

if __name__ == '__main__':

_test(consolidate)

 

{{out}}

<pre>_test(consolidate) complete

_test(conso) complete</pre>

 

=={{header|Racket}}==

#lang racket

(define (consolidate ss)

(consolidate (list (set 'a 'b) (set 'c 'd) (set 'd 'b)))

(consolidate (list (set 'h 'i 'k) (set 'a 'b) (set 'c 'd) (set 'd 'b) (set 'f 'g 'h)))

{{out}}

(list (set 'b 'a) (set 'd 'c))

(list (set 'a 'b 'c))

(list (set 'a 'b 'd 'c))

(list (set 'g 'h 'k 'i 'f) (set 'a 'b 'd 'c))

 

 

=={{header|REXX}}==

 

/*──────────────────────────────────────────────────────────────────────────────────────*/

isIn: return wordpos(arg(1), arg(2))\==0 /*is (word) argument 1 in the set arg2?*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

 

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

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

 

do set=1 for #-1

do other=set+1 to #

iterate set

end

end /*until ¬changed*/

 

if x==',' then iterate; if x=='' then leave

end /*until ¬isIn ··· */

end /*items*/

end /*set*/

 

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

end /*i*/

 

say ' the new set=' new; say

<pre>

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

the old set= {snow,ice,slush,frost,fog} {icebergs,icecubes} {rain,fog,sleet}

the new set= {snow,ice,slush,frost,fog,rain,sleet} {icebergs,icecubes}

</pre>

 

=={{header|Ruby}}==

 

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

end

p sets

{{out}}

<pre>

 

=={{header|Scala}}==

def consolidate[Type](sets: Set[Set[Type]]): Set[Set[Type]] = {

var result = sets // each iteration combines two sets and reiterates, else returns

})

 

{{out}}

<pre>{A,B} {C,D} -> {A,B} {C,D}

{A,B} {C,D} {D,B} -> {C,D,A,B}

{D,B} {F,G,H} {A,B} {C,D} {H,I,K} -> {F,I,G,H,K} {A,B,C,D}</pre>

 

=={{header|Sidef}}==

func consolidate(this, *those) {

gather {

].each { |ss|

say (format(ss), "\n\t==> ", format(consolidate(ss...)));

{{out}}

<pre>

(H I K) (A B) (C D) (D B) (F G H)

==> (A C D B) (I K F G H)

</pre>

 

{{tcllib|struct::set}}

This uses just the recursive version, as this is sufficient to handle substantial merges.

 

proc consolidate {sets} {

}

return [lset r 0 $r0]

Demonstrating:

puts 2:[consolidate {{A B} {B D}}]

puts 3:[consolidate {{A B} {C D} {D B}}]

{{out}}

<pre>1:{A B} {C D}

Original solution:

 

 

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

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

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

 

{{out}}

{{trans|Racket}}

 

 

(defun empty-p (set) (zerop (hash-count set)))

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

(format t "~s -> ~s\n" test

 

{{out}}

((a b) (c d) (d b)) -> ((d c b a))

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

 

=={{header|VBScript}}==

Function consolidate(s)

sets = Split(s,",")

WScript.StdOut.WriteLine consolidate(t)

Next

 

{{Out}}

AB,CD,DB = ABCD , - , -

HIK,AB,CD,DB,FGH = HIKFG , ABCD , - , - , -

</pre>

 

=={{header|zkl}}==

{{trans|Tcl}}

if(sets.len()<2) return(sets);

r,r0 := List(List()),sets[0];

r[0]=r0;

r

sets.apply("concat"," ").pump(String,"(%s),".fmt)[0,-1]

}

prettize(sets).print(" --> ");

consolidate(sets) : prettize(_).println();

{{out}}

<pre>