recursion - 将 python 代码翻译为 clojure、递归和 for 循环

Question

我从长度为 n 的列表中计算出 n 个组合中的 k 个。我发现python代码非常简洁，所以我直接翻译了。

def comb(sofar, rest, n):
     if n == 0:
         print sofar
     else:
         for i in range(len(rest)):
             comb(sofar + rest[i], rest[i+1:], n-1)

comb("", "abcde", 3)

产量:abc、abd、abe 等...

将被翻译为 clojure 代码:

(defn comb [sofar v n]
  (if (= n 0)
    (print sofar)
    (for [i (range 0 (count v))] 
      (comb  (str sofar (nth v i))   ;don't it need to be recur ?
             (subvec v (inc i))
             (dec i)))))

嵌套循环/递归非常令人困惑。

问题是如何更改代码以执行与 python 代码相同的功能？

我的 clojure 代码似乎没有做同样的工作。

Answer 1

首先，如果您想要一个 clojure 解决方案，请用 clojure 术语来思考，在序列上编写函数，以惰性序列的形式生成结果，并让最终消费者在需要时将其减少为字符串。下面，我根本不使用 print，只是返回惰性序列，并让 repl 成为打印机。

此外，您试图将 python for 直接转换为 clojure for 来进行循环，这不是它的用途(没有双关语)。 clojure's for是一个序列生成器，所以您可能会感到困惑。

要获得问题的简单解决方案，您可以使用 math.combinatorics :

user=> (require '[clojure.math.combinatorics :as m])
user=> (m/combinations "abcde" 3)
((\a \b \c) (\a \b \d) (\a \b \e) (\a \c \d) (\a \c \e) (\a \d \e) (\b \c \d) (\b \c \e) (\b \d \e) (\c \d \e))

如果需要，您可以编写一个映射将其转换为字符串，以获得与 python 相同的输出。

user=> (map #(apply str %1) (m/combinations "abcde" 3))
("abc" "abd" "abe" "acd" "ace" "ade" "bcd" "bce" "bde" "cde")

但是，我怀疑您正在寻找更多有关循环的教程。

有another solution to this problem here用于创建一个函数以将序列返回为字符，该函数生成与上面示例相同的序列，并且也可以包装在映射中以进行字符串输出。它使用带有 cond block 的递归来控制迭代的结束。

Here is another good article通过将问题解构为本质上递归的东西来进行相同的组合，并解释它如何与递归一起工作。

如果您想了解有关递归与命令式循环的更多信息，请查看this SO question。 .

和here is a gist提供一些循环/递归与阶乘递归的示例，以便您可以直接看到两者之间的语法风格。

就习惯编写生成这样的序列的函数而言，我发现 The Little Schemer是解释思维过程的绝佳资源。它是用方案编写的，但很容易理解并应用于 clojure。之后，您可以查看高阶函数(map/reduce)而不是使用循环。

总而言之，在执行此操作时，如果您到处使用惰性函数，那么您的结果通常会是惰性的，并且如果您进行递归，则需要尝试使用尾递归，这样在使用时就不会破坏堆栈大组合，并转储您不感兴趣的值。