没有重复元素的列表元素的所有组合

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倍。获得这个函数的更快版本是否可行，但没有重复的组合？

来源

2017-06-07 davypough

'地图product'通常不能采取的参数的任意数量。查看变量'CALL-ARGUMENTS-LIMIT'。你的'COMBINATIONS'功能有同样的限制。 –

感谢您的提醒。看起来这不会是一个问题，至少在SBCL！ CALL-ARGUMENTS-LIMIT = 4611686018427387903。 – davypough

您可能需要检查这是否正确，但它应该给你一个想法：

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删除？

来源

2017-06-07 04:25:56

没有重复元素的列表元素的所有组合

回答

相关问题