Name that set operation!

sets.clj

; I'm hoping to find a common name for a particular operation over sets that I've
; been thinking of as a "join" of sorts.
; 
; It's _not_ a relational join -- the values involved aren't relations (for me
; at the moment, they're actually graphs essentially representing
; disjoint recursive sets, but I think that's probably irrelevant
; detail) -- but it feels like it's in the spirit of a full outer join
;
;     Given N sets, recursively produce all unions of those sets that are disjoint.
;
; Does this operation have a name?

(defn- all-pairs [xs]
  (when-let [next (next xs)]
    (concat
     (map list (repeat (first xs)) next)
     (all-pairs next))))

(defn disjoint? [s1 s2]
  (empty? (clojure.set/intersection s1 s2)))

(defn join [sets]
  (let [new (->> (all-pairs sets)
                 (filter (partial apply disjoint?))
                 (map (partial apply clojure.set/union))
                 set)]
    (clojure.set/union
     sets
     (if (seq new)
       (join new)
       new))))

user> (join #{#{:a :b} #{:a :c}
              #{:d :e} #{:d :f}})
#{#{:c :d :f :a} #{:b :a} #{:c :a} #{:d :f} #{:e :d} #{:b :d :f :a} #{:e :c :d :a} #{:e :b :d :a}}
; just for readability's sake
user> (doseq [x (map (partial apply sorted-set) *1)]
        (println x))
#{:a :c :d :f}
#{:a :b}
#{:a :c}
#{:d :f}
#{:d :e}
#{:a :b :d :f}
#{:a :c :d :e}
#{:a :b :d :e}

I'm confused by #{:a :b :e :f} (for example) being missing from output. If I'm understanding, I have a hunch there are too many moving parts for a single set operation name: combinations + filter for disjoint + union? Confidence is low based on description + output that I'm understanding, though.

Ack, sorry, this is what happens when you dummy up data (my impl assumes the values are graphs with a particular structure, so the snippet in the gist was fabricated). I'll make an independent impl that will hopefully clarify things.

Yeah, I wouldn't be surprised if there's no common name for this. As another Colin mentioned on twitter, this is almost a powerset relation, which maybe is a useful pointer for someone. I re-skimmed powerset materials, and didn't come up with anything adjacent though.

Updated with a quickie generalized impl, and a much better example. Sorry for botching the fabricated example!

Seems natural to think of this as being about bags/multisets instead of sets - and you're restricting your domain to those without repeats.

Then think of union as partial function, no longer defined for sets which intersect.

Then you could say the object you're interested is the set of all elementss rechable by this "not always defined" union, or..

The closure of X with respect to union, in the space of multisets with no repeated elements

The "closure" term seems to best capture your recursive notion, and your metaphor of the scheduler sounded like making certain combinations invalid, ie. "function with restricted domain".

Does this pass the quiz? "Name that multi-set operation!" 😄

If it's a product (like outer join) then join : {X} -> X, but that's not really what we're seeing since it's more like join : X -> X. I agree with @crisptrutski that it's more of a closure-like operator. But that isn't quite the right idea either since we expect closure to be idempotent, join . join = join, but that's not true

user=> (join #{#{1 2} #{3 4} #{5 6}})
#{#{4 3} #{4 6 3 5} #{1 4 3 2} #{6 5} #{1 6 2 5} #{1 2}}
user=> (join (join #{#{1 2} #{3 4} #{5 6}}))
#{#{4 3} #{4 6 3 5} #{1 4 3 2} #{1 4 6 3 2 5} #{6 5} #{1 6 2 5} #{1 2}}

But this might just be a bug in join? Do you actually mean it to be

(defn join1 [sets]
  (->> (all-pairs sets)
       (filter (partial apply disjoint?))
       (map (partial apply clojure.set/union))
       set
       (clojure.set/union sets))

iterated until stable? That's clearly a closure operation if it ever stabilizes. Does it necessarily stabilize? Yes, since it clearly adds no more elements than (->> sets all-pairs (map #(apply union %)) set (union sets)) which just "completes the union/contains lattice" and it's easy to prove termination.

So if my fix is right then you could say it's the closure under "non-touching unions".