How to transform a list of integers (solutions) into a list of continuous intervals

Question

I have written a CSP program using CLP(FD) and SWI-Prolog.

Some constraints look like Xi mod N #= 0, so I have to call res(Xi,Li) (with res(X,L) :- setof(X, indomain(X), L)) for each variable Xi to do backtracking and get the list of effective solutions. If I don't do that, I get residual goals.

Now in the same call I want to convert this list of solutions for Xi into a list of continuous intervals. How can I do that ? Are there any existing predicates to do that ?

I tried using fd_dom(Li,Di), dom_intervals(Di,Ii) with no success as Li needs to be atomic, not a list.

dom_intervals is defined as follows, please see Getting intervals with CLP :

dom_intervals(Dom, Intervals) :-phrase(dom_intervals1(Dom), Intervals).
dom_intervals1(I) --> {integer(I)}, [I].
dom_intervals1(L..U) --> [L..U].
dom_intervals1(D1 \/ D2) --> dom_intervals1(D1), dom_intervals1(D2).

I also tried calling member(Xtmpi, Li) before fd_dom(Xtmpi,Di), dom_intervals(Di,Ii) but member enumerates results so I get a list of singletons.

Thanks in advance for your ideas.

Answer 1

It seems a bit wasteful to generate a full sequence and then compress it back down again, but I didn't find a way to resolve the fd_domain without doing that, so here's a numbers-to-consecutive-ranges grammar.

Usage:

?- phrase(ranges(Rs), [2, 4,5,6, 10, 22,23,24,25,26,27,28,29,30]).
Rs = [2, 4-6, 10, 22-30]

Code:

:- use_module(library(dcg/basics)).

ranges([R|Rs]) -->          % a list of ranges:
    [A], range(A,B),        % a number A begins a range from A to B,
    {(A=B -> R=A ; R=A-B)}, % output single values as 2, ranges as 2-9
    ranges(Rs).             % then more ranges up to ...

ranges([])     --> eos.     % ... end of stream.


range(A,Z) -->       % a range continues if:
    {succ(A,B)},     % the next number should be B,
    [B],             % and yes, B is next in the list,
    range(B,Z).      % and the range continues from B..end.
 
range(A,A), [C] -->  % a range ends if:
    {succ(A,B)},     % the next number should be B
    [C], {dif(B,C)}. % the next number is C, which is different.
    
range(A,A) --> eos.  % or a range ends at the end of stream.