Your implementation of permute is very nice. I looked at a few implementations on the net, but they do not handle duplicate elements correctly, whereas your implementation seems correct.

 

I would like to propose two enhancements to this function:

1) Sometimes, I might not require all permutations of a list, but only some N, where N < the maximum possible size. For example, with 4 distinct elements, 24 is the max possible, but I might just require 6. To handle this case, we can have a keyword argument to limit the size.

 

(permute '( 1 2 3 4) :limit 6) => Returns only 6 elements, not 24. Order is not guaranteed.

 

2) This is a bit tricky. Instead of restricting the number of elements explicitly as in (1), I might want to filter the elements based on some constraint. Here is a scenario:

 

(constrained-permute '(1 2 3 4) #'(lambda (e) (if (< (first e) (second e)) e nil)))

 

This will generate only those sequences where the first element of the list is less than the second element (just a hypothetical example).

 

Here is one way to implement this:

(defun constrained-permute (alist constraint)
  (filter-remove nil (mapcar constraint (permute alist))))

 

The problem with this is it is costly. It filters after generation. It will be better to apply the filter as part of the generation itself. To support this, we can add another keyword argument to permute:

 

(permute '(1 2 3 4) :filter #'(lambda (e) (if (< (first e) (second e)) e nil)))

 

Of course, we can also specify the limit if we want:

 

(permute '(1 2 3 4) :limit 6 :filter #'(lambda (e) (if (< (first e) (second e)) e nil)))

 

Do you think this makes sense?

 

Regards,

Rangarajan

Interesting concept, it makes sense.