CODEWITHSUNDEEP
algorithmcommon-lisp
Guilherme
Guilherme

Reputation: 618

Random assignment of elements in a list

I have a list (of N ALISTs) that I need to partition into k mutually exclusive, collectively exhaustive lists (that don't necessarily have to be the same length). That is, I need a function that will do something like the following (for N = 6, k = 2):

(my-function (listA listB listC listD listE listF))
#=> ((listA listC listF listD) (listB listE))

The approach I was thinking about goes along those lines (assigning a number up to k for each member of the ALIST and then grouping those items based on their assignment). Maybe it's stupid, I'm not sure.

(defun make-solution (problem)
  "Generates random initial solution to be later explored"
  (let ((assignments (mapcar #'(lambda (request) (random *fleet-size*)) problem)))
    ; maybe something to group back the elements of problem according to their value in assignments?
    ))

Any hints on what to fill in? Maybe a better approach? For context, what I'm doing is randomly creating an initial population for a vehicle routing problem that I can later iterate on with my local search.

Upvotes: 1

Views: 241

Answers (1)

Rainer Joswig
Rainer Joswig

Reputation: 139331

Something like this maybe:

CL-USER 39 > (pprint
              (let ((l (loop for i from 1 upto 100 collect i)))
                (flet ((part (l k &aux (r (make-array k :initial-element nil)))
                         (loop while l
                               do (push (pop l) (aref r (random k))))
                         (coerce r 'list)))
                  (part l 7))))

((98 94 89 87 85 84 78 71 68 53 42 38 35 33 27 26 5 3)
 (93 86 65 55 54 37 23 18 11 10 2)
 (92 91 82 69 67 62 61 59 56 52 44 36 34 22 21 12 7)
 (97 77 76 70 57 47 46 45 43 32 17 14 4)
 (96 95 90 88 83 81 80 73 58 49 48 39 30 25 19 8 6)
 (75 63 60 41 31 24 15 9 1)
 (100 99 79 74 72 66 64 51 50 40 29 28 20 16 13))

Preserve the order:

CL-USER 40 > (pprint
              (let ((l (loop for i from 1 upto 100 collect i)))
                (flet ((part (l k &aux (r (make-array k :initial-element nil)))
                         (loop while l
                               do (push (pop l) (aref r (random k))))
                         (map 'list #'reverse r)))
                  (part l 7))))

((6 13 14 22 24 40 44 55 57 58 64 66 67 74 78 92 95 96)
 (7 11 23 26 27 28 81 91)
 (3 5 8 9 10 20 21 33 35 36 42 45 47 63 69 72 75 80 88 89 98)
 (2 16 32 43 53 68 71 76 79 84 87 90 93 94 97)
 (1 4 12 15 18 25 30 39 41 46 48 51 54 59 65 73 83 100)
 (17 19 29 31 34 37 38 49 56 85 86)
 (50 52 60 61 62 70 77 82 99))

Upvotes: 3

Related Questions