Set consolidation: Difference between revisions
m
syntax highlighting fixup automation
m (→{{header|J}}: restore proper handling of consolidate 'ab';'bd') |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 28:
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;
Line 54:
type Set is array(Element) of Boolean;
end Set_Cons;</
Here is the implementation of Set_Cons:
<
function "+"(E: Element) return Set is
Line 134:
end Image;
end Set_Cons;</
Given that package, the task is easy:
<
procedure Set_Consolidation is
Line 177:
Ada.Text_IO.Put_Line
(Image(Consolidate((H+I+K) & (A+B) & (C+D) & (D+B) & (F+G+H))));
end Set_Consolidation;</
{{out}}
Line 186:
=={{header|Aime}}==
<
{
for (integer i, record r in l) {
Line 240:
0;
}</
{{out}}
<pre>{A, B}, {C, D}
Line 248:
=={{header|AutoHotkey}}==
<
arr2 := [] , arr3 := [] , arr4 := [] , arr5 := [], result:=[]
; sort each set individually
Line 293:
result[i, A_Index] := k
return result
}</
Examples:<
test2 := [["A","B"], ["B","D"]]
test3 := [["A","B"], ["C","D"], ["D","B"]]
Line 312:
}
MsgBox % RTrim(result, "`n[")
return</
{{out}}
<pre>[["A","B"] , ["C","D"]]
Line 320:
=={{header|Bracmat}}==
<
= a m z mm za zm zz
. ( removeNumFactors
Line 347:
& 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
Line 362:
=={{header|C}}==
<
#define s(x) (1U << ((x) - 'A'))
Line 398:
puts("\nAfter:"); show_sets(x, consolidate(x, len));
return 0;
}</
The above is O(N<sup>2</sup>) 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>
Line 502:
return 0;
}</
=={{header|C sharp}}==
<
using System.Linq;
using System.Collections.Generic;
Line 611:
foreach (var set in currentSets) yield return set.Select(value => value);
}
}</
{{out}}
<pre>
Line 644:
=={{header|Clojure}}==
<
(apply clojure.set/union sets))
Line 661:
(recur (remove-used (rest seeds) linked)
(conj (remove-used sets linked)
(consolidate-linked-sets linked)))))))</
{{out}}
Line 675:
=={{header|Common Lisp}}==
{{trans|Racket}}
<
(labels ((comb (cs s)
(cond ((null s) cs)
Line 682:
(cons (first cs) (comb (rest cs) s)))
((consolidate (cons (union s (first cs)) (rest cs)))))))
(reduce #'comb ss :initial-value nil)))</
{{Out}}
Line 696:
=={{header|D}}==
{{trans|Go}}
<
dchar[][] consolidate(dchar[][] sets) @safe {
Line 724:
[['H','I','K'], ['A','B'], ['C','D'],
['D','B'], ['F','G','H']].consolidate.writeln;
}</
{{out}}
<pre>["AB", "CD"]
Line 732:
'''Recursive version''', as described on talk page.
<
dchar[][] consolidate(dchar[][] sets) @safe {
Line 763:
[['H','I','K'], ['A','B'], ['C','D'],
['D','B'], ['F','G','H']].consolidate.writeln;
}</
<pre>["AB", "CD"]
["ABD"]
Line 770:
=={{header|EchoLisp}}==
<
;; utility : make a set of sets from a list
(define (make-set* s)
Line 795:
→ { { a b c d } { f g h i k } }
</syntaxhighlight>
=={{header|Egison}}==
<
(define $consolidate
(lambda [$xss]
Line 810:
(test (consolidate {{'H' 'I' 'K'} {'A' 'B'} {'C' 'D'} {'D' 'B'} {'F' 'G' 'H'}}))
</syntaxhighlight>
{{out}}
<
{"DBAC" "HIKFG"}
</syntaxhighlight>
=={{header|Ela}}==
This solution emulate sets using linked lists:
<
merge [] ys = ys
Line 828:
where conso xs [] = xs
conso (x::xs)@r (y::ys) | intersect x y <> [] = conso ((merge x y)::xs) ys
| else = conso (r ++ [y]) ys</
Usage:
<
:::IO
Line 838:
putLn x
y <- return $ consolidate [['A','B'], ['B','D']]
putLn y</
Output:<pre>[['K','I','F','G','H'],['A','C','D','B']]
Line 844:
=={{header|Elixir}}==
<
def set_consolidate(sets, result\\[])
def set_consolidate([], result), do: result
Line 866:
IO.write "#{inspect sets} =>\n\t"
IO.inspect RC.set_consolidate(sets)
end)</
{{out}}
Line 881:
=={{header|F_Sharp|F#}}==
<
if Seq.isEmpty s then SeqEmpty
else SeqNode ((Seq.head s), Seq.skip 1 s)
Line 906:
[["H";"I";"K"]; ["A";"B"]; ["C";"D"]; ["D";"B"]; ["F";"G";"H"]]
]
0</
{{out}}
<pre>seq [set ["C"; "D"]; set ["A"; "B"]]
Line 914:
=={{header|Factor}}==
<
: comb ( x x -- x )
Line 923:
] if ;
: consolidate ( x -- x ) { } [ comb ] reduce ;</
{{out}}
<pre>
Line 939:
=={{header|Go}}==
{{trans|Python}}
<
import "fmt"
Line 994:
}
return true
}</
{{out}}
<pre>
Line 1,002:
=={{header|Haskell}}==
<
import qualified Data.Set as S
Line 1,027:
showSet :: S.Set Char -> String
showSet = flip intercalate ["{", "}"] . intersperse ',' . S.elems</
{{Out}}
Line 1,037:
=={{header|J}}==
<
b=. y 1&e.@e.&> x
(1,-.b)#(~.;x,b#y);y
)</
In other words, fold each set into a growing list of consolidated sets. When there's any overlap between the newly considered set (<code>x</code>) and any of the list of previously considered sets (<code>y</code>), merge the unique values from all of those into a single set (any remaining sets remain as-is). Here, <code>b</code> selects the overlapping sets from y (and <code>-.b</code> selects the rest of those sets).
Line 1,046:
Examples:
<
┌──┬──┐
│ab│cd│
Line 1,061:
┌─────┬────┐
│hijfg│abcd│
└─────┴────┘</
=={{header|Java}}==
{{trans|D}}
{{works with|Java|7}}
<
public class SetConsolidation {
Line 1,128:
return r;
}
}</
<pre>[A, B] [D, C]
[D, A, B]
Line 1,135:
=={{header|JavaScript}}==
<
'use strict';
Line 1,255:
// MAIN ---
return main();
})();</
{{Out}}
<pre>{c,d}, and {a,b}
Line 1,266:
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;
Line 1,272:
# boolean
def intersect(A;B):
reduce A[] as $x (false; if . then . else (B|index($x)) end) | not | not;</
'''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:
Line 1,307:
end
end;
</syntaxhighlight>
'''Examples''':
<
[["A", "B"], ["C","D"]],
[["A","B"], ["B","D"]],
Line 1,319:
tests | to_set | consolidate;
test</
{{Out}}
<
[["A","B"],["C","D"]]
[["A","B","D"]]
[["A","B","C","D"]]
[["A","B","C","D"],["F","G","H","I","K"]]</
=={{header|Julia}}==
Line 1,331:
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.
<syntaxhighlight lang="julia">
function consolidate{T}(a::Array{Set{T},1})
1 < length(a) || return a
Line 1,350:
return c
end
</syntaxhighlight>
'''Main'''
<syntaxhighlight lang="julia">
p = Set(["A", "B"])
q = Set(["C", "D"])
Line 1,371:
println("consolidate([p, q, r, s, t]) =\n ",
consolidate([p, q, r, s, t]))
</syntaxhighlight>
{{out}}
Line 1,391:
=={{header|Kotlin}}==
<
fun<T : Comparable<T>> consolidateSets(sets: Array<Set<T>>): Set<Set<T>> {
Line 1,425:
)
for (sets in unconsolidatedSets) println(consolidateSets(sets))
}</
{{out}}
Line 1,436:
=={{header|Lua}}==
<
function T(t) return setmetatable(t, {__index=table}) end
function S(t) local s=T{} for k,v in ipairs(t) do s[v]=v end return s end
Line 1,473:
example:consolidate():each(function(set) set:keys():dump() end)
print("")
end</
{{out}}
<pre>Given input sets:
Line 1,506:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
Block[{pairs, unique},
pairs =
Line 1,514:
unique = Complement[Range@Length@x, Flatten@pairs];
Join[Union[Flatten[x[[#]]]] & /@ pairs, x[[unique]]]]
consolidate[x__] := FixedPoint[reduce, {x}]</
<pre>consolidate[{a, b}, {c, d}]
-> {{a, b}, {c, d}}
Line 1,526:
=={{header|Nim}}==
{{trans|Python}}
<
if len(sets) < 2:
return @sets
Line 1,540:
echo consolidate({'A', 'B'}, {'B', 'D'})
echo consolidate({'A', 'B'}, {'C', 'D'}, {'D', 'B'})
echo consolidate({'H', 'I', 'K'}, {'A', 'B'}, {'C', 'D'}, {'D', 'B'}, {'F', 'G', 'H'})</
{{out}}
Line 1,552:
=={{header|OCaml}}==
<
List.fold_left (fun acc v ->
if List.mem v acc then acc else v::acc
Line 1,591:
print_sets (consolidate [["H";"I";"K"]; ["A";"B"]; ["C";"D"]; ["D";"B"];
["F";"G";"H"]]);
;;</
{{out}}
Line 1,600:
=={{header|ooRexx}}==
<
* 04.08.2013 Walter Pachl using ooRexx features
* (maybe not in the best way -improvements welcome!)
Line 1,715:
End
End
Return strip(ol)</
{{out}}
<pre>
Line 1,747:
=={{header|PARI/GP}}==
<
my(v,u,s);
for(i=1,#V,
Line 1,758:
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;
Line 1,808:
}
return @result;
}</
{{out}}
<pre>### Example 1: [
Line 1,856:
=={{header|Phix}}==
Using strings to represent sets of characters
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">has_intersection</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">set1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">set2</span><span style="color: #0000FF;">)</span>
Line 1,892:
<span style="color: #0000FF;">?</span><span style="color: #000000;">consolidate</span><span style="color: #0000FF;">({</span><span style="color: #008000;">"AB"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"CD"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"DB"</span><span style="color: #0000FF;">})</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">consolidate</span><span style="color: #0000FF;">({</span><span style="color: #008000;">"HIK"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"AB"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"CD"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"DB"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"FGH"</span><span style="color: #0000FF;">})</span>
<!--</
{{out}}
<pre>
Line 1,903:
=={{header|PicoLisp}}==
{{trans|Python}}
<
(when S
(let R (cons (car S))
Line 1,910:
(set R (uniq (conc X (car R))))
(conc R (cons X)) ) )
R ) ) )</
Test:
<
-> ((A B) (C D))
: (consolidate '((A B) (B D)))
Line 1,919:
-> ((D B C A))
: (consolidate '((H I K) (A B) (C D) (D B) (F G H)))
-> ((F G H I K) (D B C A))</
=={{header|PL/I}}==
<
declare set(20) character (200) varying;
declare e character (1);
Line 1,979:
end print;
end Set;</
<pre>
The original sets: {A,B}
Line 2,000:
=={{header|Python}}==
===Python: Iterative===
<
setlist = [s for s in sets if s]
for i, s1 in enumerate(setlist):
Line 2,010:
s1.clear()
s1 = s2
return [s for s in setlist if s]</
===Python: Recursive===
<
if len(s) < 2: return s
Line 2,020:
if r[0].intersection(x): r[0].update(x)
else: r.append(x)
return r</
===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):
Line 2,057:
if __name__ == '__main__':
_test(consolidate)
_test(conso)</
{{out}}
Line 2,070:
{{Trans|JavaScript}}
{{Works with|Python|3.7}}
<
from functools import (reduce)
Line 2,142:
# MAIN ---
if __name__ == '__main__':
main()</
{{Out}}
<pre>Consolidation of sets of characters:
Line 2,151:
=={{header|Racket}}==
<
#lang racket
(define (consolidate ss)
Line 2,166:
(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)))
</syntaxhighlight>
{{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))
</syntaxhighlight>
=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku"
multi consolidate(Set \this is copy, *@those) {
gather {
Line 2,193:
[set(A,B), set(B,D)],
[set(A,B), set(C,D), set(D,B)],
[set(H,I,K), set(A,B), set(C,D), set(D,B), set(F,G,H)];</
{{out}}
<pre>set(A, B) set(C, D)
Line 2,205:
=={{header|REXX}}==
<
@.=; @.1 = '{A,B} {C,D}'
@.2 = "{A,B} {B,D}"
Line 2,256:
say ' the new set=' new; say
return</
{{out|output|text= when using the (internal) default supplied sample sets:}}
<pre>
Line 2,276:
=={{header|Ring}}==
<
# Project : Set consolidation
Line 2,315:
consolidate = s + " = " + substr(list2str(sets),nl,",")
return consolidate
</syntaxhighlight>
Output:
<pre>
Line 2,325:
=={{header|Ruby}}==
<
tests = [[[:A,:B], [:C,:D]],
Line 2,337:
end
p sets
end</
{{out}}
<pre>
Line 2,348:
=={{header|Scala}}==
<
def consolidate[Type](sets: Set[Set[Type]]): Set[Set[Type]] = {
var result = sets // each iteration combines two sets and reiterates, else returns
Line 2,374:
})
}</
{{out}}
<pre>{A,B} {C,D} -> {A,B} {C,D}
Line 2,383:
=={{header|Sidef}}==
{{trans|Raku}}
<
func consolidate(this, *those) {
gather {
Line 2,407:
].each { |ss|
say (format(ss), "\n\t==> ", format(consolidate(ss...)));
}</
{{out}}
<pre>
Line 2,424:
This is not a particularly efficient solution, but it gets the job done.
<syntaxhighlight lang="sql">
/*
This code is an implementation of "Set consolidation" in SQL ORACLE 19c
Line 2,519:
;
/
</syntaxhighlight>
{{out}}
Line 2,542:
{{tcllib|struct::set}}
This uses just the recursive version, as this is sufficient to handle substantial merges.
<
proc consolidate {sets} {
Line 2,559:
}
return [lset r 0 $r0]
}</
Demonstrating:
<
puts 2:[consolidate {{A B} {B D}}]
puts 3:[consolidate {{A B} {C D} {D B}}]
puts 4:[consolidate {{H I K} {A B} {C D} {D B} {F G H}}]</
{{out}}
<pre>1:{A B} {C D}
Line 2,575:
Original solution:
<
(defun fnd (p x) (if (eq [p x] x) x (fnd p [p x])))
Line 2,599:
((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)))</
{{out}}
Line 2,609:
{{trans|Racket}}
<
(defun empty-p (set) (zerop (hash-count set)))
Line 2,628:
((h i k) (a b) (c d) (d b) (f g h)))))
(format t "~s -> ~s\n" test
[mapcar hash-keys (consoli [mapcar mkset test])]))</
{{out}}
Line 2,639:
{{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
Line 2,703:
show consolidate(ms(Array(mc("AB"), mc("CD"), mc("DB"))))
show consolidate(ms(Array(mc("HIK"), mc("AB"), mc("CD"), mc("DB"), mc("FGH"))))
End Sub</
<pre>{{A, B}, {C, D}}
{{A, B, D}}
Line 2,710:
=={{header|VBScript}}==
<syntaxhighlight lang="vb">
Function consolidate(s)
sets = Split(s,",")
Line 2,744:
WScript.StdOut.WriteLine consolidate(t)
Next
</syntaxhighlight>
{{Out}}
Line 2,760:
As Sets are Map-based, iteration (and hence printing) order are undefined.
<
var consolidateSets = Fn.new { |sets|
Line 2,797:
System.print("Unconsolidated: %(sets)")
System.print("Cosolidated : %(consolidateSets.call(sets))\n")
}</
{{out}}
Line 2,816:
=={{header|zkl}}==
{{trans|Tcl}}
<
if(sets.len()<2) return(sets);
r,r0 := List(List()),sets[0];
Line 2,826:
r[0]=r0;
r
}</
<
sets.apply("concat"," ").pump(String,"(%s),".fmt)[0,-1]
}
Line 2,842:
prettize(sets).print(" --> ");
consolidate(sets) : prettize(_).println();
}</
{{out}}
<pre>
|