Efficient Cartesian Algorithm Ignoring Terms

Question

Say I have sets A_1,...A_n, , for example. [[abc][de][f]] . I would like to find the Cartesian product of these sets, but not including any members that are supersets of the elements of some ignore list.

For example, if my ignore list is [[ae][c]] , the result of the Cartesian product will be [[adf][bdf][bef]] . Note that any member with c is not there, not a single [aef] .

Of course, one way to do this is to find the complete Cartesian product and then remove the offensive elements, but I would like a more effective way for me to avoid checking the solutions in the first place.

I have an initial solution, which includes the gradual construction of each member in the cart, and at every stage I remove any elements from A_i , if I add them to the term that I create, it will become a superset of any one of the ignored . This works great and is better than a naive solution, but there is still a lot of redundant validation, which also depends on the order in which the sets are presented. For instance. if [f] was on my ignore list, I will still try to create terms until I get to [f] and then drop it.

For clarity, my clojure implementation

 (defn first-elements "Get the first elements of a set of sets, unless ignored" [sets ignores in-ignore?] (loop [product-tuple [] sets sets] (println "sets " sets) (cond (or (nil? sets) (nil? (first sets))) product-tuple :else (if-let [set-op (remove #(in-ignore? product-tuple ignores %) (first sets))] (if (and (coll? set-op) (empty? set-op)) product-tuple (recur (conj product-tuple (first set-op)) (next sets))) product-tuple)))) (defn in-ignore? "if I add elem to this build will it become a superset of any of the ignores" [build ignores elem] (some #(clojure.set/superset? (conj (set build) elem) %) ignores)) (defn cartesian-product-ignore "All the ways to take one item from each sequence, except for ignore" [ignores original-sets] (loop [cart-prod #{} sets original-sets] (let [firsts (first-elements sets ignores in-ignore?)] (print "firsts " firsts "-cart-prod " cart-prod " sets " sets "\n") (cond (zero? (count firsts)) cart-prod (= (count sets) (count firsts)) (recur (conj cart-prod firsts) (update-in sets [(dec (count sets))] next)) :else (recur cart-prod (assoc (update-in sets [(dec (count firsts))] next) (count firsts) (original-sets (count firsts)))))))) 

Answer 1

I think there are some improvements that can be made regarding your current approach. But first, let the basic cartisian-product be implemented. Then we can adapt it to accept the ignore list. This is easy enough using for and some recursion:

 (defn cartesian-product [colls] (if (empty? colls) (list ()) (for [e (first colls) sub-product (cartesian-product (rest colls))] (cons e sub-product)))) ;; Quick test run (cartesian-product [[:a :b :c] [:d :e] [:f]]) => ((:a :d :f) (:a :e :f) (:b :d :f) (:b :e :f) (:c :d :f) (:c :e :f)) 

Good. And since we use for , we have the advantage of laziness. If you need your result as something other than a sequence of sequences, it's easy enough to convert it to something else.

Now the tricky part is implementing ignore sets. According to your description, your current approach is to remove elements from A_i, if you add them to the term that you are building, this term will become a superset of any of the ignore sets. As your code shows, this is not only somewhat inefficient (for example, superset? Is the worst linear time by the size of its first parameter), but it also makes the code more complex than necessary.

So let's take a different approach. Instead of deleting elements from A_i, we will remove any elements that we add to the term from ignore sets. Then we can trim the term if any of the ignored sets is empty. As a bonus, all that is required is a few changes to our previous implementation of cartesian-product :

 (defn cartesian-product-ignore [ignore-sets colls] (cond (some empty? ignore-sets) () ; prune (empty? colls) (list ()) ; base case :else ; recursive case (for [e (first colls) sub-product (cartesian-product-ignore (map (fn [s] (disj se)) ignore-sets) (rest colls))] (cons e sub-product)))) ;; test without any ignore sets (cartesian-product-ignore [] [[:a :b :c] [:d :e] [:f]]) => ((:a :d :f) (:a :e :f) (:b :d :f) (:b :e :f) (:c :d :f) (:c :e :f)) ;; Now the moment of truth (cartesian-product-ignore [(set [:a :e]) (set [:c])] [[:a :b :c] [:d :e] [:f]]) => ((:a :d :f) (:b :d :f) (:b :e :f)) 

Of course, small changes may be required to meet your specific needs. For example, you might want to accept ignoring sets as a vector or sequence and convert them to internal sets. But this is the essence of the algorithm.

Answer 2

Here's the key (naive) approach

 (ns testing (:refer-clojure :exclude [==]) (:use [clojure.core.logic]) ) (run* [q] (fresh [xyz] (membero x [:a :b :c]) (membero y [:d :e]) (membero z [:f]) (== q [xyz]) (!= q [:a :ez] ) (!= q [:cyz] ) ) ) ==> ([:a :d :f] [:b :d :f] [:b :e :f]) 

Although it is much slower than the @Nathan_Davis algorithm, 23.263 ms versus 0.109 ms

Answer 3

Take a look at clojure.math.combinatorics