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.gavanelliReceived on Mon Mar 27 2023 - 09:51:33 CEST
This archive was generated by hypermail 2.3.0 : Tue Jun 04 2024 - 18:13:21 CEST