HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Producing all allocations by n items from a list

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
producingallitemsallocationslistfrom

Problem

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))))))

Solution

(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.

Code Snippets

(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))))))

Context

StackExchange Code Review Q#19614, answer score: 2

Revisions (0)

No revisions yet.