2

Given a number n, find a permutation of the numbers 1...n such that all adjacent entries sum up to primes. If such a permutation does not exist, throw an error.

Is there a purely-functional way to do this problem? The solution, which apparently uses backtracking, given uses C++, a language which I am not very familiar with, and loops in loops in loops with very badly-named variable names and a whole lot of mutation. Even if the solution requires mutation, nested loops are really difficult to translate into Racket, the language I currently use.

A more general question would be, how to do backtracking algorithms purely functionally when the concept of backtracking seems to always involve maintaining a state of where you are currently and a big history breadcrumb global state variable that keeps getting mutated?

Of course the dumb way would be to generate all permutations and test them one by one, but are there more efficient ways, preferably implementing a backtracking method, to do so functionally?

Since I use Racket, the solution might not be purely functional but preferably mostly functional, i.e. no repeatedly mutating counter vars in loops or such.

  • do you have a link to this C++ code? anyway, generate-and-test under lazy evaluation is backtracking, "turning a failure into a list of successes", i.e. churning up lists of all solutions, where empty lists represent failure, and using append-map calls chained together as processing steps (so each solution is turned into a list of further refined solutions, and all is combined through append-map which is a join for a nondeterminism (list) monad). The key to efficiency is then early rejection. – Will Ness Jun 20 '13 at 9:00
  • Aside from the obvious "Yes since church-turing thesis" here's a quick doodle of naive and lazy approach which is actually pretty efficient if you only want 1 such permutation lpaste.net/95678 – Daniel Gratzer Nov 14 '13 at 21:28
8

I just wrote an implementation in Clojure, a functional Lisp-I, which you may find below. Because of the controversy in the commments to this answer, I will try to explain the code and the techniques used to achieve the result as good as possible, especially for those who are not Clojurists. Forgive me if I don't touch on everything in great detail and length.

This version does not mutate state. All of Clojures values are immutable, e. g. a vector [1 2] can not be altered once it has been constructed. When you want to concat that vector with another vector [3 4] you may invoke a function like concat like this (concat [1 2] [3 4]). Concat will return a new vector [1 2 3 4] and the two input vectors will be forgotten. The great thing is that behind the scenes, structural sharing is happening: The new vector [1 2 3 4] consists of the same data [1 2] and [3 4] consisted of. Also, if we had bound the vector [1 2] to a symbol a instead, after (concat a [3 4]) a would still be [1 2]. So while you are always generating new immutable values, in memory only the delta will be allocated.

One other feature of Clojure I am taking advantage of is laziness. E. g. you can build a sequence of all number 0 ... n with (range). The call to range returns an infinite sequence like (0 1 2 3 4 5...), but it is not realized until elements of it are consumed. Finally, many transformation functions return new lazy-sequences from lazy input sequences, so (filter even? (range)) would give me a lazy sequence of all numbers >= 0 for which the predicate even? (a boolean function) returns true - however, the filtering only happens when I actually consume elements from that sequence, e. g. (take 3 (filter even? (range))) will return (0 2 4): Until here, filter has been invoked five times (as many times as necessary to produce three elements or have the input sequence consumed).

The prime ring generator below utilizes this laziness. If you invoke (rings-of-primes 100) it immediately returns a lazy sequence of all possible prime rings with 100 elements from 1 to 100. Nothing is calculated, so if I wanted to have only three rings, I could do (take 3 (rings-of-primes 100)) and calculation would only happen for the production of three rings.

The core to the solution below is the function helper-fn which is defined within rings-of-primes. It takes two immutable values as arguments and refers to two other immutable values, length (the argument to rings-of-primes) and n-range (defined in rings-of-primes as seq [1 .. length]) in its body.

The two arguments to helper-fn are used, an immutable set of numbers that have been used in the possible ring passed as the second arg, acc (short for accumulator).

