How can I generate all permutations of a certain size with repetitions in a diagram?

Question

I am studying a circuit and I am trying to create permutations with repetitions of a certain size.

For example, given n = 4 and setting S = {a, b, c, d, e, f}, I would like to generate all possible permutations: {a, a, a, a}, {a, a, a, b }, ..., {a, a, a, e}, {a, a, b, a}, {a, a, b, b}, ..., {a, a, B, F}, ... {e, a, a, a}, {e, a, a, b} ..., {F, A, A, F}, ... {F, F, F, F}.

The trouble is that I can’t understand how to choose “a” 4 times, and remember that I selected it 4 times, then select “a” 3 times and “b” once and remember all this, so I don’t choose him again.

I know that these problems are best solved with the help of recursive algorithms, but it just complicates the situation, for example, as I remember in recursion, which elements I chose.

I do not know how to approach this problem at all. I would be very happy if someone wrote a thought process to solve this problem. I would really appreciate it!

Please help me.

Thanks, Boda Sido.

Answer 1

It is good to start with the procedure interface and the expected results. Your procedure will be called (permutations size elements) and is expected to return a list of permutations of elements in ELEMENTS, with each permutation being lengthy. The image that you are going to represent as a "permutation" as a list. Therefore, if you called (permutations 1 '(abc)) , you expect output ((a) (b) (c)) .

So, a trick about recursive procedures, you need to find out what is a basic condition that you can easily answer, and a recursive step that you can answer by changing the solution to a simpler problem. For PERMUTATIONS, specify that the recursive step will include decreasing SIZE, so the base step will be when SIZE is 0 and the answer is a permutation list of zero length, i. e. (()) .

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

  ELEMENTS = (ab)
 SIZE (PERMUTATIONS SIZE ELEMENTS)
 0 (())
 1 ((a) (b))
 2 ((aa) (ab) (ba) (bb))
 3 ((aaa) (aab) (aba) (abb) (baa) ...)

So basically what you want to do, given R = (permutations n elements) , you can get (permutations (+ n 1) elements) by taking each permutation P into R, and then for each element E in ELEMENTS, connect E with P to create a new permutation and collect their list. 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 ep));  Add the element to the perm'n.
                       elements))
                (permutations (- size 1) elements))))

I use FLATMAP for external matching because the internal MAP creates lists of new permutations, and we must add these lists together to create one large flat list of permutations that we want.

Of course, all of this assumes that you know, and are well versed in operations such as MAP. If you do not, it would be very difficult to come up with an elegant solution, as I just did here.

Answer 2

Here is another version: I used shorthand, not flatmap. I wrote it in the MIT-scheme .

 (define (per s) (define (ins c before after) (if (null? after) (list (append before (list c))) (append (list (append before (list c) after)) (ins c (append before (list (car after))) (cdr after))))) (define (iter l) (cond ((null? l) '(())) (else (let ((rest (iter (cdr l)))) (reduce-left append () (map (lambda (x) (ins (car l) () x) ) rest)))))) (iter s)) (per '(1 3 2 4)) 

Answer 3

Hint. You can use parameters for a recursive call to "remember" what other recursive calls did;)