Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I have strong feeling that the code below is ugly at least as there are 2 same "cons".
I would appreciate if you advise me ways to improve it.

The code produces all allocation by n items from list lst.

(defun allocations (lst n)
  (if (= n 1)
      (loop for i in lst
       collect (cons i nil))
      (loop for i in lst
   append (mapcar #'(lambda (l) (cons i l))
                      (allocations (remove i lst) (- n 1))))))
share|improve this question

migrated from stackoverflow.com Dec 14 '12 at 16:43

This question came from our site for professional and enthusiast programmers.

1  
To make sure I understood you: you are trying to do permutations based on an assumption that the elements of the list are unique non-negative integers? In that case, I'd rather use a general purpose permutation algorithm instead. Actually, complexity-wise you'd only gain from that. Also variable names like lst and l can be improved by expanding them to the full length. The first branch in the if is equivalent to (mapcar #'list lst). –  wvxvw Dec 14 '12 at 13:08
    
thanks @wvxvw! Yes, you are right. List elements are unique and non-negative integers. I will try to use general purpose permutation algorithm. –  korabelnik Dec 14 '12 at 13:27
    
thank you @finnw! I will use codereview site. –  korabelnik Dec 14 '12 at 13:32

1 Answer 1

up vote 2 down vote accepted
(defun allocations (source length)
  (if (= 1 length)
      (list (list (car source)))
      (loop for processed = nil then (cons (car i) processed)
         for i on source
         for todo = (cdr i)
         appending
           (loop for intermediate
              in (allocations
                  (append (reverse processed) todo)
                  (1- length))
              appending
                (loop for prefix = nil then (cons (car suffix) prefix)
                   for suffix on intermediate
                   collect (append prefix (list (car i)) suffix))))))

This should be a more general case of the problem (i.e. it makes no assumption of the nature of the elements in the list), but it doesn't verify that there is enough of the elements in the source list to build the required number of permutations.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.