Prolog, optimize generation

1
votes

I wrote a prolog program which generates all possible positions of elements in a two-dimensional table. The number of elements and the table size are given.

My code:

geni(Min, Min, Max) :- Min =< Max.
geni(Min, X, Max) :- Max >= Min, MinInc is Min+1, geni(MinInc, X, Max).
generate(_, 0, []) :- !.
generate(TSize, N, [X|Tail]) :- X=k(X1,Y1), geni(1,X1,TSize), 
                                geni(1,Y1,TSize), NDec is N-1, 
                                generate(TSize,NDec, Tail), not(member(X, Tail)).

(where TSize is the size of the table, N is the number of elements, and the last one is the result)

Predicate 'geni' generates number X in interval [A;B].

Example (2 elements in 2x2 table):

?- generate(2, 2, R).
R = [k(1, 1), k(1, 2)] ;
R = [k(1, 1), k(2, 1)] ;
R = [k(1, 1), k(2, 2)] ;
R = [k(1, 2), k(1, 1)] ;
R = [k(1, 2), k(2, 1)] ;
R = [k(1, 2), k(2, 2)] ;
R = [k(2, 1), k(1, 1)] ;
R = [k(2, 1), k(1, 2)] ;
R = [k(2, 1), k(2, 2)] ;
R = [k(2, 2), k(1, 1)] ;
R = [k(2, 2), k(1, 2)] ;
R = [k(2, 2), k(2, 1)] ;
false.

It works correctly but is too slow when I use higher numbers. I think the predicate 'geni' is good but something is wrong with 'generate'. How could I optimize it?

3
optimizationprolog
the number of possible ways to arrange k elements in an nxn array is (n^2)!/(n^2 - k)! this results in very large numbers even for relatively small values of n and k. so if you're actually iterating through all the possibilities your program is bound to be slow. - yurib
In this case I would like to solve problem with chess table and knights. There all elements are equal.Does it change anything? - Martynas
Your EDIT is worth a new question, this one has been solved. (I'll post my answer there :) - Cephalopod
I asked new question about the problem in EDIT here stackoverflow.com/questions/4421233/… - Martynas

3 Answers

3
votes

Notwithstanding any algorithmic optimizations, what you should always do is use tail recursion: The recursive call must be the last one in your predicate, this way the prolog interpreter can do a much faster loop instead of a true recursion because it can drop stack frames of former function calls, knowing that there will not be any code after the call, so inner variables are not needed anymore.

Tail recursion is usually achieved by introducing an additional function (here: predicate) argument that serves as an accumulator in which the final result is accumulated while the recursion runs, and then in the final recursive step, the accumulator holds the complete result. It is then simply passed back up though the recursion steps.

generate_new(TSize, N, Result) :- generate_new(TSize, N, [], Result).

generate_new(_, 0, Result, Result) :- !.

generate_new(TSize, N, Temp, Result) :-
                    geni(1, X1, TSize),
                    geni(1, Y1, TSize),
                    X = k(X1, Y1),
                    NDec is N - 1,
                    \+ member(X, Temp),
                    generate_new(TSize, NDec, [X|Temp], Result).
3
votes

Let's have a closer look how the alogrithm works. It has 3 parts:

1) Generate X

X=k(X1,Y1), geni(1,X1,TSize), 
geni(1,Y1,TSize),

2) Generate Tail

NDec is N-1, 
generate(TSize,NDec, Tail),

3) Check everything matches

not(member(X, Tail)).

On every recursion level, it will be executed somehow like this:

1) Generate an X, 2) generate a tail, 3) check fails, 2) generate another tail, 3) check fails again ...

So basically on every level your alogrithm generates a lot of tails to find one that matches the current X. And for each of these lots of tails, even more tails have to be generated on the next recursion level.

So just generate the tail first and the find a matching X.

generate(TSize, N, [X|Tail]) :-
    NDec is N-1, generate(TSize,NDec, Tail),
    X=k(X1,Y1), geni(1,X1,TSize), geni(1,Y1,TSize), 
    not(member(X, Tail)).

Long story short: because of the backtracking approach do the expensive things (like recursion) first.

0
votes

This is not a complete answer but if you are using SWI-Prolog, then instead of your geni/3 you can use between/3 which is probably faster.