如何识别对象的子集？

Question

我如何最好地迭代 Clojure 中的以下对象？

{
  :item-set-1 ["a" "b" "c"]
  :item-set-2 ["d" "e" "f"]
}

我想尝试识别对象的所有子集并生成如下结果：

{
 [:item-set-1 ["a"]]
 [:item-set-1 ["a" "b"]]
 [:item-set-1 ["a" "b" "c"]]
 [:item-set-1 ["b"]]
 [:item-set-1 ["b" "c"]]
 [:item-set-1 ["c"]]
 [:item-set-2 ["d"]]
 [:item-set-2 ["d" "e"]]
 [:item-set-2 ["d" "e" "f"]]
 [:item-set-1 ["e"]]
 [:item-set-1 ["e" "f"]]
 [:item-set-1 ["f"]]

 [:item-set-1 ["a"] [:item-set-2 ["d"]]]
 [:item-set-1 ["b"] [:item-set-2 ["e"]]]
 [:item-set-1 ["c"] [:item-set-2 ["f"]]]

 [:item-set-1 ["a" "b"] [:item-set-2 ["d" "e"]]]
 [:item-set-1 ["a" "b"] [:item-set-2 ["e" "f"]]]
 [:item-set-1 ["a" "b"] [:item-set-2 ["d" "f"]]]
 [:item-set-1 ["b" "c"] [:item-set-2 ["d" "e"]]]
 [:item-set-1 ["b" "c"] [:item-set-2 ["e" "f"]]]
 [:item-set-1 ["b" "c"] [:item-set-2 ["d" "f"]]]
 [:item-set-1 ["a" "c"] [:item-set-2 ["d" "e"]]]
 [:item-set-1 ["a" "c"] [:item-set-2 ["e" "f"]]]
 [:item-set-1 ["a" "c"] [:item-set-2 ["d" "f"]]]

 [:item-set-1 ["a" "b" "c"] [:item-set-2 ["d" "e" "f"]]]
}

我相信我可以使用 clojure.math.combinatorics 来识别每个键中的子集而不是整个对象。

更新：我尝试使用以下代码生成子集：

(defn generate-freq-item-set []
  (let [result [{:data (generate-string {:item-set-1 ["a" "b" "c"] :item-set-2 ["d" "e" "f"]})}]
        items (as-> () items
                    (->> (for [row result]
                           (for [data (parse-string (:data row))]
                              (for [subset (combo/subsets (second data))]
                               (conj items {(first data) subset}))))))
        frequencies (sort-by last >
                             (->> (apply concat (apply concat (apply concat items)))
                                      (frequencies)))]
      (prn frequencies)))

但这会产生以下输出，这并不是我想要的：

([{"item-set-1" ()} 1] 
 [{"item-set-2" ("d")} 1] 
 [{"item-set-1" ("a" "b" "c")} 1] 
 [{"item-set-2" ("d" "e")} 1] 
 [{"item-set-1" ("b" "c")} 1] 
 [{"item-set-2" ("d" "e" "f")} 1] 
 [{"item-set-2" ()} 1] 
 [{"item-set-1" ("a" "b")} 1] 
 [{"item-set-1" ("c")} 1] 
 [{"item-set-2" ("e")} 1] 
 [{"item-set-2" ("d" "f")} 1] 
 [{"item-set-2" ("f")} 1] 
 [{"item-set-2" ("e" "f")} 1] 
 [{"item-set-1" ("b")} 1] 
 [{"item-set-1" ("a")} 1] 
 [{"item-set-1" ("a" "c")} 1])

Answer 1

我现在没有安装clojure，但本质上，你需要这样做： 1) 将子集函数映射到每个项集。您最终将得到包含所有子集的两组。 2) 将笛卡尔积应用于这两组子集。而已。笛卡尔积取两组并输出所有可能的组合。

我下班回来并安装好 clojure 后会回复你

编辑

终于到家了，这是密码：

