Stuck on an infinite loop in prolog

I'd like my program to find me all sub-sets of size K of the integers 1,2,...,N.

For this, I wrote the following subs(N,X,Y) means that X is a sub-set of size N of the set Y. I defined the following:

subs(0,[],X).
subs(N,[A|R1],[A|R2]):-N>0, N1 is N-1, subs(N1,R1,R2).
subs(N,[A|R1],[B|R2]):-subs(N,[A|R1],R2).
subs(N,[A|R1],[B|R2]):-subs(N,R1,[B|R2]).

And then as a check I ran subs(2,X,[1,2,3,4]).

I got the first answer [1,2], but never did it give a second answer, as it got stuck in an infinite loop. I tried to trace it, and seems that after finding the first answer it does:

   Redo: (8) subs(0, _G613, [3, 4]) ? creep
^  Call: (9) 0>0 ? creep
^  Fail: (9) 0>0 ? creep
   Redo: (8) subs(0, _G613, [3, 4]) ? creep
   Call: (9) subs(0, [_G618|_G619], [4]) ? creep
^  Call: (10) 0>0 ? creep
^  Fail: (10) 0>0 ? creep
   Redo: (9) subs(0, [_G618|_G619], [4]) ? creep
   Call: (10) subs(0, [_G618|_G619], []) ? creep
   Fail: (10) subs(0, [_G618|_G619], []) ? creep
   Redo: (9) subs(0, [_G618|_G619], [4]) ? creep
   Call: (10) subs(0, _G619, [4]) ? creep
   Exit: (10) subs(0, [], [4]) ? creep
   Exit: (9) subs(0, [_G618], [4]) ? creep
   Exit: (8) subs(0, [_G618], [3, 4]) ? creep
   Exit: (7) subs(1, [2, _G618], [2, 3, 4]) ?

So I see that I get stuck with subs(0, _G619, [4]). Does someone have an idea of how to overcome this problem?

Thanks

Solution

Your 4th clause has a flaw. The head of the second argument (the subset) has a variable A which is singleton. The clause basically reads, [A|R1] is a subset of N values from [B|R2] if R1 is a subset of N values from [B|R2], for any variable A. That wouldn't be a correct rule for a subset, and results in the infinite loop since it doesn't ultimately reduce to the base case. It's not clear what the purpose of this rule is. You can probably just remove it as the first 3 adequately define the subset.

You also should constrain N in the 3rd clause to avoid duplicate overlap of rule matching.

That plus a little variable clean-up makes your predicate into:

subs(0, [], _).
subs(N, [A|R1], [A|R2]) :- N > 0, N1 is N-1, subs(N1, R1, R2).
subs(N, R1, [_|R2]) :- N > 0, subs(N, R1, R2).