Clojure：根据值序列对序列进行分区

Question

我想要根据值序列来对序列进行分区。

(partition-by-seq [3 5] [1 2 3 4 5 6]) 
((1 2 3)(4 5)(6))

第一个输入是分割点序列。 第二个输入是我想要分区的序列。 因此，第一个列表将在值3（1 2 3）处进行分区，第二个分区将是（4 5），其中5是下一个分割点。

另一个例子：

(partition-by-seq [3] [2 3 4 5])
result: ((2 3)(4 5))

(partition-by-seq [2 5] [2 3 5 6])
result: ((2)(3 5)(6))

给定：第一个序列（分割点）始终是第二个输入序列的子集。

- Thomas Deutsch

---

“split-points”是什么意思？这个序列是否表示一个范围？ - Lee

分割点是用于将输入序列分区的值。 (partition-by-seq [3] [1 2 3 4 5 6]) 将得到 ((1 2 3) (4 5 6))。 - Thomas Deutsch

你尝试过什么了吗？还是你期望我们替你完成作业？ - m0skit0

谢谢您的提问。所有序列都已排序，且值是唯一的。 - Thomas Deutsch

作为一个Clojure初学者，我尝试构建一个时间管理应用程序。第一个序列是我有约会的时间点。第二个序列是空闲时间和约会开始时间的列表。 - Thomas Deutsch

Answer 1

我想到了一个解决方案，它很懒惰，但是（在我看来）非常直接。

(defn part-seq [splitters coll]
  (lazy-seq
   (when-let [s (seq coll)]
     (if-let [split-point (first splitters)]
       ; build seq until first splitter
       (let [run (cons (first s) (take-while #(<= % split-point) (next s)))]
         ; build the lazy seq of partitions recursively
         (cons run
               (part-seq (rest splitters) (drop (count run) s))))
       ; just return one partition if there is no splitter 
       (list coll)))))

如果所有的“分割点”都在序列中：

(part-seq [3 5 8] [0 1 2 3 4 5 6 7 8 9])
;;=> ((0 1 2 3) (4 5) (6 7 8) (9))

如果一些“分割点”不在序列中。

(part-seq [3 5 8] [0 1 2 4 5 6 8 9])
;;=> ((0 1 2) (4 5) (6 8) (9))

这是一个关于分割器和待分割序列的无限序列示例。

(take 5 (part-seq (iterate (partial + 3) 5) (range)))
;;=> ((0 1 2 3 4 5) (6 7 8) (9 10 11) (12 13 14) (15 16 17))

- T.Gounelle

Answer 2

要分割的序列是一个“splittee”，而分割点（又称为“splitter”）的元素标记着一个分区的最后一个元素。

从你的例子中：

splittee: [1 2 3 4 5 6]

splitter: [3 5]

结果：((1 2 3)(4 5)(6))

因为生成的分区始终是递增整数序列，而递增整数序列x可以定义为start <= x < end，因此根据该定义，可以将splitter元素转换为序列的end。

所以，从[3 5]开始，我们想要找到以4和6结尾的子序列。

然后通过添加start，splitter可以转换为[start end]序列。还使用了splittee的start和end。

因此，分割器[3 5]变为：

[[1 4] [4 6] [6 7]]

可以通过以下方式进行分割转换

(->> (concat [(first splittee)] 
              (mapcat (juxt inc inc) splitter) 
              [(inc (last splittee))])
     (partition 2)

转换后的 splitter 和期望结果之间存在良好的对称性。

[[1 4] [4 6] [6 7]]

((1 2 3) (4 5) (6))

那么问题就变成了如何从 splittee 中提取由转换后的 splitter 中的 [start end] 范围内的子序列。

clojure 有一个 subseq 函数，可以通过 start 和 end 条件在有序序列中找到子序列。我只需为每个转换后的拆分器元素映射 splittee 的 subseq。

(map (fn [[x y]]
       (subseq (apply sorted-set splittee) <= x < y))
     transformed-splitter)

通过结合上述步骤，我的答案是：

(defn partition-by-seq 
  [splitter splittee]
  (->> (concat [(first splittee)]
                (mapcat (juxt inc inc) splitter)
                [(inc (last splittee))])
       (partition 2)
       (map (fn [[x y]]
              (subseq (apply sorted-set splittee) <= x < y)))))

- mavbozo

---

哇，非常感谢。我可以从你的例子中学到很多。 - Thomas Deutsch

Answer 3

这是我想出来的解决方案。

(def a [1 2 3 4 5 6])
(def p [2 4 5])

(defn partition-by-seq [s input]
  (loop [i 0 
         t input
         v (transient [])]
    (if (< i (count s))
        (let [x (split-with #(<= % (nth s i)) t)]
          (recur (inc i) (first (rest x)) (conj! v (first x))))
      (do
        (conj! v t)
        (filter #(not= (count %) 0) (persistent! v))))))

(partition-by-seq p a)

- Thomas Deutsch