Efficiently require a specific cardinality in clpfd

Nice to know
1

I need ways to guarantee that a value occurs exactly once, or at least one, in a list. I’m running out of memory.

It seems global_cardinality, with it’s requirement of specifying all (other) values with wildcards consumes too much memory.

I tried (without success) some other ideas to generate my constraints … :

count_occurrences_in(X, N, List) :-
    maplist(equal_to(X), List, Booleans),
    sum(Booleans, #=, N).

equal_to(X, Y, B) :-
    X #= Y #<==> B.

match_once(Var, [Item], (Var #= Item)).
match_once(Var, [Item | Rest], ((Var #= Item) #\ RestConstraint)) :-
    match_once(Var, Rest, RestConstraint).

from_to_var_arc(From,To,Var,arc(From,Var,To)).   

domain_var_occurs_once(Domain, Var, Vars) :- 
    range_del_element_to_list(Domain, Var, NotVar),
    maplist(from_to_var_arc(zeroVar, zeroVar), NotVar, NotVarArcs0),
    maplist(from_to_var_arc(oneVar, oneVar), NotVar, NotVarArcs1),
    append([[arc(zeroVar, Var, oneVar)], NotVarArcs0, NotVarArcs1] , AllArcs),
    automaton(Vars, [source(zeroVar), sink(oneVar)], AllArcs).

The internals of the constraint solver are beyond me at the moment, so these were just experimental shots in the dark. Any insight is appreciated.

2

Seems my memory problems were (largely) a result of “misuse” of findall.

I was using findall to directly retrieve variables from a list.
Fix was to use findall to retreive indexes of variables, then maplist the indexes.

1 Like