使用遞歸的列表子集

我需要編寫一個函數來生成給定列表的所有可能的子集。我相信我應該使用map，但我很努力想出用於迭代的正確語法。我需要在任何地方插入lambda表達式嗎？使用遞歸的列表子集

的(list 1 2 3)的所有可能的子集應當是：通過包括或不包括的每個項目產生冪的

(list (list) 
     (list 1) (list 2) (list 3) 
     (list 1 2) (list 2 3) (list 1 3) 
     (list 1 2 3)))

來源

2013-10-17 user2888512

可能重複[Memory efficiency power set algorithm]（http://stackoverflow.com/questions/7371264/memory-efficient-power-set-algorithm），在鏈接的文章中有一個Scheme實現 –

謝謝。通過權力集算法問題的答案看真的很有幫助。 – user2888512

思考。基本情況是，如果你沒有物品，在這種情況下，功率集是空集的集合。僞代碼將是：

Powerset([]) = [[]] 
Powerset(first:rest) = 
    let subPowersets = Powerset(rest) in 
     [subPowerset for subPowerset in subPowersets] ++ 
     [first:subPowerset for subPowerset in subPowersets]

來源

2013-10-17 00:51:02 Claudiu

謝謝。我現在得到如何設置功能。 – user2888512

你還可以嘗試：

(define power-set 
(lambda (set) 
    (if (empty? set) '() 
     (remove-duplicates (append* (power-set (car set)) 
              (map (lambda (x) (cons (car A) x)) (power-set (cdr A))))))))

雖然我使用此代碼與其他功能，如（設置工會）代替（刪除，複製（追加*。 ..））另外，我根據他們的基數用另一個函數對它們進行分類。

你可以通過閱讀它的數學定義來構造這些簡單的程序。你可以通過閱讀文檔來改進它們（一些數學定義導致'不好'遞歸，你可以嘗試使用tail-recursion）

來源

2013-10-17 17:40:26

使用遞歸的列表子集

回答

相關問題