FD: Minimizing nondistinct

[Torsten Anders]

Hi,

in some FD problem I want to minimize the number of nondistinct elements in a 
list. I can not use FD.distinct, because this would result in an 
over-constraint problem.

I therefore thought of counting the nondistinct pairs and then minimizing 
this number by a best solution search. This does work, but the number of 
pairs to check within a list grows very fast by increasing the list length. 
The resulting mass of propagators slow down the search very very much.

Below is my first attempt. For simplicity reasons I ommitted all further 
constraints (i.e. the example below could indeed use FD.distinct).

Any ideas to enhance this? I thought of using FD.distinctOffset and then 
minimizing the number of different offset values (do not know yet whether 
that really simplifies things).

Or would you propose to write a special propagator (in C++)? The propagator 
may get the number of element pairs which do not need to be distinct as an 
additional arg (no idea either, how to write something like that)...

Thank you,
Torsten Anders

----------------------------


declare
proc {HowManySame L N}
   fun {Aux L}
      X = {Nth L 1}
      Lr = {List.drop L 1}
   in  
      if {Length Lr} > 0
      then {Append {Aux Lr}
	    {Map Lr proc {$ Y B}
		       B = (X =: Y)
		    end}}
      else nil
      end
   end
in
   {FD.decl N}
   {FD.sum {Aux L} '=:' N}
end

{ExploreBest			
 proc {$ Sol}
    L X N=15	% increasing N quickly increases nr of propagators
 in
    Sol = sol(satisfaction: X solution: L)
    {FD.list N 1#N L}
    {HowManySame L X}
    {FD.distribute ff L}
 end
 proc {$ Old New}
    Old.satisfaction >: New.satisfaction
 end}

-
Please send submissions to users at mozart-oz.org
and administriva mail to users-request at mozart-oz.org.
The Mozart Oz web site is at http://www.mozart-oz.org/.