發現列表的所有K-長度子集在序言

我需要找到在序言列表的K-長度子集，我有這個功能：發現列表的所有K-長度子集在序言

subset([], []). 
    subset([E|Tail], [E|NTail]):- 
    subset(Tail, NTail). 
    subset([_|Tail], NTail):- 
    subset(Tail, NTail).

，我申請的另一個規則的長度列表，

length(Xs,Size)

問題，是因爲它搜索所有長度的子集，它是非常緩慢的，是有這個K-長度子集的直接遞歸定義？

我搜索了一個星期，並不能找到任何

來源

2013-04-05 Dima

我的意思是（抱歉，如果它看起來smartassing）什麼是你應該嘗試自己，展現你做了什麼，什麼是不爲你工作... – gusbro 2013-04-05 14:45:15

我想這一點，但它不能正常工作，subset_of （K，0，[]，[]）。（K，Len，[X | Xs]，Zs）： L1是Len_1, subset_of（K，L1，Xs，Zs）， L1 == K. 012-subset_of （X，Ys，Zs）： L1 = K. 子集的（K，Xs，Zs）：子集（K，Xs，，Xss）： - length（Xs，Len）， findall（Ys，subset_of（K，Len，Xs，Ys），Xss）。 – Dima 2013-04-05 14:49:47

保持計數記錄的想法是正確的，但不需要使用findall。查看對原始子集程序的簡單修改的答案 – gusbro 2013-04-05 15:11:17

使用您最初的解決方案subset/2，您可以添加另一種說法（LEN）和：

基本情況成立時，萊恩= 0
這增加了元件的遞歸步驟遞減Len和完成遞歸如果新長度= 0

這看起來：

subset(0, [], []). 
subset(Len, [E|Tail], [E|NTail]):- 
    succ(PLen, Len), 
    (PLen > 0 -> subset(PLen, Tail, NTail) ; NTail=[]). 
subset(Len, [_|Tail], NTail):- 
    subset(Len, Tail, NTail).

來源

2013-04-05 15:03:31 gusbro

它看起來不錯，但由於某些原因，它不會更快：\ – Dima 2013-04-05 15:52:32

您可以將第一個子句更改爲「subset（0，_，[]）： - ！。」，就像Len爲零無論輸入列表如何，結果都必須是空列表......不知道它是否真的可以顯着提高性能。 – gusbro 2013-04-05 16:02:56

仍然是相同的速度.... – Dima 2013-04-05 16:24:12

發現列表的所有K-長度子集在序言

回答

相關問題