All subset of list with k elements in Prolog

Question

Please help me to solve this problem:

subset(N, [1,2,3], L).

if N=2, I want the result is that:

[1,2];

[2,1];

[1,3];

[3,1];

[2,3];

[3,2];

(in any order)

select/3 it's the builtin that can help you to solve this little problem — CapelliC, Jan 31 '12 at 12:39
Please, don't just post your assignment, but show some effort. What have you tried? — Fred Foo, Jan 31 '12 at 15:56
My solution:
subset(0, _, []).
subset(N, [X | T], [X | R]) :- N > 0, N1 is N - 1, subset(N1, T, R).
subset(N, [_ | T], R) :- N > 0, subset(N, T, R).
The result is that:
[1,2];[1,3];[2,3]; — Welcome789, Feb 01 '12 at 07:19

score 2 · Answer 1 · edited May 23 '17 at 10:29

I rewrite this solution: (based on: 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).

The result (tested in 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.

score 1 · Accepted Answer · answered Jan 31 '12 at 16:59

1

Well, your base case is trivial:

subset(0,Lst,[]).

If N>0, you have 2 choices as to what to do with the first element of Lst:

You can ignore it, and look for your subset in what remains of Lst
You can include it in your subset, adding it to what you get for a 1-smaller subset of what remains of Lst.

You might think you have to worry about Lst being too short (or N being too big: same thing), but if you've coded the above properly, it should be taken care of for you.

Hoep that's enough to get you started.

answered Jan 31 '12 at 16:59

Scott Hunter

48,888
12
60
101

My solution:
subset(0, _, []).
subset(N, [X | T], [X | R]) :- N > 0, N1 is N - 1, subset(N1, T, R).
subset(N, [_ | T], R) :- N > 0, subset(N, T, R).
The result is that:
[1,2];[1,3];[2,3]; – Welcome789 Feb 01 '12 at 07:37
The result from your solution looks like it has what you originally said you needed, except for the reversed-duplicates. If you still need them, you'll need a rule that produces the reverse of what you produce now. – Scott Hunter Feb 01 '12 at 12:46
I tried to reverse my list with SWI-Prolog built-in predicate reverse. But it doesn't work. – Welcome789 Feb 01 '12 at 14:04
Not sure what you mean by "doesn't work", but even if it did, it wouldn't solve the problem for N>2. What you need is instead of always taking the first element of the list out, you need to take an arbitrary element out so that all permutations will be possible. – Scott Hunter Feb 01 '12 at 14:24

All subset of list with k elements in Prolog

2 Answers2