One of the great advantages of Clojure is that when you are dealing with immutable values, it's quite easy to write pure functions. helper-fn is one of those pure functions. It is defined as follows: It takes the input of a set of used numbers, and a vector of numbers which is supposed to be a partial ring of primes, and always returns a sequence of possible rings of primes that begin with the numbers in acc and have a size of length. If no rings are possible, helper-fn returns (), an empty list (not the same as nil in Clojure).

          (let [last-elem (peek acc)]
            (if (and (= length (count acc))
                     (is-prime?
                      (+ last-elem
                         (first acc))))
              [acc]

In the above code-snippet (the first lines of helper-fn), the symbol last-elem is bound to the last value of acc. Then within the conditional statement if two conditions are tested: 1. Has accumulator the user-desired length ((= length (count acc)))?, 2. Do the last and the first element add up to a prime number. If both conditions are matched, helper-fn returns [acc], a vector with exactly one element: The accumulator, a valid prime-ring. The nesting in an additional vector is needed because our function is supposed to return a sequence of valid prime-rings, not just a sequence of numbers.

Now what happens if the passed value is not a prime-ring, like when the function is invoked the first time within rings-of-primes: (helper-fn #{1} [1]). As you might have noticed, #{1} is the notation for a set, and within helper-fn, used will now be bound to #{1} and acc will be bound to [1].

Given that we have asked for a length of 4, the test-clause in the code snippet above will fail. What happens then?

              (let [parity-filter (if (even? last-elem)
                                    odd?
                                    even?)]
                (->> n-range
                     (filter #(and (parity-filter %)
                                   (not (used %))
                                   (is-prime? (+ %
                                                 last-elem))))
                     (lazy-mapcat #(helper-fn 
                                    (conj used %)
                                    (conj acc %))))))))]

The parity-filter symbol will be bound to either the predicate function odd? or to the predicate function even?, depending on whether the last-element of acc is even or odd. The reason is that you can divide even numbers by two, and adding two even numbers or two odd numbers always results in an even number which can't be a prime number then. So we only want the numbers with the opposite parity of the last element of acc, last-elem.

->> is an awesome macro. It does not do anything except for reordering the code you put into it. That is one of the advantages of Clojure being a lisp, that all your code is data that can be manipulated before evaluation. ->> reorders your code so (->> x (doY) (doZ baz)) => (doZ baz (doY x)). In other words, the first argument is appended to the end of the second form, which is appended to the end of the third form and so on.

So in this case, n-range, which was generated at the beginning of rings-of-primes, another immutable value, will be threaded with ->>. n-range will always be a sequence [1 .. length]. Now this sequence must be filtered. We define a small function, a lambda, on the fly as the first argument to filter:

                             #(and (parity-filter %)
                                   (not (used %))
                                   (is-prime? (+ %
                                                 last-elem)))

In this case #(...) creates a function with one argument to which we refer as %. E. g. #(+ % %) would create a function that takes one argument and doubles it. Our lambda is a predicate function that tests the argument for three conditions: 1. It must pass the parity-filter, 2. It may not be in the set used (you can invoke sets like functions and they return whether they contain the argument), 3. Added to the last-elem of acc, it must be a prime-number. If this three conditions match, it is a possible candidate for the next iteration of the prime ring we are building, and it will be part of the lazy sequence returned by the filter expression.

After that, a function lazy-mapcat that comes with this source, is invoked. It takes a transformation function and a sequence of elements (our filtered candidates), transforms each input element with the transform function and concats the returned value (a sequence) to the other returned values. The transformation function may return any kind of sequence, also the empty sequence. Let's have a closer look at the transformation function:

                                 #(helper-fn 
                                    (conj used %)
                                    (conj acc %))

Yes! It's a call to helper-fn itself. conj takes a collection and an argument and returns a new collection with that argument in it. Here we put the value taken from our filtered sequence into a new version of used, also create a new version of acc with that number in it, and pass them to helper-fn. Now go back to line 1. helper-fn will then (after many more recursive steps) return a sequence of possible prime-rings and because of mapcat we do that for each candidate that may be the next valid number in the current prime-ring. All the resulting sequences of rings will be concatenated to one sequence of rings. Of course, in some cases helper-fn will return an empty list, and on a higher level, that empty list will be concataned with other lists - also within a mapcat expression.

As you can see, no state is mutated. The resulting function is pure and can also be invoked with odd lengths or negative input values, in which case it will (mathematically correctly) return an empty list as a result.

You could say that the backtracking happens with acc passed to helper-fn, but much more I'd like to think of this implementation of a pure function call that results in the self assembly of possible prime-rings through a series of recursive function calls.

;; Clojure implementation of http://coj.uci.cu/24h/problem.xhtml?abb=1196
;; This version generates all possible rings of primes for any given n
;; Leon Grapenthin, Nov. 14 2013