(require '[clojure.math.combinatorics :as combo])

(def inputdata {:item-set-1 ["a" "b" "c"] :item-set-2 ["d" "e" "f"]})

(defn subsets-without-empty [set] (filter not-empty (combo/subsets set)))

(defn to-subset-maps [kv] 
  (map (fn [v] {(key kv) v})
  (subsets-without-empty (val kv))))

(defn create-subsets [dictOfSets] (map to-subset-maps dictOfSets))

(apply combo/cartesian-product (create-subsets inputdata))

subsets-without-empty 按照您的建议获取除空子集之外的所有子集

to-subset-maps 将 {:a [1 2]} 转换为 [{:a [1]} {:a [2]} {:a [1 2]}]，即创建子集并将原始密钥传播到每个子集（您的输出格式需要）

create-subsets 仅对输入映射的每个成员应用 to-subset-maps。

最后，我们得到了一个集合中的结果。所以我们只需要打开它并传递给 cartesian-product 以获得所有组合，这就是最后一行 apply 的用武之地。现在，这个解决方案适用于任意数量的维度（或输入地图）。

Answer 2

我会按如下方式解决这个问题。

首先，我会将您拥有的初始地图拼接成一个列表，在元数据中保存有关该项目所属集合的信息。

由于无法将元数据附加到原始字符串，我们需要创建一个包装器类型：

(defrecord ItemSetElement [x])

(defn make-item-set-element [x]
  (->ItemSetElement x))

(defn unwrap-item-set-element [elem]
  (:x elem))

然后执行将初始映射转换为序列的函数，保存所需信息：

(defn wrap-element-and-save-owner [owner s]
  (with-meta (make-item-set-element s) {::owner owner}))

(defn prepare-data [data]
  (mapcat
   (fn [[key ss]]
     (map (partial wrap-element-and-save-owner key) ss))
   data))

> (prepare-data {:item-set-1 ["a" "b"], :item-set-2 ["c"]})
({:x "a"} {:x "b"} {:x "c"})

如您所见，prepare-data 的结果只是一个序列，但序列的每个元素在其元数据中都有关于 "owner" 集的信息，例如：

> (meta (first (prepare-data {:item-set-1 ["a" "b"], :item-set-2 ["c"]})))
{:user/owner :item-set-1}

有了一个序列，我们可以使用clojure.math.combinatorics/subsets生成它的所有子集：

> (require '[clojure.math.combinatorics :as combo])
nil
> (combo/subsets (prepare-data {:item-set-1 ["a" "b"], :item-set-2 ["c"]}))
(()
 ({:x "a"})
 ({:x "b"})
 ({:x "c"})
 ({:x "a"} {:x "b"})
 ({:x "a"} {:x "c"})
 ({:x "b"} {:x "c"})
 ({:x "a"} {:x "b"} {:x "c"}))

子集中的每个元素仍然有关于其 "owner" 的信息，因此我们可以轻松地将其转换为类似初始结构的结构。这是一个函数：

(defn reconstruct-item-sets [subset]
  (->> subset
       (group-by #(::owner (meta %)))
       (map (fn [[key elements]]
              [key (map unwrap-item-set-element elements)]))
       (into {})))

总结一下所有代码，包括将所有内容粘合在一起的函数：

(require '[clojure.math.combinatorics :as combo])

(defrecord ItemSetElement [x])

(defn make-item-set-element [x]
  (->ItemSetElement x))

(defn unwrap-item-set-element [elem]
  (:x elem))

(defn wrap-element-and-save-owner [owner s]
  (with-meta (make-item-set-element s) {::owner owner}))

(defn prepare-data [data]
  (mapcat
   (fn [[key ss]]
     (map (partial wrap-element-and-save-owner key) ss))
   data))

(defn reconstruct-item-sets [subset]
  (->> subset
       (group-by #(::owner (meta %)))
       (map (fn [[key elements]]
              [key (map unwrap-item-set-element elements)]))
       (into {})))

 (defn my-subsets [data]
   (->> data
        prepare-data
        combo/subsets
        (map reconstruct-item-sets)))

(def data {:item-set-1 ["a" "b"]
           :item-set-2 ["c" "d" "e"]})

> (my-subsets data)
({}
 {:item-set-1 ("a")}
 {:item-set-1 ("b")}
 {:item-set-2 ("c")}
 {:item-set-2 ("d")}
 {:item-set-2 ("e")}
 {:item-set-1 ("a" "b")}
 {:item-set-1 ("a"), :item-set-2 ("c")}
 {:item-set-1 ("a"), :item-set-2 ("d")}
 {:item-set-1 ("a"), :item-set-2 ("e")}
 {:item-set-1 ("b"), :item-set-2 ("c")}
 {:item-set-1 ("b"), :item-set-2 ("d")}
 {:item-set-1 ("b"), :item-set-2 ("e")}
 {:item-set-2 ("c" "d")}
 {:item-set-2 ("c" "e")}
 {:item-set-2 ("d" "e")}
 {:item-set-1 ("a" "b"), :item-set-2 ("c")}
 {:item-set-1 ("a" "b"), :item-set-2 ("d")}
 {:item-set-1 ("a" "b"), :item-set-2 ("e")}
 {:item-set-1 ("a"), :item-set-2 ("c" "d")}
 {:item-set-1 ("a"), :item-set-2 ("c" "e")}
 {:item-set-1 ("a"), :item-set-2 ("d" "e")}
 {:item-set-1 ("b"), :item-set-2 ("c" "d")}
 {:item-set-1 ("b"), :item-set-2 ("c" "e")}
 {:item-set-1 ("b"), :item-set-2 ("d" "e")}
 {:item-set-2 ("c" "d" "e")}
 {:item-set-1 ("a" "b"), :item-set-2 ("c" "d")}
 {:item-set-1 ("a" "b"), :item-set-2 ("c" "e")}
 {:item-set-1 ("a" "b"), :item-set-2 ("d" "e")}
 {:item-set-1 ("a"), :item-set-2 ("c" "d" "e")}
 {:item-set-1 ("b"), :item-set-2 ("c" "d" "e")}
 {:item-set-1 ("a" "b"), :item-set-2 ("c" "d" "e")})

如何识别对象的子集？

How to identify sub sets of an object?

iterator

clojure

combinatorics