如何無序集分成子集在序言

謂語我到目前爲止有：

divide_set(S, Sd) :- 
    length(S, L), 
    between(1, L, N), 
    length(Sd, N), 
    append(Sd, S), 
    forall(member(M, Sd), M \= []).

這給了我這些結果：

?- divide_set([a, b, c, d, e, f], Sd). 
Sd = [[a, b, c, d, e, f]] ; 
Sd = [[a], [b, c, d, e, f]] ; 
Sd = [[a, b], [c, d, e, f]] ; 
Sd = [[a, b, c], [d, e, f]] ; 
Sd = [[a, b, c, d], [e, f]] ; 
Sd = [[a, b, c, d, e], [f]] ; 
...

所以集爲有序設定。但是對待我想[a, f]對於要包括的實例了。

我怎麼能延長我的斷言，這樣我得到的子集，而不是subsquences？

（我能爲每一個可能的順序做，但我認爲這會不會是最好的解決方案）

來源

2017-09-15 Scriptim

依靠太多的任何解決方案'追加/ 3'都將有同樣的問題 –

@DanielLyons有什麼建議？ – Scriptim

我最喜歡的這類問題，主力是['選擇/ 3'（http://www.swi-prolog.org/pldoc/doc_for?object=select/3），但我不完全知道如何申請它對這個問題，因爲你想獲得一些任意數量的集合。儘管如此，你會受到元素數量的限制。 –

哇，那種一個棘手的問題！我首先想到的是去嘗試這樣的事情，一個聲明閱讀：

superset(Superset, Subsets) :- 
    foreach(member(Subset, Subsets), 
    foreach(member(X, Subset), member(X, Superset))).

這看起來不錯的紙，而是用member/2產生導致無限遞歸，因爲它出現幻覺包含綁定變量的大規模名單。所以這沒有奏效。

我的下一個想法是，也許我可以生成所有排列像你的建議。但是，正如我想象的那樣，生成所有的排列，然後圍繞它們建立所有可能的列表，聽起來好像會有很多重複的答案。所以我想到了你的意見，可能有更有效的方法來做到這一點。

然後我開始通過做一些例如輸入/輸出，這是這樣的：

divide_set([X,Y], [[X],[Y]]). 
divide_set([X,Y], [[X,Y]]). 

divide_set([X,Y,Z], [[X],[Y],[Z]]). 
divide_set([X,Y,Z], [[X],[Y,Z]]). 

divide_set([X,Y,Z], [[X,Y],[Z]]). 
divide_set([X,Y,Z], [[X,Z],[Y]]). 
divide_set([X,Y,Z], [[X,Y,Z]]).

這種分類方式他們讓我看到一個辦法：一個在我要麼拉出前項和復發，或拉出前項和它前面加上遞歸的結果，這使我這個執行：

divide_set([X], [[X]]). 
divide_set([X|Remainder], [[X]|Rest]) :- 
    divide_set(Remainder, Rest). 
divide_set([X|Remainder], [[X|Subset]|RestButOne]) :- 
    divide_set(Remainder, Rest), 
    select(Subset, Rest, RestButOne).

我不知道，如果這是正確的，但是這是我的輸出得到您的樣品輸入：

?- divide_set([1,2,3,4], X). 
X = [[1], [2], [3], [4]] ; 
X = [[1], [2], [3, 4]] ; 
X = [[1], [2, 3], [4]] ; 
X = [[1], [2, 4], [3]] ; 
X = [[1], [2, 3, 4]] ; 
X = [[1, 2], [3], [4]] ; 
X = [[1, 3], [2], [4]] ; 
X = [[1, 4], [2], [3]] ; 
X = [[1, 2], [3, 4]] ; 
X = [[1, 3, 4], [2]] ; 
X = [[1, 2, 3], [4]] ; 
X = [[1, 4], [2, 3]] ; 
X = [[1, 2, 4], [3]] ; 
X = [[1, 3], [2, 4]] ; 
X = [[1, 2, 3, 4]] ; 
false.

我還沒有做數學來看看我們應該在組合方面得到什麼，但在第一次臉紅這看起來是正確的。我看到了四個元素所期望的所有不同大小的子集，並且我看到了我所期望的所有不同數量的子集。隨着它進一步進入遞歸，這項工作會減少;你會注意到數字1從未出現在第二個或後續的列表中，2從未出現在第三或第四個子集等中，所以我認爲這是正確的合理的可能性。

而且，你有興趣確實發生場景：

?- divide_set([a, b, c, d, e, f], [[a,f]|Rest]). 
Rest = [[b], [c], [d], [e]] ; 
Rest = [[b], [c], [d, e]] ; 
Rest = [[b], [c, d], [e]] ; 
Rest = [[b], [c, e], [d]] ; 
Rest = [[b], [c, d, e]] ; 
Rest = [[b, c], [d], [e]] ; 
Rest = [[b, d], [c], [e]] ; 
Rest = [[b, e], [c], [d]] ; 
Rest = [[b, c], [d, e]] ; 
Rest = [[b, d, e], [c]] ; 
Rest = [[b, c, d], [e]] ; 
Rest = [[b, e], [c, d]] ; 
Rest = [[b, c, e], [d]] ; 
Rest = [[b, d], [c, e]] ; 
Rest = [[b, c, d, e]] ; 
false.

來源

2017-09-15 19:54:16

如何無序集分成子集在序言

回答

相關問題