(def is-prime?
  "Returns true if n is a prime number. Memoized."
  (memoize              ;; remember all results returned by this function
                        ;; so that a second call with the same n does not
                        ;; require calculation
   (fn is-prime?
     [n]
     (cond
      (even? n) (= 2 n) ;; if n is even, return whether
                        ;; its 2, the only even prime number
      (= 1 n) false     ;; if n is one, return false
      :otherwise
      (->> (range 2 n)  ;; build a sequence from 2 to n
           (filter (comp zero?
                         (partial mod n))) ;; filter those were dividing
                                           ;; n by them has a rest of 0
           empty?))))) ;; none could be found? => It's a prime number.

(defn lazy-mapcat
  ;; stolen from http://clojurian.blogspot.de/2012/11/beware-of-mapcat.html
  [f coll]
  (lazy-seq
   (if (not-empty coll)
     (concat
      (f (first coll))
      (lazy-mapcat f (rest coll))))))

(defn rings-of-primes
  "Returns a lazy sequence of possible prime rings for length."
  [length]
  (let [n-range (range 1 (inc length))
        helper-fn
        (fn helper-fn
          ;; tries to build the seq until acc has length and the ring
          ;; condition is fulfilled, otherwise returns nil
          [used acc]
          (let [last-elem (peek acc)]
            (if (and (= length (count acc))
                     (is-prime?
                      (+ last-elem
                         (first acc))))
              [acc]
              (let [;; slight optimization: a prime number (+ x y) with
                    ;; (not= x y) can only be built when the parities of
                    ;; x and y differ:
                    parity-filter (if (even? last-elem)
                                    odd?
                                    even?)]
                (->> n-range
                     (filter #(and (parity-filter %)
                                   (not (used %))
                                   (is-prime? (+ %
                                                 last-elem))))
                     (lazy-mapcat #(helper-fn 
                                    (conj used %)
                                    (conj acc %))))))))]
    (helper-fn #{1} [1])))

;; (time
;;  (first (rings-of-primes 100)))
;; "Elapsed time: 57.316798 msecs"
;; [1 2 3 4 7 6 5 8 9 10 13 16 15 14 17 12 11 18 19 22
;;  21 20 23 24 29 30 31 28 25 34 27 26 33 38 35 32 39
;;  40 43 36 37 42 41 48 49 52 45 44 53 50 47 54 55 46
;;  51 56 57 70 61 66 65 62 69 58 73 64 63 68 59 72 67
;;  60 71 78 79 84 83 74 75 76 81 82 85 88 91 90 89 92
;;  87 80 77 86 93 98 95 96 97 94 99 100]
  • The point here is that the C++ implementation is not written in functional manner but utilizing mutable state. My implementation does not use any mutable state and is purely functional. – user108745 Nov 14 '13 at 22:07
  • 4
    I have now written very extended commentary on the implementation with a focus on mutability and recursion. – user108745 Nov 15 '13 at 15:58
  • 2
    be careful with the number of edits you do. Your answer will convert to community wiki status at the 10th edit, I believe. – user53019 Nov 15 '13 at 16:48
  • 1
    don't listen to @GlenH7 - feel free to do substantial edits as much as needed! As of now, your answer is good enough to warrant exception: if CW is ever triggered, simply ping me and I'll raise a flag or meta complaint to return it back to your ownership. Been there done that: 1, 2 – gnat Nov 15 '13 at 17:04
  • Great edit! Take this as a lesson; unlike StackOverflow you don't need to be the fastest gun in the west here, if your answer is the 7th one on a question but the best one it will often end up at the top :) Hope to see more posts from you here, always happy to have more FP content! – Jimmy Hoffa Nov 15 '13 at 20:15
7

You've got your finger right on the nose of the solution but just don't quite see it, so let's take a quick detour and see if it becomes a little clearer.

In a purely functional language, where you can't mutate anything and therefore cannot have loop indexers etc, how do you write loops?

That's right; you recurse. Why? Because when your only state is in local, and immutable, the only way to change the values in your local is to create new local frames with the values you want.

Now then, back to backtracking, the beauty of not having indices to manage in a loop, is that when you want to move back a few iterations; all you do is return from each frame until you're back where you want to be.

Alternatively, you can backtrack functionally by holding on to your old closures states and move forward into them instead of backwards up the stack when you want to go to an old state. This is however unpleasant as you alluded to above.

Now if you want to get an even more beautiful look at backtracking, you can take a look at Monads and how you do control flow with them, google and I'm sure you can find monadic implementations in racket. Looking at Parser Combinators is a great place to see functional approaches to backtracking.

  • As a racket specific hint, call/cc can be used to implement some very very snazzy logic programming dsl's and datalog is a prolog like language Racket can easily interface with – Daniel Gratzer Nov 15 '13 at 0:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.