沒有重複元素的列表元素的所有組合

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

沒有重複元素的列表元素的所有組合

回答

相關問題