CODEWITHSUNDEEP
prologclpfdswi-prolog-for-sharing
Stephen Foster
Stephen Foster

Reputation: 399

How to bound all combinations prolog search with clp(fd)?

The thing I wanted to do was generate all combinations of elements from a given list. E.g.: From [a,b,c], I might want:

[]
[a]
[b]
[c]
[a,a]
[a,b]
[a,c]
[b,a]
...

And so on. Perhaps there is a magical prolog one-liner that does this. If so, I would love to hear it.

However, my question is less about solving this particular problem and more of a request that someone explain some subtleties of Prolog's search algorithm for me.

So here's what I did first to solve the above problem:

members([], _).
members([X|Xs], List) :-
  member(X,List),
  members(Xs, List).

This works great but returns all possible results, and not in a great order:

[]
[a]
[a,a]
[a,a,a]

Okay, that's no problem. I really just want all combinations up to a certain length. So I decided to first get the ones that have exactly a particular length:

membersWithLength(Members, List, Bound) :-
  L = Bound,
  length(Members, L),  members(Members, List).

This works great, e.g. for length 2:

[a,a]
[a,b]
[a,c]
...

And so on. Now my attempt to use clpfd to leverage the above function to get all lists up to a certain length went awry:

:- use_module(library(clpfd)).


membersLessThan(Members, List, Bound) :-
  L in 0..Bound,  % I also tried L #=< Bound
  membersWithLength(Members, List, L).

Kind of works. Finds the right results (lists with length less than Bound). But after it finds them, it loops continuously searching for more results. E.g. for length 2:

[]
[a]
[b]
[c]
[a,a]
[a,b]
...
[c,c]
Hangs looking for more solutions.

I guess this is the heart of my question. Can someone explain why (according to the trace) prolog continues to check larger and larger lists as possible solutions, even though they are all doomed to failure? And can someone tell me if there's a way to help prolog avoid this doomed journey?

I ultimately used the following code to solve the problem, but I was disappointed that I couldn't figure out how to use clpfd's integer constraints to constrain the size of the lists.

membersLessThan_(Members, List, Bound) :-
  numlist(0,Bound,ZeroToBound),
  member(L, ZeroToBound),
  membersWithLength(Members, List, L).

Here is all the relevant code on SWISH: http://swish.swi-prolog.org/p/allcombos.pl

Upvotes: 1

Views: 340

Answers (1)

Joan
Joan

Reputation: 99

With you original implementation of members, if you want to enumerate all the answers you can do:

length(L, _), members(L, [a,b,c]).

which gives you the answers:

L = [] ;
L = [a] ;
L = [b] ;
L = [c] ;
L = [a, a] ;
L = [a, b] ;
L = [a, c] ;
L = [b, a] ;
L = [b, b] ;
L = [b, c] ;
L = [c, a] ;
L = [c, b] ;
L = [c, c] ;
L = [a, a, a] ;
L = [a, a, b] ;
L = [a, a, c] ;
L = [a, b, a]

This is a common idiom for iterative deepening, which allows you to list all the answers fairly. I don't think clpfd can help you in this case.

EDIT

I see that in the title you explicitly ask about CLPFD. The reason your code doesn't work is that when you do 

L in 0..Bound

you are not actually enumerating those values. For the next predicates, L is still unbound and carries a constraint. So membersWithLength will keep looping trying new lengths, and once the length it's instantiated, it will see that the constraint fails and try again. You can see it in these examples:

L in 0..2, length(X, L)

loops like in your code, because length keeps trying. If you want to limit it, L has to be instantiated before calling length. You can use label for that. This next example doesn't loop:

L in 0..2, label([L]), length(X, L)

Upvotes: 0

Related Questions