假设我有套A_1,...A_n,
例如[[a b c][d e][f]]
. 我想找到这些集合的笛卡尔积,但不包括任何作为某些忽略列表元素超集的术语。
例如,如果我的忽略列表是[[a e][c]]
,笛卡尔积的结果将是[[a d f][b d f][b e f]]
。请注意,任何带有c
is 的术语都没有,也没有[a e f]
。
当然,我可以做到这一点的一种方法是找到完整的笛卡尔积,然后删除有问题的项目,但我想要一种更有效的方法,这样我就可以避免首先检查解决方案。
我有一个初始解决方案,其中涉及逐步构建购物车产品中的每个术语,并且在每个阶段,A_i
如果将它们添加到我正在构建的术语中会导致它成为任何一个忽略的超集,我会删除任何元素。这工作得很好,并且比简单的解决方案更好,但是仍然有大量的冗余检查,这也取决于集合的呈现顺序。例如,如果[f]
在我的忽略列表中,我仍然会继续尝试创建术语,直到达到[f]
然后丢弃。
具体而言,我的 clojure 实现是
(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))))))))