忽略项的高效笛卡尔积算法

Question

假设我有集合A_1,...A_n，例如[[a b c][d e][f]]。我想找到这些集合的笛卡尔积，但不包括任何超集的元素在某些忽略列表中。

例如，如果我的忽略列表是[[a e][c]]，笛卡尔积的结果将是[[a d f][b d f][b e f]]。请注意，任何带有c的项都不在其中，[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))))))))

- zenna

Answer 1

我认为在您目前的方法上有些改进可以进行。但首先，我们需要实现一个基本的cartisian-product。然后我们可以将其适应为接受一个忽略列表。这很容易使用for和一些递归实现：

(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))

很好。既然我们使用for，我们就有了懒惰的优势。如果您希望结果不是一个序列的序列，那么将其转换为其他内容很容易。

现在，难点在于实现忽略集。根据您的描述，您当前的方法是，如果将元素添加到正在构建的术语中会导致该术语成为任何忽略集的超集，则从A_i中删除这些元素。正如您的代码所示，这不仅有点低效（例如，superset?相对于其第一个参数的大小是最坏情况下线性时间），而且使代码比必要的复杂。

因此，让我们采用不同的方法。我们不是从A_i中删除元素，而是从忽略集中删除我们添加到术语中的任何元素。然后，如果任何忽略集为空，我们可以修剪一个术语。额外的好处是，这仅需要对先前的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 s e))
                                                         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))

当然，根据您的实际需求可能需要进行一些微小的更改。例如，您可能希望将忽略集作为向量或序列接受，并在内部转换为集。但这就是算法的本质。

- Nathan Davis

---

这个算法真的很棒！ - Leon Grapenthin

这似乎没有解决 OP 的问题。即，工作量在最坏情况下与未修剪的笛卡尔积大小成比例，这可能比最终答案的大小多几倍。 - n. m.

@n.m，我认为这里呈现的最终算法完成的工作应该与最终答案的大小成比例。你为什么认为它不是呢？ - Nathan Davis

Answer 2

这里提供一个核心逻辑（天真）的方法。

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

              )
       )

==> ([:a :d :f] [:b :d :f] [:b :e :f])

尽管它比@Nathan_Davis的算法慢得多，需要23.263毫秒而不是0.109毫秒。

- tangrammer

Answer 3

请查看clojure.math.combinatorics

- Hendekagon

---

我在 clojure.math.combinatorics 中没有看到任何允许跳过某些项的函数。 - Nathan Davis

抱歉，我没有仔细阅读问题 - 这是在math.combinatorics中很好的一个功能。 - Hendekagon

没问题。而且嘿，作为开源项目，也许你可以添加它 - 这样就是一个正确的答案了;-) - Nathan Davis