如何使用Common Lisp獲取列表的所有可能組合？

我想寫一個Common Lisp函數，它會給我列出所有可能的排列，每個元素只能使用一次。例如，列表'（1 2 3）將給出輸出（（1 2 3）（1 3 2）（2 1 3）（2 3 1）（3 1 2）（3 2 1））。如何使用Common Lisp獲取列表的所有可能組合？

我已經寫了一些這樣的作品，但它笨重，它並不總是工作，我甚至都沒有真正理解它。我不是在尋求代碼，只是想了解如何思考它的一些指導。我對寫算法不太瞭解。

感謝，傑森

來源

2010-01-18 Jason

通常這是一個好主意，發佈你寫的代碼到目前爲止。這樣，我們可以看到你在想什麼... – 2010-01-18 17:30:16

如果這是功課，請標記爲這樣。 – 2010-01-19 08:12:37

這不是家庭作業。我故意省略了我到目前爲止的代碼。我不想用我有缺陷的想法來玷污答案。 – Jason 2010-01-19 20:41:04

-2

我不知道，如果你的問題是關於Common Lisp的，或有關的算法。

這裏還有其他語言的類似問題（和解決方案），例如Python。通常可以將Python翻譯成Common Lisp，然後選擇一個並移植它？ :-)

來源

2010-01-18 17:02:46 Ken

作爲基本方法，「所有排列」遵循這個遞歸模式：

 
    all permutations of a list L is: 
    for each element E in L: 
     that element prepended to all permutations of [ L with E removed ]

如果我們給出你的列表中有沒有重複的元素，下面應該做的：

 
(defun all-permutations (list) 
    (cond ((null list) nil) 
     ((null (cdr list)) (list list)) 
     (t (loop for element in list 
      append (mapcar (lambda (l) (cons element l)) 
          (all-permutations (remove element list)))))))

來源

2010-01-18 17:09:00 Vatine

謝謝！這有點像我的，但有一些小而重要的區別。我看到的唯一問題是（全排列'（1 2 3））和（全排列'（1 1 2 3））給出了相同的結果，但這應該很容易改變。（我的最終目標是爭奪單詞。） – Jason 2010-01-19 20:51:10

如果您有難以區分的元素，它會變得有點棘手，您需要執行一些預處理以避免多次生成「相同」排列。但是，不要像上面那樣使用列表，而是使用（SYMBOL。COUNT）向量作爲您傳遞的數據結構，並且減少計數（在副本上！）而不是刪除應該照顧到這一點。 – Vatine 2010-01-20 06:42:49

（defun定義排列（）（標籤（（DO-排列（項目）（如果項目（mapcan（拉姆達（X）（mapcar（拉姆達（Y）（利弊XY））（DO-排列（刪除（））））（do-permutations'（「Guy」「Man」「Dude」）））） – 2018-02-10 13:55:51

瀏覽您的列表，依次選擇每個元素。這個元素將是你當前排列的第一個元素。

將該元素賦予其餘元素的所有排列。

來源

2010-01-18 17:09:16

下面是允許重複元素的答案。該代碼是更「lispish」，因爲它不使用循環，具有比賴Joswig的解決方案不太理解的缺點：

(defun all-permutations (lst &optional (remain lst)) 
    (cond ((null remain) nil) 
     ((null (rest lst)) (list lst)) 
     (t (append 
      (mapcar (lambda (l) (cons (first lst) l)) 
        (all-permutations (rest lst))) 
      (all-permutations (append (rest lst) (list (first lst))) (rest remain))))))

可選留個參數用來cdring在列表中向下，旋轉列表元素進入遞歸之前。

來源

2011-12-09 16:31:34

如果唯一排列可以將cond包裝在remove-duplicates中需要 – mcheema 2017-01-03 18:30:10

如何使用Common Lisp獲取列表的所有可能組合？

回答

相關問題