2

This code is intended to basically loop through each letter in the supplied string and continue until z, then increment the prior letter and restart at a (e.g. starts at "bde", next would be "bdf", ends at "zzz" - the same way a typical loop would work.)

I could of course do a nested for comprehension since this is only three levels, but if the levels are arbitrarily deep, the way I would traditionally approach that is by using recursion (as demonstrated below), in what basically amounts to a depth first search.

The problem with this approach is that any non-trivial sized input blows the stack (for example, "abcd"), and I can't think of a good way to do it without recursion. A similar approach in Python (with some small differences like accumulating results in a mutable list), implemented below the clojure code doesn't hit the stack limit for input "abcd".

I tried using loop/recur but this construct doesn't seem to work from within a for macro as the call must suspend on the next loop iteration and is therefore not in tail position (at least I believe that is the reason).

What is the most idiomatic way to approach this type of problem?

;;; 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'))
Improve this question
2
  • It is not clear what you are trying to accomplish. Is this procedure supposed to create a list of lexicographic successors to a given string, i.e. ("bde" "bdf" "bdg" ... "zzz")? Commented Jul 10, 2017 at 22:08
  • Yes, that is the intent. Commented Jul 10, 2017 at 22:10

4 Answers 4

Reset to default
3

You are generating a list that is tremendously over-nested by evaluating something like this:

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

And then trying to fix the accidental nesting with flatten, which of course has to walk recursively into your gigantic structure, and then explodes. Instead, generate a flat list to begin with. The easiest way to do this is simply to take your map version, replace map with mapcat, and remove the now-unnecessary flatten:

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

You'll also have to adjust the base case from r to [r], as I did here: you're generating a list of valid passwords, not just one password, and so the return type should always be a list.

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

I actually did try mapcat previously but goofed on the [r] portion so I was getting individual characters - this is what I was missing. That's the good news, the bad news is that it still blows the stack.
Oh, of course. Because (mapcat (mapcat (mapcat ... is a problem too, just a different kind of problem. edit: Actually, no, I disagree. (count (gen-pw "aaaaa" "")) returns 11881376 just fine, and there's no way you have ten million stack frames to play with.
hmm let me test this again on my machine - was using on online REPL since I wasn't near it, and it choked there. Previously not even "abcd" would run.
Incidentally this will still run out of stack if the desired string length is very large: it consumes a number of stack frames that is linear in the length of the string. So if you wanted to generate passwords that are a thousand characters long, you'd run into trouble. The same is true of your Python version, of course.
Out of curiosity, why did you use cond here instead of just if?
|
1

I see this problem statement as about computing a cartesian product, so I'm inclined to just recommend the lazy mutual-recursion implementation of that found in clojure.math.combinatorics. Using it becomes something like:

(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" ...
Improve this answer

1 Comment

Yep - this would be the counterpart to itertools.product - I like it. Thank you for this addition.
1

One way to do this is using 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))

Note that for ["zza" 2] the \a is in third position (hence 2) and for ["dzs" 0] the \d is in first position (hence 0).

Improve this answer

Comments

-1

If you're reaching the recursion limit, make your process iterative rather than recursive.

You're right that when the recursive procedure call is part of a larger expression (that is, not in tail position), it will produce a recursive process. Therefore, make sure that the recursive call represents the entire value of the procedure.

(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"
Improve this answer

1 Comment

This is a solution that would work well in scheme, but doesn't work in clojure because there's no automatic tail-call optimization. You could fix that by using recur, but your approach is still strict/eager, where a lazy solution would be much better.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.