没有重复元素的列表元素的所有组合
问题描述:
Alexandria具有函数map-product
,该函数接受任意数量的列表参数,并按顺序生成元素的所有组合(每个列表一个元素)。例如:没有重复元素的列表元素的所有组合
(alexandria:map-product 'list '(1 2) '(3 4) '(5 6))
=> ((1 3 5) (1 3 6) (1 4 5) (1 4 6) (2 3 5) (2 3 6) (2 4 5) (2 4 6))
并且当存在在参数重复的元素,所产生的组合也将含有一些重复的元素:
(alexandria:map-product 'list '(1 2) '(3 4) '(5 1))
=> ((1 3 5) (1 3 1) (1 4 5) (1 4 1) (2 3 5) (2 3 1) (2 4 5) (2 4 1))
其中(1 3 1)和(1 4 1)含有重复。
我想除去含有从结果重复所有这样的列表。我目前的解决方案是简单地做:
(delete-if-not #'alexandria:setp result)
但是这需要后期处理的金额过高,特别是导致组合的数量通常在数百人。一个更好的解决办法是写像map-product
一个函数,并没有产生在首位重复。
在Lisp: How to get all possible combinations of the elements from lists contained on a list?另一篇文章由ZCK提供大致相当于map-product
这似乎是它的功能可以被修改,以内部消费税重复:
(defun combinations (&rest lists)
(if (car lists)
(mapcan (lambda (inner-val)
(mapcar (lambda (outer-val)
(cons outer-val
inner-val))
(car lists)))
(apply #'combinations (cdr lists)))
(list nil)))
然而,这不是明摆着要我如何插入重复测试。此外,一个简单的计时跑,似乎表明该函数比alexandria:map-product
慢约16倍。获得这个函数的更快版本是否可行,但没有重复的组合?
答
您可能需要检查这是否正确,但它应该给你一个想法:
CL-USER 40 > (defun combinations-1 (lists)
(if (car lists)
(mapcan (lambda (inner-val)
(mapcan (lambda (outer-val)
(unless (member outer-val inner-val)
(list (cons outer-val inner-val))))
(car lists)))
(combinations-1 (cdr lists)))
(list nil)))
COMBINATIONS-1
CL-USER 41 > (combinations-1 '((3 2) (1 2) (5 1)))
((3 1 5) (2 1 5) (3 2 5) (3 2 1))
另一个MAPCAN代替MAPCAR过滤近等基因系。为此,我们需要返回列表,从而添加LIST调用。我们只在列表中添加一些内容,如果它不是成员,则使用空列表。
请注意,我也去掉了&其余列表/应用模式。
问:与重复减至零的所有子列表,使他们通过MAPCAN删除?
'地图product'通常不能采取的参数的任意数量。查看变量'CALL-ARGUMENTS-LIMIT'。你的'COMBINATIONS'功能有同样的限制。 –
感谢您的提醒。看起来这不会是一个问题,至少在SBCL! CALL-ARGUMENTS-LIMIT = 4611686018427387903。 – davypough