Clojure - 执行动态嵌套循环的惯用方法

Question

这段代码旨在基本上循环遍历提供的字符串中的每个字母并继续直到z，然后递增前一个字母并在a处重新启动(例如，从"bde"开始，下一个是"bdf"，以"zzz"结束 - 与典型循环的工作方式相同。

我当然可以做一个嵌套的理解，因为这只有三个级别，但如果级别是任意深度的，我传统上的做法是使用递归(如下所示(，这基本上相当于深度优先搜索。

这种方法的问题在于，任何非平凡大小的输入都会吹动堆栈(例如，"abcd"(，我想不出没有递归的好方法。 在 Python 中实现的类似方法(有一些小差异，例如在可变列表中累积结果(，在 clojure 代码下方实现不会达到输入"abcd"的堆栈限制。

我尝试使用 loop/recur，但这种结构似乎在 for 宏中不起作用，因为调用必须在下一次循环迭代中暂停，因此不在尾部位置(至少我相信这是原因(。

解决此类问题的最惯用方法是什么？

;;; example using for macro
(defn gen-pw [pw r]
(cond (empty? pw) r
:else (flatten (for [x (range (int(first pw)) 123)]
(gen-pw (rest pw) (str r (char x)))))))

;;; example using map instead of for macro
(defn gen-pw [pw r]
(cond (empty? pw) r
:else (flatten (map #(gen-pw (rest pw) (str r (char %)))
(range (int(first pw)) 123))))) 
(gen-pw "bde" "") 

def gen_pw(pw,r='',final=[]):
if not pw:
final.append(r)
return 
for letter in range(ord(pw[0]),123):
gen_pw(pw[1:],r + chr(letter))
return final
print(gen_pw('abcd'))

Answer 1

您正在通过评估如下内容来生成一个非常过度嵌套的列表：

(for [...]
(for [...]
(for [...]
...)))

然后试图用flatten修复意外嵌套，当然必须递归地走进你巨大的结构，然后爆炸。相反，首先生成一个平面列表。最简单的方法是简单地采用您的map版本，将map替换为mapcat，然后删除现在不必要的flatten：

(defn gen-pw [pw r]
(cond (empty? pw) [r]
:else (mapcat #(gen-pw (rest pw) (str r (char %)))
(range (int(first pw)) 123))))

您还必须将基本大小写从r调整为[r]，就像我在这里所做的那样：您正在生成有效密码的列表，而不仅仅是一个密码，因此返回类型应始终为列表。

Answer 2

我认为这个问题陈述是关于计算笛卡尔乘积的，所以我倾向于推荐在clojure.math.combinatorics中找到的惰性相互递归实现。使用它变成这样的东西：

(ns loops
(:require [clojure.math.combinatorics :refer [cartesian-product]]
[clojure.string :refer [join]]))
(defn chars-from [start]
(map char (range (int start) 123)))
(defn gen-pw [pw]
(map join (apply cartesian-product (map chars-from pw))))
(gen-pw "bde")
;;=> ("bde" "bdf" "bdg" ... "bee" "bef" "beg" ...

Answer 3

一种方法是使用iterate：

(defn transition [[text n]]
(let [c (nth text n)
nxt (if (= c z) z (-> c int inc char))
nxt-str (str (subs text 0 n) nxt (subs text (inc n) (dec (count text))))]
(if (= z nxt)
[nxt-str (inc n)]
[nxt-str n])))
(defn ongoing? [[text n]]
(not (every? #(= z %) text)))
(->> (iterate transition ["zza" 2])
(take-while ongoing?)
(map first))

请注意，对于["zza" 2]，a位于第三位(因此为 2(，对于 ["dzs" 0]，d位于第一位置(因此为 0(。

Answer 4

如果您达到递归限制，请使您的流程迭代而不是递归。

您是对的，当递归过程调用是较大表达式的一部分(即不在尾部位置(时，它将产生递归过程。因此，请确保递归调用表示过程的整个值。

(defn gen-pw [pw r]
(let (s (successor pw))
(if (nil? s)                ; (successor "zzz") is equal to nil
r
(gen-pw s (cons s r)))))  ; (successor "bfe") is equal to "bff"