在序言

k個元素列表的所有子集

請幫幫我來解決這個問題：在序言

子集（N，[1,2,3]，L）。

如果N = 2，我想要的結果是：

[1,2];

[2,1];

[1,3];

[3,1];

[2,3];

[3,2];

（以任意順序）

來源

2012-01-31 Welcome789

如果它的家庭作業請標籤作爲這樣 – CapelliC 2012-01-31 12:36:41

選擇/ 3這是內置，可以幫助你解決這個小問題 – CapelliC 2012-01-31 12:39:50

請不要只是發佈你的任務，但顯示一些努力。你有什麼嘗試？ – 2012-01-31 15:56:46

那麼，你的基本情況很簡單：

subset(0,Lst,[]).

如果N> 0，你有2種選擇，以什麼做LST的第一要素：

你可以忽略它，並期待您的子集，剩下的LST
您可以包括在您的子集，將它添加到您獲得的剩餘Lst的1個較小子集中。

您可能認爲您必須擔心Lst太短（或N太大：同樣的事情），但是如果您已經正確編碼了上述內容，則應該爲您照顧。

呃，這足以讓你開始。

來源

2012-01-31 16:59:44

我的解決方案：
subset（0，_，[]）。子集（N，[X | T]，[X | R]）： - \t N> 0,\t N1是N-1子集（N1，T，R）。（N，[_ | T]，R）： - N> 0，子集（N，T，R）。
結果是：
[1,2]; [1,3]; [2,3]; – Welcome789 2012-02-01 07:37:25

您的解決方案的結果看起來像您最初所說的需要，除了反向重複項。如果你仍然需要它們，你需要一個規則來產生與你現在產生的東西相反的東西。 – 2012-02-01 12:46:29

我試圖用SWI-Prolog內置謂詞反轉來反轉我的列表。但它不起作用。 – Welcome789 2012-02-01 14:04:11

我重寫此解決方案：（基於：Permuted combinations of the elements of a list - Prolog）

subset(N, InList, Out) :- 
    splitSet(InList,_,SubList), 
    permutation(SubList,Out), 
    length(Out, N). 

splitSet([ ],[ ],[ ]). 
splitSet([H|T],[H|L],R) :- 
    splitSet(T,L,R). 
splitSet([H|T],L,[H|R]) :- 
    splitSet(T,L,R).

結果（在SWI-Prolog的測試）：

?- subset(2,[1,2,3],R). 
R = [2, 3] ; 
R = [3, 2] ; 
R = [1, 3] ; 
R = [3, 1] ; 
R = [1, 2] ; 
R = [2, 1] ; 
false.

來源

2012-02-06 14:57:51 Welcome789

回答

相關問題