6

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]。

もちろん、これを行う1つの方法は、完全なデカルト積を見つけてから問題のあるアイテムを削除することですが、最初からソリューションをチェックしないようにするなど、より効率的な方法が必要です。

カート製品の各用語を段階的に構築する初期ソリューションがあり、各段階で、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))))))))
4

3 に答える 3

2

ここでcore.logic（素朴な）アプローチ

(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 ミリ秒です。

于 2013-11-29T11:19:00.727 に答える