重複要素を持たないリスト要素のすべての組み合わせ

Question

Alexandriaは、任意の数のリスト引数を取り、各リストから1つずつ順番に要素のすべての組み合わせを生成する関数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)) 

および引数で重複する要素が存在する場合、結果として得られる組み合わせも含むであろういくつかの重複する要素：（1 3 1）及び（1 4 1）を含む

(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)) 

例えば重複します。

私は結果から重複を含むリストをすべて削除したいと思います。

(delete-if-not #'alexandria:setp result) 

が、これは組み合わせの結果の数は数百、典型的には、特に以来、後処理の法外な金額を要求する：私の現在のソリューションは、単純に行うことです。より良い解決策は、最初に重複を生成しなかったmap-productのような関数を書くことです。

ZCKによってLisp: How to get all possible combinations of the elements from lists contained on a list?でのもう一つの柱は、それが内部的に物品税の重複に変更することができように思える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倍遅いことを示しているようです。この関数のより高速なバージョンを得ることは可能ですか？重複する組み合わせはありませんか？あなたは正しさのためにこれをチェックする必要があるかもしれませんが、それはあなたのアイデアを与える必要があります

Answer 1

：

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はのNILをフィルタリングします。そのためには、リストを返す必要があります。つまり、追加されたLIST呼び出しです。メンバーになっていない場合は、リストに何かを追加します。そうでない場合は空のリストが使用されます。

私も&休憩リスト/適用パターンを削除しました。

Q：繰り返しを含むすべてのサブリストはNILに縮小されているため、MAPCAN経由で削除されますか？