How do I generate all permutations of certain size with repetitions in Scheme?

Question

I am learning Scheme and I am trying to generate permutations with repetitions of certain size.

For example, given n=4 and set S = {a, b, c, d, e, f}, I'd like to generate all possible permutations: {a,a,a,a},{a,a,a,b},...,{a,a,a,f},{a,a,b,a},{a,a,b,b},...,{a,a,b,f},...{f,a,a,a},{f,a,a,b}...,{f,a,a,f},...{f,f,f,f}.

The trouble is that I can't understand how to pick 'a' 4 times, and remember that i had picked it 4 times, then pick 'a' 3 times, and 'b' one time, and remember all this, so I don't pick it again.

I know that these kinds of problems are best solved with recursive algorithms, but it just makes everything more complicated, like, how do I remember in the recursion, what elements have I picked.

I don't know how to approach this problem at all. I would be very glad if someone wrote out the thought process of solving this problem. I'd appreciate it very much!

Please help me.

Thanks, Boda Cydo.

Answer 1

It's good to start from the procedure's interface and expected results. Your procedure is going to be called (permutations size elements) and is expected to return a list of permutations of the items in ELEMENTS, each permutation being SIZE items long. Figure you're going to represent a "permutation" as a list. So if you called (permutations 1 '(a b c)) you'd expect an output of ((a) (b) (c)).

So the trick about recursive procedures, is you have to figure out what the base condition is that you can answer easily, and the recursive step which you can answer by modifying the solution of a simpler problem. For PERMUTATIONS, figure the recursive step is going to involve decreasing SIZE, so the base step is going to be when SIZE is 0, and the answer is a list of a zero-length permutation, i. e. (()).

To answer the recursive step, you have to figure out what to do to the result for size N - 1 to get a result for size N. To do this, it can help to write out some expected results for small N and see if you can discern a pattern:

ELEMENTS = (a b)
SIZE   (PERMUTATIONS SIZE ELEMENTS)
0      ( () )
1      ( (a) (b) )
2      ( (a a) (a b) (b a) (b b) )
3      ( (a a a) (a a b) (a b a) (a b b) (b a a) ... )

So basically what you want to do is, given R = (permutations n elements), you can get (permutations (+ n 1) elements) by taking each permutation P in R, and then for each element E in ELEMENTS, adjoin E to P to create a new permutation, and collect a list of them. And we can do this with nested MAPs:

(define (permutations size elements)
  (if (zero? size)
      '(())
      (flatmap (lambda (p)            ; For each permutation we already have:
                 (map (lambda (e)     ;   For each element in the set:
                        (cons e p))   ;     Add the element to the perm'n.
                      elements))
               (permutations (- size 1) elements))))

I'm using FLATMAP for the outer mapping, because the inner MAP creates lists of new permutations, and we have to append those lists together to create the one big flat list of permutations that we want.

Of course, this is all assuming you know about and have a good handle on sequence operations like MAP. If you don't it'd be real difficult to come up with an elegant solution like I just did here.