CODEWITHSUNDEEP
listprolog
dntf0llow
dntf0llow

Reputation: 1

Create a predicate that returns lists that meet certain conditions

I was trying to create a predicate example(N, L), where L is a list that for given N:

Also, before appearence of number n, we expect every number from {1, ..., n-1} to appear at least once

For example, 

`?- example(3, L).
L = [1, 1, 2, 2, 3, 3] ;
L = [1, 1, 2, 3, 3, 2] ;
L = [1, 2, 2, 1, 3, 3] ;
L = [1, 2, 2, 3, 3, 1] ;
L = [1, 2, 3, 3, 2, 1] ;
L = [1, 2, 3, 1, 2, 3] ;`

So my idea was to create a list like 1_2_3_...n_, filling all "_" with permutations of n-sized set. For N = 2, I would get 1 1 2 2, 1 2 2 1 meeting all conditions. I tried a lot of times, but still have no idea how to create such a structure in SWI. I would appreciate any hint, thanks in advance.

Upvotes: 0

Views: 62

Answers (1)

damianodamiano
damianodamiano

Reputation: 2662

To give you an idea on how to solve this task using clpfd library, i wrote part of the solution:

:- use_module(library(clpfd)).

gapBetweenElements(_,C,N):-
    C > N.
gapBetweenElements(L,C,N):-
    C =< N,
    N1 #< N2,
    N2 - N1 #= T,
    T rem 2 #= 1,
    element(N1,L,C),
    element(N2,L,C),
    C1 is C+1,
    gapBetweenElements(L,C1,N).

countElement([],_,[]).
countElement([H|T],E,[HB|TB]):-
    HB in 0..1,
    H #= E #<==> HB #= 1,
    countElement(T,E,TB).

occurrencesNumber(_,C,N,_):-
    C > N.
occurrencesNumber(L,C,N,Times):-
    C =< N,
    countElement(L,C,LB),
    sum(LB,#=,Times),
    C1 is C+1,
    occurrencesNumber(L,C1,N,Times).

applyDomain([],_).
applyDomain([H|T],V):-
    H in 1..V,
    applyDomain(T,V).

example(N,L):-
    Len is 2*N,
    length(L,Len),
    applyDomain(L,N),
    occurrencesNumber(L,1,N,2),
    gapBetweenElements(L,1,N),
    label(L).

With length/2 you constrain the list to be made of Len elements. With applyDomain/2 you can set the domain for each element (in this case, from 1 to N). With occurrencesNumber/4 you constraint the list to contain each element, exactly two times (note that, to count the element in the list, i used countElement/3 wich counts each element using reification variables. This might not be the best solution because reification varibles don't do much propagation...). With gapBetweenElements/3 you impose that the gap between same elements must be even. Finally with label/1, you can search for the solution.

?- example(3,L).
L = [1, 1, 2, 2, 3, 3]
L = [1, 1, 2, 3, 3, 2]
L = [1, 1, 3, 2, 2, 3]
L = [1, 1, 3, 3, 2, 2]
and so on...

Now you need to implement the last constraint, as you said: "before appearence of number n, we expect every number from {1, ..., n-1} to appear at least once".

Upvotes: 1

Related Questions