Efficiently require a specific cardinality in clpfd

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).

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.

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