Jump to content

Enhancing the permute function

Recommended Posts

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?




Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

  • Create New...

Important Information

Terms of Use Privacy Policy