在Clojure中，如何将排序的整数数组分成连续的分区？

huangapple
go评论88阅读模式
英文:

In clojure how to partition an array of sorted integers into contiguous partitions?

问题

以下是翻译好的部分：

"I'd like to partition an array of sorted integers into contiguous partitions."

"我想将一个已排序的整数数组分成连续的分区。"

"The following ruby:"

"下面的 Ruby 代码："

"Outputs:"

"输出："

"How can I do this in clojure?"

"我怎样在 Clojure 中实现这个？"

"I tried using partition-by, but AFAIK it only takes one argument."

"我尝试使用 partition-by，但据我所知它只接受一个参数。"

英文:

I'd like to partition an array of sorted integers into contiguous partitions.

The following ruby:

  1. [1,2,3,8,9,10,99].slice_when { |x, y| y > x + 1 }.to_a

Outputs:

  1. [[1, 2, 3], [8, 9, 10], [99]]

How can I do this in clojure?

I tried using partition-by, but AFAIK it only takes one argument.

答案1

得分: 4

你必须在某个地方保存上一个元素。在这种情况下，你可以这样做：

  1. (defn slice [coll]
  2.   (let [prev (atom (first coll))]
  3.     (->> coll
  4.          (partition-by #(> (inc @prev) (reset! prev %))))))
  6. (slice [1 2 3 8 9 10 99])
  7. => ((1 2 3) (8 9 10) (99))

如果你还想提供这个函数，你将需要编写一个基于reduce的解决方案：

  1. (defn slice-when [pred coll]
  2.   (->> coll
  3.        (reduce (fn [acc current]
  4.                  (if-let [previous (peek (peek acc))]
  5.                    (if (pred previous current)
  6.                      (conj acc [current])
  7.                      (conj (pop acc) (conj (peek acc) current)))
  8.                    (conj acc [current])))
  9.                [])))

示例：

  1. (slice-when (fn [x y] (> y (inc x))) 
  2.             [1 2 3 8 9 10 99])
  3. => [[1 2 3] [8 9 10] [99]]
英文:

You have to save somewhere that previous element. In this case, you can do:

  1. (defn slice [coll]
  2.   (let [prev (atom (first coll))]
  3.     (->> coll
  4.          (partition-by #(< (inc @prev) (reset! prev %))))))
  6. (slice [1 2 3 8 9 10 99])
  7. => ((1 2 3) (8 9 10) (99))

If you also want to provide that function, you will have to write some reduce-based solution:

  1. (defn slice-when [pred coll]
  2.   (->> coll
  3.        (reduce (fn [acc current]
  4.                  (if-let [previous (peek (peek acc))]
  5.                    (if (pred previous current)
  6.                      (conj acc [current])
  7.                      (conj (pop acc) (conj (peek acc) current)))
  8.                    (conj acc [current])))
  9.                [])))

Example:

  1. (slice-when (fn [x y] (> y (inc x))) 
  2.             [1 2 3 8 9 10 99])
  3. => [[1 2 3] [8 9 10] [99]]

答案2

得分: 1

你也可以标记所有的分割点，然后只是根据它们进行分区。

  1. (defn split-when [pred data]  
  2.   (when-let [[x & xs] (seq data)]
  3.     (->> (mapcat (fn [a b] (if (pred a b) [::split b] [b])) 
  4.                  data xs)
  5.          (cons x)
  6.          (partition-by #{::split})
  7.          (take-nth 2))))

用户> (split-when (complement (comp #{-1} -)) [1 5 6 7 9 10 22])
;;=> ((1) (5 6 7) (9 10) (22))

或者，你可以收集应该分割的所有索引，并传递给subvec：

  1. (defn split-when [pred data]   
  2.   (when (seq data)
  3.     (let [splits (keep-indexed (fn [i [a b]] (when (pred a b) (inc i)))
  4.                                (partition 2 1 data))
  5.           indices `[0 ~@splits ~(count data)]]
  6.       (map (partial subvec (vec data)) indices (rest indices)))))

用户> (split-when (complement (comp #{-1} -)) [1 5 6 7 9 10 22])
;;=> (1 [5 6 7] [9 10] [22])

英文:

you could also mark all the split points, and then just partition with them

  1. (defn split-when [pred data]  
  2.   (when-let [[x & xs] (seq data)]
  3.     (->> (mapcat (fn [a b] (if (pred a b) [::split b] [b])) 
  4.                  data xs)
  5.          (cons x)
  6.          (partition-by #{::split})
  7.          (take-nth 2))))
  1. user> (split-when (complement (comp #{-1} -)) [1 5 6 7 9 10 22])
  2. ;;=> ((1) (5 6 7) (9 10) (22))

otherwise you can collect all the indices where you should split and pass over to subvec:

  1.  (defn split-when [pred data]   
  2.    (when (seq data)
  3.      (let [splits (keep-indexed (fn [i [a b]] (when (pred a b) (inc i)))
  4.                                 (partition 2 1 data))
  5.            indices `[0 ~@splits ~(count data)]]
  6.        (map (partial subvec (vec data)) indices (rest indices)))))
  1. user> (split-when (complement (comp #{-1} -)) [1 5 6 7 9 10 22])
  2. ;;=> ([1] [5 6 7] [9 10] [22])

答案3

得分: 1

以下是您提供的内容的中文翻译部分：

我编写了一个通用版本，如下所示。

它将数据向量分割为所有可能的点，将子向量传递给类似于以下的谓词函数：

  1. (fn [data1 data2] ...)

它跟踪所有谓词返回 true 的索引，然后使用 reduce 和 subvec 来累积结果。我包含了一个单元测试。

  1. (ns tst.demo.core
  2.   (:use demo.core tupelo.core tupelo.test))
  4. ; 我们使用 `split-at` 来对集合进行分区。对于像 [0 1 2] 这样的集合，
  5. ; 提供像 {:data1 [] :data2 [0 1 2]} 或 {:data1 [0 1 2] :data2 []} 这样的退化分割是没有意义的。
  6. ; 因此，我们需要在范围 [1..(N-1)] 内找到分割点
  7. (verify
  8.   (let [data   [0 1 2]
  9.         N      (count data)
  10.         result (forv [i (thru N)]
  11.                  (let [[data1 data2] (split-at i data)]
  12.                    (vals->map i data1 data2)))]
  14.     (is= result
  15.       [{:i 0 :data1 [] :data2 [0 1 2]}
  16.        {:i 1 :data1 [0] :data2 [1 2]}
  17.        {:i 2 :data1 [0 1] :data2 [2]}
  18.        {:i 3 :data1 [0 1 2] :data2 []}])))

因此，我们避免了 data1 或 data2 中的一个为空向量的退化情况。

  1. (defn partition-when
  2.   [pred coll]
  3.   (let [data       (vec coll)
  4.         N          (count data)
  5.         N-1        (dec N)
  6.         ; 我们使用 `split-at` 来对集合进行分区。对于像 [0 1 2] 这样的集合，
  7.         ; 提供像 {:data1 [] :data2 [0 1 2]} 或 {:data1 [0 1 2] :data2 []} 这样的退化分割是没有意义的。
  8.         ; 因此，我们需要在范围 [1..(N-1)] 内找到分割点
  9.         split-idxs (loop [i    1
  10.                           idxs []]
  11.                      (if-not (< i N-1)
  12.                        idxs
  13.                        (let [[data1 data2] (split-at i data)
  14.                              split?      (pred data1 data2)
  15.                              result-next (if split?
  16.                                            (append idxs i)
  17.                                            idxs)
  18.                              i-next      (inc i)]
  19.                          (recur i-next result-next))))
  20.         ; 由于我们使用 `subvec`，我们必须在向量的开始/结束添加“默认”值
  21.         split-idxs (glue [0] split-idxs [N])
  22.         idx-pairs  (partition 2 1 split-idxs)
  23.         subvecs    (reduce (fn [cum [start end]]
  24.                              (let [next-part (subvec data start end)
  25.                                    next-cum  (append cum next-part)]
  26.                                next-cum))
  27.                      []
  28.                      idx-pairs)]
  29.     subvecs))

以及单元测试。请注意，谓词函数必须负责从 data1 和 data2 中获取单个元素。

  1. (verify
  2.   (let [split-fn (fn [data1 data2]
  3.                    (let [x (last data1)
  4.                          y (first data2)]
  5.                      (< (inc x) y)))]
  6.     (is= [[1 2 3] [8 9 10] [99]]
  7.       (partition-when split-fn
  8.         [1 2 3 8 9 10 99]))))

这个函数现在是 Tupelo 库的一部分。

英文:

I wrote a general version shown below.

It splits the data vector at all possible points, presenting the sub-vectors to a predicate function that looks like:

  1. (fn [data1 data2] ...)

It keeps track of all the indexes where the pred returns true, then uses reduce and subvec to accumulate the result. I've included a unit test.

  1. (ns tst.demo.core
  2.   (:use demo.core tupelo.core tupelo.test))
  4. ; We use `split-at` to partition the coll. Given a coll like [0 1 2], it makes
  5. ; no sense to give degenerate splits like {:data1 [] :data2 [0 1 2]}
  6. ; or {:data1 [0 1 2] :data2 []}. So, we need the split point in the range [1..(N-1)]
  7. (verify
  8.   (let [data   [0 1 2]
  9.         N      (count data)
  10.         result (forv [i (thru N)]
  11.                  (let [[data1 data2] (split-at i data)]
  12.                    (vals-&gt;map i data1 data2)))]
  13.     (is= result
  14.       [{:i 0 :data1 [] :data2 [0 1 2]}
  15.        {:i 1 :data1 [0] :data2 [1 2]}
  16.        {:i 2 :data1 [0 1] :data2 [2]}
  17.        {:i 3 :data1 [0 1 2] :data2 []}])))

So, we avoid the degenerate case where either data1 or data2 is the empty vector.

  1. (defn partition-when
  2.   [pred coll]
  3.   (let [data       (vec coll)
  4.         N          (count data)
  5.         N-1        (dec N)
  6.         ; We use `split-at` to partition the coll. Given a coll like [0 1 2], it makes
  7.         ; no sense to give degenerate splits like {:data1 [] :data2 [0 1 2]}
  8.         ; or {:data1 [0 1 2] :data2 []}. So, we need the split point in the range [1..(N-1)]
  9.         split-idxs (loop [i    1
  10.                           idxs []]
  11.                      (if-not (&lt;= i N-1)
  12.                        idxs
  13.                        (let [[data1 data2] (split-at i data)
  14.                              split?      (pred data1 data2)
  15.                              result-next (if split?
  16.                                            (append idxs i)
  17.                                            idxs)
  18.                              i-next      (inc i)]
  19.                          (recur i-next result-next))))
  20.         ; Since we are using `subvec`, we must add in the &quot;default&quot; values at the
  21.         ; start/end of the vector
  22.         split-idxs (glue [0] split-idxs [N])
  23.         idx-pairs  (partition 2 1 split-idxs)
  24.         subvecs    (reduce (fn [cum [start end]]
  25.                              (let [next-part (subvec data start end)
  26.                                    next-cum  (append cum next-part)]
  27.                                next-cum))
  28.                      []
  29.                      idx-pairs)]
  30.     subvecs))

and the unit test. Notice the predicate function must take responsibility for pulling individual elements out of data1 and data2

  1. (verify
  2.   (let [split-fn (fn [data1 data2]
  3.                    (let [x (last data1)
  4.                          y (first data2)]
  5.                      (&lt; (inc x) y)))]
  6.     (is= [[1 2 3] [8 9 10] [99]]
  7.       (partition-when split-fn
  8.         [1 2 3 8 9 10 99])))
  9.   )

This function is now part of the Tupelo library.

答案4

得分: 0

我觉得这个解决方案非常简洁：

  1. (defn partition-contiguous [numbers]
  2.   (->> numbers
  3.        (partition-by identity)
  4.        (map-indexed cons)
  5.        (partition-by (fn [[x y]] (- x y)))
  6.        (map #(mapcat rest %))))
  8. (partition-contiguous [1 2 3 3 8 9 9 10 10 99])
  9. ;; => ((1 2 3 3) (8 9 9 10 10) (99))
英文:

I find this solution pretty concise:

  1. (defn partition-contiguous [numbers]
  2.   (-&gt;&gt; numbers
  3.        (partition-by identity)
  4.        (map-indexed cons)
  5.        (partition-by (fn [[x y]] (- x y)))
  6.        (map #(mapcat rest %))))
  8. (partition-contiguous [1 2 3 3 8 9 9 10 10 99])
  9. ;; =&gt; ((1 2 3 3) (8 9 9 10 10) (99))

答案5

得分: 0

The library dev.weavejester/medley ("一个小而有用的函数集合，大多数函数在 clojure.core 命名空间中都不会显得不合适") 自 1.7.0 版本以来包含了 partition-between 函数。该函数可用于将已排序的集合划分为连续的分区：

  1. (require '[medley.core :refer [partition-between]])
  3. (partition-between (fn [x y] (> y (inc x))) [1 2 3 8 9 10 99])
  4. ;; => ((1 2 3) (8 9 10) (99))
英文:

The library dev.weavejester/medley ("A small collection of useful, mostly pure functions that might not look out of place in the clojure.core namespace") contains partition-between since 1.7.0. That function can be used to partition a sorted collection into contiguous partitions:

  1. (require &#39;[medley.core :refer [partition-between]])
  3. (partition-between (fn [x y] (&gt; y (inc x))) [1 2 3 8 9 10 99])
  4. ;; =&gt; ((1 2 3) (8 9 10) (99))

huangapple
  • 本文由 发表于 2023年3月3日 22:03:40
  • 转载请务必保留本文链接：https://go.coder-hub.com/75628071.html
  • clojure
  • ruby
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定