Lisp: How to get all possible combinations of the elements from lists contained on a list?
Clash Royale CLAN TAG#URR8PPP
Lisp: How to get all possible combinations of the elements from lists contained on a list?
I need to write a function in Common-Lisp that takes a list of lists and returns a list containing all the possible combinations of the elements from the sublists.
So, for example calling the function on a list such as ((1 2) (1 2)) should return a list like ((1 1) (1 2) (2 1) (2 2)). The input list can be of any length and the sublists are not guaranted to have the same length.
I know how to get this with paired elements from the sublists ( inputtting ((1 2) (1 2)) returns ((1 1) (2 2)), but that's not good enough for the arc-consistency algorithm I'm trying to write, and I'm stuck.
Thank you.
Sort-of duplicate of (Scheme) Recursive function to compute all possible combinations of some lists?. Granted that's a Scheme question and not CL, but it's not hard to adapt.
– Chris Jester-Young
Sep 7 '13 at 17:35
What you want is basically the cartesian product of the sublists. You should be able to find solutions for your problem by looking for that term.
– Rörd
Sep 7 '13 at 17:58
@Rörd Indeed, that's exactly what I searched for when trying to find a (sort-of) duplicate: I first search for
[common-lisp] cartesian (which found nothing), then [lisp] cartesian, and so on.– Chris Jester-Young
Sep 7 '13 at 18:23
[common-lisp] cartesian
[lisp] cartesian
Erm... those aren't combinations. Combinations don't allow things like
(1 2) and (2 1) in the same result. That's the cartesian / cross-product. Combinations are per definition independent of the order.– user797257
Sep 7 '13 at 19:24
(1 2)
(2 1)
2 Answers
2
If you don't want to use a library, here's code to do the same thing, and works with any number of lists:
(defun combinations (&rest lists)
(if (endp lists)
(list nil)
(mapcan (lambda (inner-val)
(mapcar (lambda (outer-val)
(cons outer-val
inner-val))
(car lists)))
(apply #'combinations (cdr lists)))))
[2]> (combinations '(1 2))
((1) (2))
[3]> (combinations '(1 2) '(3 4))
((1 3) (2 3) (1 4) (2 4))
[4]> (combinations '(1 2) '(3 4) '(5 6))
((1 3 5) (2 3 5) (1 4 5) (2 4 5) (1 3 6) (2 3 6) (1 4 6) (2 4 6))
Thank you very much, that's exactly what I was looking for
– A.Fernandez
Sep 8 '13 at 18:00
Tiny bug: one would expect
(combinations '(1 2) '(3 4) '()) and (combinations '(1 2) '() '(3 4)) to be nil, like (combinations '() '(1 2) '(3 4)). However, the three results are different. Thus the function works if no list beyond the first is empty.– user1220978
Sep 9 '13 at 11:58
(combinations '(1 2) '(3 4) '())
(combinations '(1 2) '() '(3 4))
nil
(combinations '() '(1 2) '(3 4))
@ user1220978: You're right. The problem was that I was using
(if (car lists) to check for the end of the lists, but that would also be false for an empty list argument. I'm editing my answer to use endp to check for the end instead, with this change the function will also correctly return the empty list if it gets any empty lists in its arguments.– Rörd
Aug 6 at 14:19
(if (car lists)
endp
@zck: Sorry, I was confused which of the answers here was mine and which was yours. Anyone, please disregard the parts in my previous comment where I call this "my answer".
– Rörd
Aug 7 at 13:48
Haha, no worries. It was like five years ago, and did fix a bug. :-p
– zck
Aug 7 at 16:21
wvxvw removed their answer that pointed to a function from Alexandria, but it does provide a very similarly named function that actually does what you want. Instead of alexandria:map-combinations, you need alexandria:map-product, e.g.
alexandria:map-combinations
alexandria:map-product
(apply #'alexandria:map-product #'list '((1 2) (1 2)))
evaluates to
((1 1) (1 2) (2 1) (2 2))
I realized I got confused about what OP really wanted. Whether there was a mistake in the example, or the naming, so I decided to remove the answer, just so not to keep the confusion going.
– user797257
Sep 7 '13 at 21:57
By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.
what have you done so far? stackoverflow is not really a service to automagically convert informal specs into CL code. You best ask such questions showing your effort so far.
– Rainer Joswig
Sep 7 '13 at 17:30