序言：長度爲k的子集

Question

在我們過了subset_of/2謂詞，我的老師給的類如下：

subset_of([],[]). 
subset_of([X|Xs],Zs):-subset_of(Xs,Ys),maybe_add(X,Ys,Zs). 

maybe_add(_,Ys,Ys). 
maybe_add(X,Ys,[X|Ys]). 

subsets_of(Xs,Xss):-findall(Ys,subset_of(Xs,Ys),Xss). 

然後，他問我們將其更改爲只給一些長度爲K的子集（但不通過使用length/2，直接找到遞歸定義）。我的第一個嘗試是將subset_of調用分解爲一個添加額外元素和一個不調用（而不是具有maybe_add調用）的元素，並跟蹤傳遞的列表長度並在最後檢查，但這沒有按計劃運作。

subset_of(K, 0, [],[]). 
subset_of(K, Len, [X|Xs],Zs):- 
     L1 is Len - 1, 
     subset_of(K, L1, Xs, Zs), 
     L1 == K. 
subset_of(K, Len, [X|Xs],Zs):- 
     L1 is Len - 1, 
     subset_of(K, L1, Xs,Ys), 
     do_add(X, Ys, Zs), 
     Len == K. 
subsets_of(K,Xs,Xss):- 
     length(Xs, Len), 
     findall(Ys,subset_of(K, Len, Xs,Ys),Xss). 

我不是要求正確的代碼來解決這個問題，但只是在正確的方向推，所以我可以不斷嘗試弄清楚。這是我第一次用聲明式的語言，我很困惑。

Answer 1

如果你不想要一個直接的答案，比我說它可以做得簡單得多。我的解決方案中有3條規則。但是，我不使用這個額外的maybe_add公式或其他任何可能的結果。如果你真的需要它，它可以被使用，然後它需要5個參數 - 3個輸入參數和2個輸出參數。與原始解決方案一樣，這將subset_of的規則數量減少到只有2個。畢竟他們非常相似。

還要小心重複。我認爲subset_of(0, _, [])正如其他答案中的建議可能是導致重複的一種方式。然而，可能有一個合併它的正確解決方案，我不確定沒有。

認爲它是正確性的證明。假設你想遞歸地證明一個集合是另一個集合的K元素子集。你將如何去做。看看你使用的含義。你怎麼能把它們變成Prolog的規則？

Answer 2

不使用maybe_add似乎是一個好主意。然而，你不需要兩個額外的參數：一個會做。您的基本子句將爲

subset_of(0, _, []). 

即，空集是任何東西的零元子集。在兩個遞歸子句中，一個子查找K-1 -element子集，另一個查找K大小的子集。