Set consolidation: Difference between revisions
(Go solution) |
No edit summary |
||
Line 39: | Line 39: | ||
Is the two sets: |
Is the two sets: |
||
{'A', 'C', 'B', 'D'}, and {'G', 'F', 'I', 'H', 'K'} |
{'A', 'C', 'B', 'D'}, and {'G', 'F', 'I', 'H', 'K'} |
||
=={{header|Ela}}== |
|||
This solution emulate sets using linked lists: |
|||
<lang ela>open Core |
|||
let merge [] ys = ys |
|||
merge (x::xs) ys | x `elem` ys = merge xs ys |
|||
| else = merge xs (x::ys) |
|||
let consolidate (_::[])@xs = xs |
|||
consolidate (x::xs) = conso [x] (consolidate xs) |
|||
where conso xs [] = xs |
|||
conso (x::xs)@r (y::ys) | intersect x y <> [] = conso ((merge x y)::xs) ys |
|||
| else = conso (r ++ [y]) ys</lang> |
|||
Usage: |
|||
In this example sets are filled with variants (somewhat similar to atoms in Lisp). One can use any other values (such as strings or chars) as well. |
|||
<lang ela>open Con |
|||
consolidate [[H,I,K], [A,B], [C,D], [D,B], [F,G,H]] |> writen $ |
|||
consolidate [[A,B], [B,D]] |> writen |
|||
</lang> |
|||
{{out}} |
|||
<pre>[[K,I,F,G,H],[A,C,D,B]] |
|||
[[A,B,D]]</pre> |
|||
=={{header|Go}}== |
=={{header|Go}}== |
Revision as of 09:27, 10 May 2012
You are encouraged to solve this task according to the task description, using any language you may know.
See also:
Given two sets of items then if any item is common to any set then the result of applying consolidation to those sets is:
- The two input sets if no common item exists between those two sets of items.
- Or one set of all the items from both sets if they share a common item.
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. If N<2 then consolidation has no meaning and the input can be returned.
Example 1:
Given the two sets {A,B} and {C,D} then there is no common element between the sets and the result is the same as the input.
Example 2:
Given the two sets {A,B} and {B,D} then there is a common element B between the sets and the result is the set {B,D,A}. (Note that order of items in a set is immaterial - {A,B,D} is the same as {B,D,A} and {D,A,B} etc).
Example 3:
Given the three sets {A,B} and {C,D} and {D,B} then there is no common element between the sets {A,B} and {C,D} but the sets {A,B} and and {D,B} do share a common element that consolidates to produce the result {B,D,A}. On examining this result with the remaining set {C,D} they share a common element and so consolidate to the final output of the single set {A,B,C,D}
Example 4:
The consolidation of the five sets: {H,I,K}, {A,B}, {C,D}, {D,B}, and {F,G,H} Is the two sets: {'A', 'C', 'B', 'D'}, and {'G', 'F', 'I', 'H', 'K'}
Ela
This solution emulate sets using linked lists:
<lang ela>open Core
let merge [] ys = ys
merge (x::xs) ys | x `elem` ys = merge xs ys | else = merge xs (x::ys)
let consolidate (_::[])@xs = xs
consolidate (x::xs) = conso [x] (consolidate xs) where conso xs [] = xs conso (x::xs)@r (y::ys) | intersect x y <> [] = conso ((merge x y)::xs) ys | else = conso (r ++ [y]) ys</lang>
Usage:
In this example sets are filled with variants (somewhat similar to atoms in Lisp). One can use any other values (such as strings or chars) as well.
<lang ela>open Con
consolidate [[H,I,K], [A,B], [C,D], [D,B], [F,G,H]] |> writen $ consolidate [[A,B], [B,D]] |> writen </lang>
- Output:
[[K,I,F,G,H],[A,C,D,B]] [[A,B,D]]
Go
<lang go>package main
import "fmt"
type set map[string]bool
var testCase = []set{
set{"H": true, "I": true, "K": true}, set{"A": true, "B": true}, set{"C": true, "D": true}, set{"D": true, "B": true}, set{"F": true, "G": true, "H": true},
}
func main() {
fmt.Println(consolidate(testCase))
}
func consolidate(sets []set) []set {
setlist := []set{} for _, s := range sets { if s != nil && len(s) > 0 { setlist = append(setlist, s) } } for i, s1 := range setlist { if len(s1) > 0 { for _, s2 := range setlist[i+1:] { if s1.disjoint(s2) { continue } for e := range s1 { s2[e] = true delete(s1, e) } s1 = s2 } } } r := []set{} for _, s := range setlist { if len(s) > 0 { r = append(r, s) } } return r
}
func (s1 set) disjoint(s2 set) bool {
for e := range s2 { if s1[e] { return false } } return true
}</lang>
- Output:
[map[A:true C:true B:true D:true] map[G:true F:true I:true H:true K:true]]
Python
Iterative
The docstring contains solutions to all the examples as well as a check to show the order-independence of the sets given to the consolidate function. <lang python>def consolidate(sets):
>>> # Define some variables >>> A,B,C,D,E,F,G,H,I,J,K = 'A,B,C,D,E,F,G,H,I,J,K'.split(',') >>> # Consolidate some lists of sets >>> 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', 'C', 'B', 'D'}] >>> consolidate([{H,I,K}, {A,B}, {C,D}, {D,B}, {F,G,H}]) [{'A', 'C', 'B', 'D'}, {'G', 'F', 'I', 'H', 'K'}] >>> consolidate([{A,H}, {H,I,K}, {A,B}, {C,D}, {D,B}, {F,G,H}]) [{'A', 'C', 'B', 'D', 'G', 'F', 'I', 'H', 'K'}] >>> consolidate([{H,I,K}, {A,B}, {C,D}, {D,B}, {F,G,H}, {A,H}]) [{'A', 'C', 'B', 'D', 'G', 'F', 'I', 'H', 'K'}] >>> # Confirm order-independence >>> from copy import deepcopy >>> import itertools >>> sets = [{H,I,K}, {A,B}, {C,D}, {D,B}, {F,G,H}, {A,H}] >>> answer = consolidate(deepcopy(sets)) >>> for perm in itertools.permutations(sets): assert consolidate(deepcopy(perm)) == answer
>>> answer [{'A', 'C', 'B', 'D', 'G', 'F', 'I', 'H', 'K'}] >>> len(list(itertools.permutations(sets))) 720 >>> setlist = [s for s in sets if s] for i, s1 in enumerate(setlist): if s1: for s2 in setlist[i+1:]: intersection = s1.intersection(s2) if intersection: s2.update(s1) s1.clear() s1 = s2 return [s for s in setlist if s]
</lang>
Recursive
<lang python>def conso(s): if len(s) < 2: return s
r, b = [s[0]], conso(s[1:]) for x in b: if r[0].intersection(x): r[0].update(x) else: r.append(x) return r </lang>