Frequency capping

Help!
1

What is the cleanest way to implement ‘frequency capping’ in Prolog?

Let’s say I have this code.

item(a).
item(b).
item(c).
item(d).
pairs(First, Second) :- item(First), item(Second).

It returns all permutations of a,b,c,d.

How to introduce a constraint so that the result has no letter in the same position more than twice? E.g. after returning (a,a) and (a,b). (a,c) should be excluded, proceeding to (b,b), excluding (b,c) and so on.

I think it can be viewed as an optimization task but I hope there is an easier solution where I would keep a running total of value occurrences and fail when it exceeds the limit.

Any help is appreciated.

Thank you

2

What is the logic (a,a), (a,b), (b,b)? Normal backtracking gives you (b,a). Using that you would effectively just create the Cartesian product of [a,b] though, which is most likely not what you want. Are you looking for all solution (can be many)? A random one?

If we are just talking about a two-dimensional combination and not too many possible values I guess generating all and filtering is the simplest.

3

I created this toy example for simplification. In our real-time use case, the number of permutation is pretty large, in the millions. It takes a while to get all the solutions but it’s very quick to get the first several solutions. The front-end is user-driven and requests solutions in batches.

To be precise, here is a (truncated) output from running the toy example. I marked the tuples that the frequency cap 2 would exclude.
?- pairs(First, Second).

First = Second, Second = a

First = a,
Second = b

First = a,        <- Exclude, 3rd occurence of First:a
Second = c   <-

First = a,        <- Exclude, 4th occurence of First:a
Second = d    <-

First = b,
Second = a

First = Second, Second = b

First = b,       <-- Exclude, 3rd occurence of First:b
Second = c  <-

First = b,       <-- Exclude, 4th occurence of First:b
Second = d  <--

First = c,       <-- Exclude, 3rd occurence of Second:a
Second = a  <--

First = c,       <- Exclude, 3rd occurence of Second:b
Second = b  <-
.....
4

Answering my own question but still looking for a cleaner way to implement capping.

Here’s what does the trick.

:- dynamic used_times/2.
used_times((_: _), 0) :- !.

cap([]).
cap([(Key:Var, Limit)| Tail]) :-
    used_times((Key:Var), N0),
    N is N0 + 1,
    N =< Limit,
    cap(Tail),
    ignore(retract(used_times((Key:Var), N0))),
    asserta(used_times((Key:Var), N) :- !).

Now I can do, for example:

pairs(A,B), cap([(‘A’:A, 2), (‘B’:B, 1)])

And get an expected answer:

A = B, B = a

A = a,
B = b

A = b,
B = c

A = b,
B = d