Re: [eclipse-clp-users] On stating a strange constraint

Hi Panagiotis,

this constraint reminds me of a symmetry breaking labeling proposed by 
Pedro Meseguer.

Anyway, what about:

L[0] = 1

forall i>0
	L[i] <= maxlist(L[0..(i-1)]) + 1
?

I hope the intuition is clear, with L[0..(1-i)] I mean the sublist of 
the first i elements of the list L.

Best,
Marco


On 27/03/2023 11:34, Panagiotis Stamatopoulos wrote:
> Hello Everybody,
> 
> I am seeking ideas on how to implement in ECLiPSe a specific
> constraint in a simple, if possible, and efficient way.
> 
> Let L be a list of length N with domain variables ranging
> in 1..M. Acceptable lists are the ones that ...
> 1. ... contain values from 1 up to K (K =< M), but not any
> values from K+1 up to M (K is not given).
> 2. ... satisfy the condition that the first occurrences of
> the values from 1 to K appear in this order in the list.
> 
> For example, let N = 8 and M = 5. The lists [1,1,2,1,2,3,2,1]
> and [1,2,1,3,2,4,3,1] are valid. The first one has K = 3 (only
> items 1, 2, 3 appear in the list) and the second one has K = 4
> (just 5 is missing from the list). In the first list, the first
> occurrences of 1, 2, 3 are in positions 1, 3, 6 and in the second
> list, the first occurrences of 1, 2, 3, 4 are in positions 1, 2,
> 4, 6 in the lists. All fine!
> 
> I believe that the requirement 1 above could be implemented
> easily with the occurrences constraint (one for each number in
> 1..M) and a set of implication (=>) constraints, stating that
> if the number of occurrences of x in 1..M is 0, then the numbers
> of occurrences of x+1, x+2, ... in the list should also be 0.
> I cannot predict the propagation level of this approach, but
> it seems that, at least, declaratively can be stated.
> 
> I don't have any good ideas for the requirement 2. I tried
> something that exploits again the occurrences constraint (for
> every number in 1..M and every prefix list of the given list)
> and then the lex_le constraint. It worked, but if N is around
> 50 or more, the efficiency is unacceptable.
> 
> Any ideas on the above would be more than welcome.
> 
> Best Regards,
> Panagiotis
> 
> 
> _______________________________________________
> ECLiPSe-CLP-Users mailing list
> ECLiPSe-CLP-Users_at_lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/eclipse-clp-users

-- 
Marco Gavanelli
Coordinator of the courses
-L8 Electronics and Computer Science Engineering
-LM29 Electronics Engineering for ICT
-LM32 Computer Science and Automation Engineering
Associate Professor
Ph.D. in Computer Science Engineering
Dept of Engineering
University of Ferrara
Tel/Fax  +39-0532-97-4833
http://docente.unife.it/marco.gavanelli