Set consolidation: Difference between revisions

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

 

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

{

for (integer i, record r in l) {

 

0;

{{out}}

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

{A, B, C, D}

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

 

=={{header|AutoHotkey}}==

arr2 := [] , arr3 := [] , arr4 := [] , arr5 := [], result:=[]

; sort each set individually

result[i, A_Index] := k

return result

test2 := [["A","B"], ["B","D"]]

test3 := [["A","B"], ["C","D"], ["D","B"]]

}

MsgBox % RTrim(result, "`n[")

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

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

 

 

=={{header|Clojure}}==

(apply clojure.set/union sets))

 

(recur (remove-used (rest seeds) linked)

(conj (remove-used sets linked)

 

{{out}}

=={{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"]]

 

=={{header|Factor}}==

 

: comb ( x x -- x )

] if ;

 

{{out}}

<pre>

=={{header|Go}}==

{{trans|Python}}

 

import "fmt"

}

return true

{{out}}

<pre>

=={{header|Haskell}}==

 

import qualified Data.Set as S

 

 

showSet :: S.Set Char -> String

 

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

 

=={{header|JavaScript}}==

'use strict';

 

// MAIN ---

return main();

{{Out}}

<pre>{c,d}, and {a,b}

 

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|Nim}}==

{{trans|Python}}

if len(sets) < 2:

var (r, b) = (@[sets[0]], consolidate(sets[1..^1]))

for x in b:

r

 

{{out}}

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

=={{header|Phix}}==

Using strings to represent sets of characters

{{out}}

<pre>

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

{{Trans|JavaScript}}

{{Works with|Python|3.7}}

 

from functools import (reduce)

# MAIN ---

if __name__ == '__main__':

{{Out}}

<pre>Consolidation of sets of characters:

['ba', 'cd', 'db'] -> [{'d', 'a', 'c', 'b'}]

['ikh', 'ba', 'cd', 'db', 'gfh'] -> [{'d', 'a', 'c', 'b'}, {'i', 'k', 'g', 'h', 'f'}]</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|Raku}}==

(formerly Perl 6)

multi consolidate(Set \this is copy, *@those) {

gather {

[set(A,B), set(B,D)],

[set(A,B), set(C,D), set(D,B)],

{{out}}

<pre>set(A, B) set(C, D)

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

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

 

=={{header|REXX}}==

@.=; @.1 = '{A,B} {C,D}'

@.2 = "{A,B} {B,D}"

 

say ' the new set=' new; say

{{out|output|text=&nbsp; when using the (internal) default supplied sample sets:}}

<pre>

 

=={{header|Ring}}==

# Project : Set consolidation

 

consolidate = s + " = " + substr(list2str(sets),nl,",")

return consolidate

Output:

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

{{trans|Raku}}

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

{{trans|Phix}}

This solutions uses collections as sets. The first three coroutines are based on the Phix solution. Two coroutines are written to create the example sets as collections, and another coroutine to show the consolidated set.

For Each element In set1

On Error Resume Next

show consolidate(ms(Array(mc("AB"), mc("CD"), mc("DB"))))

show consolidate(ms(Array(mc("HIK"), mc("AB"), mc("CD"), mc("DB"), mc("FGH"))))

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

{{A, B, D}}

 

=={{header|VBScript}}==

Function consolidate(s)

sets = Split(s,",")

WScript.StdOut.WriteLine consolidate(t)

Next

 

{{Out}}

 

As Sets are Map-based, iteration (and hence printing) order are undefined.

 

var consolidateSets = Fn.new { |sets|

System.print("Unconsolidated: %(sets)")

System.print("Cosolidated : %(consolidateSets.call(sets))\n")

 

{{out}}

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