Generate all pairs that sum to given number

Question

I'm trying to generate all pairs X, Y that sum to given number Z using the following predicates:

genN(0).
genN(X) :- 
    genN(Xprev), 
    X is Xprev + 1.

sum2(X, Y, Z) :- 
    X + Y =:= Z.

allSum2(X, Y, Z) :- 
    genN(X), 
    X < Z, 
    genN(Y), 
    Y < Z, 
    sum2(X, Y, Z).

I'm using
genN to generate all natural numbers
sum2 checks if given 3 numbers X, Y, Z then X + Y = Z.

Then the logic of allSum2 is to
generate all pairs X and Y such that X and Y are smaller than Z and
to check if they sum up to Z.

Unfortunately I get stuck in generating infinitely many Ys and I do not understand why.

Can someone explain it to me?

Because `genN(Y)` is nested "deeper" in the `allSum2/3` predicate, and thus that is the first backtracking point. Yes `Y < Z` might let each attempt fail, but `genN/1` will keep suggesting new values, hence the infinite loop. — Willem Van Onsem, Dec 13 '18 at 19:46
Why then when I ask allSum2(X, Y, 5). I do not see X = 0, Y = 5 as an answer? — Zarrie, Dec 13 '18 at 19:57
Because then the `Y < Z` constraint fails, since `5 < 5` is false. — Willem Van Onsem, Dec 13 '18 at 19:58
Of interest: [Combing generator results and writing result to stream](https://stackoverflow.com/q/42904186/1243762) The question is broader than what you seek, but the accepted answer covers what you need. — Guy Coder, Dec 13 '18 at 20:10
This is ideally handled using CLP(FD): `addends(A1, A2, Sum) :- [A1, A2] ins 0..sup, A1 + A2 #= Sum, label([A1, A2]).` Call it as, `addends(X, Y, 5)`. Include additional constraints if you wish (like `A1 < A2`). — lurker, Dec 13 '18 at 20:16
Basically one here perhaps should use *diagonal enumeration*. — Willem Van Onsem, Dec 13 '18 at 20:17
@WillemVanOnsem `diagonal enumeration` I think I know what you are talking about but a link would confirm it. — Guy Coder, Dec 13 '18 at 20:19
@WillemVanOnsem Is this it [Cantor's diagonal argument](https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument) ? — Guy Coder, Dec 13 '18 at 20:21
@GuyCoder no, it's the [other diagonals](https://cs.stackexchange.com/a/97610/2909), perpendicular to the Cantor's. Or [this](https://hackage.haskell.org/package/control-monad-omega-0.3.1/docs/Control-Monad-Omega.html#v:diagonal). My code enumerates the diagonals down up, while the other code enumerates them top down AFAICS. — Will Ness, Dec 14 '18 at 12:38
@WillemVanOnsem Leaning Haskell is on the list, but it keeps moving down. Makes you wonder what is getting put on the list ahead of Haskell? — Guy Coder, Dec 14 '18 at 12:50
@GuyCoder I'm sorry, that's what I've got on it right now. It's nothing fancy, we just take lists from the list of lists one-by-one, and order them in a jagged fashion. imagine we have a bunch of rows one under another; then we push row at index 1 from top (zero-based) 1 notch to the right, at index 2 -- 2 notches to the right, etc. then we collect the elements in the resulting columns, top down. what we get are the diagonals. (I've edited my code in the first link to this effect, too, in the mean time). — Will Ness, Dec 14 '18 at 13:50

Generate all pairs that sum to given number

0 Answers0