Остановить и разделить сгенерированную последовательность на повторы - clojure
Я пытаюсь создать последовательность, которая будет генерировать только значения, пока не найдет следующие условия и не вернет перечисленные результаты:
кейс =
- 0 - вернуть {:origin [все сгенерировано, кроме 0]: pattern 0}
- 1 - вернуть {:origin nil:pattern [all-Generated-values] }
- Повторяемое значение - {:origin [values-before-repeat]: шаблон [values-after-repeat]
{
; n = int
; x = int
; hist - all generated values
; Keeps the head below x
(defn trim-head [head x]
(loop [head head]
(if (> head x)
(recur (- head x))
head)))
; Generates the next head
(defn next-head [head x n]
(trim-head (* head n) x))
(defn row [x n]
(iterate #(next-head % x n) n))
; Generates a whole row -
; Rows are a max of x - 1.
(take (- x 1) (row 11 3))
Примеры случаев, которые нужно остановить до достижения конца строки:
[9 8 4 5 6 7 4] - "4" повторяется, поэтому STOP. Верните предыдущий как начало координат, а остальные как шаблон.
{:origin [9 8] :pattern [4 5 6 7]}
[4 5 6 1] - нашел '1', так что СТОП, так что верните все как образец
{:origin nil :pattern [4 5 6 1]}
[3 0] - нашел '0', чтобы остановить
{:origin [3] :pattern [0]}
: else, если последовательности достигают длины x - 1:
{:origin [all values generated] :pattern nil}
Эта проблема
Я с успехом использовал разбивку на части для разделения групп в точке, где найдено повторяющееся значение, но хотел бы сделать это лениво. Есть ли какой-нибудь способ, которым я могу использовать take-while, или condp, или условие: while цикла for, чтобы создать условие, которое разбивает, когда он находит повторы?
Некоторые попытки
(take 2 (partition-by #(= 1 %) (row 11 4)))
(for [p (partition-by #(stop-match? %) head) (iterate #(next-head % x n) n)
:while (or (not= (last p) (or 1 0 n) (nil? (rest p))]
{:origin (first p) :pattern (concat (second p) (last p))}))
# Обновления
То, что я действительно хочу сделать, это выяснить, не повторилось ли значение, и разбить последовательность без использования индекса. Это возможно? Что-то вроде этого -
{
(defn row [x n]
(loop [hist [n]
head (gen-next-head (first hist) x n)
steps 1]
(if (>= (- x 1) steps)
(case head
0 {:origin [hist] :pattern [0]}
1 {:origin nil :pattern (conj hist head)}
; Speculative from here on out
(let [p (partition-by #(apply distinct? %) (conj hist head))]
(if-not (nil? (next p)) ; One partition if no repeats.
{:origin (first p) :pattern (concat (second p) (nth 3 p))}
(recur (conj hist head) (gen-next-head head x n) (inc steps)))))
{:origin hist :pattern nil})))
}
2 ответа
Возможна небольшая лень: вы можете лениво потреблять новые элементы, но вы должны висеть на всех старых элементах, чтобы использовать их в качестве шаблона, поэтому в последовательности, подобной (iterate inc 2) Вы должны использовать всю доступную память. Дополнительно, for только когда-либо позволяет вам смотреть на один элемент одновременно, поэтому он не подходит для этой задачи. Однако написать его как цикл / рекурс, хотя и немного утомительно, но и не сложно. Вы не указали, что возвращать, если последовательность заканчивается перед повторением, 1 или 0, поэтому я только догадался.
Кроме того, ваш первый пример вывода неверен: он должен останавливаться на 1, а не на 4, поэтому я скорректировал ваш ввод. Помимо этого, однако, вопрос хорошо задан: спасибо за четкое указание проблемы и описание того, с чем у вас возникли проблемы, а также того, что вы пробовали.
(defn trim-head [coll]
(loop [so-far [], indexes {}, index 0, coll (seq coll)]
(if-not coll
{:origin nil, :pattern so-far} ;; ?? not specified in question
(let [x (first coll), xs (rest coll)]
(if (contains? indexes x)
{:origin (subvec so-far 0 (indexes x))
:pattern (subvec so-far (indexes x))}
(case x
0 {:origin so-far, :pattern [x]}
1 {:origin nil, :pattern (conj so-far x)}
(recur (conj so-far x) (assoc indexes x index) (inc index) (seq xs))))))))
user> (map trim-head [[9 8 2 4 5 6 7 4] [4 5 6 1] [3 0]])
({:origin [9 8 2], :pattern [4 5 6 7]}
{:origin nil, :pattern [4 5 6 1]}
{:origin [3], :pattern [0]})
То, что я действительно хочу сделать, это выяснить, не повторилось ли значение, и разбить последовательность без использования индекса. Это возможно?
Я выполнил ваше обновленное требование прямо сейчас. В этом случае, split-with было бы предпочтительнее partition-by,
;;; find out if a value has repeated, but considering zero and one.
(defn- generate
"Returns a vector of [duplicate-value values-until-duplicate].
duplicate-value might be zero or one."
[s]
(->> [s [] #{0 1}]
(iterate (fn [[[head & more] generated idx]]
[more (conj generated head) (conj idx head)]))
(take-while (comp seq first))
(drop-while (fn [[[head & _] _ idx]]
(nil? (idx head))))
first
((juxt ffirst second))))
;;; partition the seq without using the index.
(defn partition-by-duplicate
[s]
(let [[pivot generated-values] (generate s)]
(cond (= 0 pivot) {:origin generated-values, :pattern [0]}
(= 1 pivot) {:origin nil, :pattern (conj generated-values 1)}
pivot (->> generated-values
(split-with (partial not= pivot))
(interleave [:pattern :origin])
(apply hash-map))
:else {:origin s, :pattern nil})))
Пример:
user> (map generate [[9 8 2 4 5 6 7 4] [4 5 6 1] [3 0]])
([4 [9 8 2 4 5 6 7]]
[1 [4 5 6]]
[0 [3]])
user> (map partition-by-duplicate [[9 8 2 4 5 6 7 4] [4 5 6 1] [3 0]])
({:pattern (9 8 2), :origin (4 5 6 7)}
{:origin nil, :pattern [4 5 6 1]}
{:origin [3], :pattern [0]})