Scheme - generate all distinct permutations of a list

Question

While reading a certain book about functional programming and scheme (and Racket) in particular, I happened upon an exercise which states the following: `

"Write a function 'rp' which takes, as an argument, a list 'lp' of pairs '(a . n)',
where 'a' is either a symbol or a number and 'n' is a natural number, 
and which returns the list of all the lists, whose elements are the 'a's defined by 
the pairs in 'lp', each one appearing exactly 'n' times."

For some reason this is really cryptic, but what it basically asks for is the list of all distinct permutations of a list containing n times the number/symbol a.

E.g : [[(rp '((a . 2) (b . 1))]] = '((a a b) (a b a) (b a a))

Generating the permutations, ignoring the distinct part, is fairly easy since there is a, relatively, straight forward recursive definition:

The list of permutations of an empty list, is a list containing an empty list.
The list of permutations of 3 elements a b c is a list containing the lists of all permutations of
a and b where, for each one, c has been inserted in all possible positions.

Which I translated in the following racket code:

(define permut
  (lambda(ls)
    (if(null? ls) '(())
       (apply append
              (map (lambda(l) (insert_perm (car ls) l))
                   (permut (cdr ls)))))))

(define insert_perm
  (lambda(x ls)
    (if(null? ls) (list (list x))
       (cons (cons x ls)
             (map (lambda(l) (cons (car ls) l))
                  (insert_perm x (cdr ls)))))))

This works, but does not return distinct permutations. Taking into account the duplicates seems to me much more complicated. Is there a simple modification of the simple permutation case that I cannot see? Is the solution completely different? Any help would be appreciated.

Answer 1

The change is pretty simple. When you have no duplicate, the following works:

The list of permutations of 3 elements a b c is a list containing the lists of all permutations of a and b where, for each one, c has been inserted in all possible positions.

With duplicates, the above doesn't work anymore. A permutation of 2 elements a = "a", b = "b" is:

• "a" "b"
• "b" "a"

Now, consider c = "a". If you insert it in all possible positions, then you would get:

• c "a" "b" = "a" "a" "b"
• "a" c "b" = "a" "a" "b"
• "a" "b" c = "a" "b" "a"
• c "b" "a" = "a" "b" "a"
• "b" c "a" = "b" "a" "a"
• "b" "a" c = "b" "a" "a"

So instead, make a restriction that when you are inserting, you will only do it before the first occurrence of the same element that exists in the list that you are inserting to:

• c "a" "b" = "a" "a" "b" -- this is OK. c comes before the first occurrence of "a"
• "a" c "b" = "a" "a" "b" -- this is not OK. c comes after the first occurrence of "a"
• "a" "b" c = "a" "b" "a" -- this is not OK
• c "b" "a" = "a" "b" "a" -- this is OK
• "b" c "a" = "b" "a" "a" -- this is OK
• "b" "a" c = "b" "a" "a" -- this is not OK

This gives:

• "a" "a" "b"
• "a" "b" "a"
• "b" "a" "a"

as desired.

Moreover, you can see that this algorithm is a generalization of the algorithm that doesn't work with duplicates. When there's no duplicate, there's no "first occurrence", so you are allowed to insert everywhere.

---

By the way, here's how I would format your code in Racket/Scheme style:

(define (permut ls)
  (if (null? ls)
      '(())
      (apply append
             (map (lambda (l) (insert-perm (car ls) l))
                  (permut (cdr ls))))))

(define (insert-perm x ls)
  (if (null? ls)
      (list (list x))
      (cons (cons x ls)
            (map (lambda (l) (cons (car ls) l))
                 (insert-perm x (cdr ls))))))

Answer 2

After some thought I came up with my own recursive definition that seems to work. This solution is an alternative to the one proposed in the answer by @Sorawee Porncharoenwase and can be defined as follows:

The distinct permutations of a list containing only one kind of element 
(e.g '(a a a)) is the list itself.
if (f l) gives the list of distinct permutations (lists) of l, 
where l contains x times each distinct element el_i, 0<=i<=n 
and if ll is the list l plus one element el_i, 0<=i<=n+1 (distinct or not)
Then the distinct permutations of ll is a list containing 
all the following possible concatenations:
el_i + (f l/{el_i}), where l/{el_i} is the list l excluding its ith distinct element.

To illustrate this definition, consider the following examples:

The list of all distinct permutations of (a b c) is the list containing
a + {(b c) (c b)} = (a b c) (a c b)
b + {(a c) (c a)} = (b a c) (b c a)
c + {(a b) (b a)} = (c a b) (c b a)

The list of all distinct permutations of (a a b) is the list containing: 
a + {(a b) (b a)} = (a a b) (a b a)
b + {(a a)} = (b a a)

etc...

Similarly, the list of all distinct permutations of (a a b c) is: 
a + {(a b c) ...} = (a a b c) (a a c b) (a b a c) (a b c a) (a c a b) (a c b a)
b + {(a a c) ...} = (a a c) (a c a) (c a a)
c + {(a a b) ...} = (a a b) (a b a) (b a a)

This leads to the following implementation:

(define unique_perm
  (lambda(ls)
    (if (= (length ls) 1)
        (list (build-list (cdar ls) (const (caar ls))))
        (apply append (map (lambda(p) (map (lambda(l) (cons (car p) l)) (unique_perm (update_ls ls p)))) ls)))))

(define update_ls
  (lambda(ls p)
    (cond ((null? ls) ls)
          ((equal? (caar ls) (car p))
           (if (= (- (cdar ls) 1) 0)
               (cdr ls)
               (cons (cons (caar ls) (- (cdar ls) 1)) (cdr ls))))
          (else (cons (car ls) (update_ls (cdr ls) p))))))

Example:

> (unique_perm_2 '((a . 3) (b . 2)))
'((a a a b b) (a a b a b) (a a b b a) (a b a a b) (a b a b a) (a b b a a) (b a a a b) (b a a b a) (b a b a a) (b b a a a))