As simple generator for states: based on an inductive definition.
A state is a sequence of 5 numbers between 1 and 5.
We represent it with an SWI-Prolog dict (dicts are really handy):
s{pos0:V0,pos1:V1,pos2:V2,pos3:V3,pos4:V4}
And so:
% A generator
state(State) :-
state(State,1,5). % 1,5 are the Min,Max for the accepted values
% Inductive defintion: A state is the initial state or a state that has been "advanced by 1 position"
state(State,Min,_Max) :-
state_initial(Min,State).
state(State,Min,Max) :-
state(S,Min,Max),
state_next(S,State,Min,Max).
% The initial state
state_initial(Min,s{pos0:Min,pos1:Min,pos2:Min,pos3:Min,pos4:Min}).
% StateOut is StateIn "advanced by 1 position" (behaves like counting)
state_next(StateIn,StateOut,Min,Max) :-
pos_advances(pos0,Min,Max,StateIn,StateOut).
% ---
% pos_advances(+Pos,+Min,+Max,+StateIn,?StateOut)
% ---
pos_advances(Pos,Min,Max,StateIn,StateOut) :-
get_dict(Pos,StateIn,Value),
Value == Max, % carry situation: need to advance the next-slowest position
!,
pos_order(Pos,PosSlower), % fails if Pos is the slowest position, which is what we want
put_dict(Pos,StateIn,Min,S1), % Value at Pos is reset to Min
pos_advances(PosSlower,Min,Max,S1,StateOut). % "Ripple down" to the slower position
pos_advances(Pos,_Min,Max,StateIn,StateOut) :-
get_dict(Pos,StateIn,Value),
assertion(Value < Max), % not-carry situation
succ(Value,ValuePlus),
put_dict(Pos,StateIn,ValuePlus,StateOut). % Value at Pos is set; no recursive call
% ---
% pos_order(?FastPos,?SlowPos).
% ---
pos_order(pos0,pos1). % pos0 changes fastest
pos_order(pos1,pos2).
pos_order(pos2,pos3).
pos_order(pos3,pos4). % pos4 changes slowest and has no slower position
Extra simple. Of course one could also enumerate States alternatively using a 5-dimensional enumeration (inductive definition compiled-by-human):
state_alt(State) :-
state_alt(State,1,5).
state_alt(s{pos0:V0,pos1:V1,pos2:V2,pos3:V3,pos4:V4},Min,Max) :-
bagof(X,between(Min,Max,X),Values),
member(V4,Values), % slowest changing
member(V3,Values),
member(V2,Values),
member(V1,Values),
member(V0,Values). % fastest changing when backtracking
So we run this:
?- state(State).
State = s{pos0:1,pos1:1,pos2:1,pos3:1,pos4:1} ;
State = s{pos0:2,pos1:1,pos2:1,pos3:1,pos4:1} ;
State = s{pos0:3,pos1:1,pos2:1,pos3:1,pos4:1} ;
State = s{pos0:4,pos1:1,pos2:1,pos3:1,pos4:1} ;
State = s{pos0:5,pos1:1,pos2:1,pos3:1,pos4:1} ;
State = s{pos0:1,pos1:2,pos2:1,pos3:1,pos4:1} ;
State = s{pos0:2,pos1:2,pos2:1,pos3:1,pos4:1} ;
State = s{pos0:3,pos1:2,pos2:1,pos3:1,pos4:1} ;
State = s{pos0:4,pos1:2,pos2:1,pos3:1,pos4:1} ;
State = s{pos0:5,pos1:2,pos2:1,pos3:1,pos4:1} ;
State = s{pos0:1,pos1:3,pos2:1,pos3:1,pos4:1} ;
State = s{pos0:2,pos1:3,pos2:1,pos3:1,pos4:1} ;
State = s{pos0:3,pos1:3,pos2:1,pos3:1,pos4:1} ;
State = s{pos0:4,pos1:3,pos2:1,pos3:1,pos4:1} ;
State = s{pos0:5,pos1:3,pos2:1,pos3:1,pos4:1} ;
....
Later results of the enumeration demand excessively large amounts of computation because Prolog needs to basically “count from the initial state to the next state to be generated by 1”, so we deploy tabling:
?- table state/3.
true.
But now the ordering of the solutions is really unexpected:
?- state(State).
State = s{pos0:3,pos1:3,pos2:3,pos3:3,pos4:3} ;
State = s{pos0:3,pos1:3,pos2:3,pos3:3,pos4:2} ;
State = s{pos0:3,pos1:3,pos2:3,pos3:3,pos4:1} ;
State = s{pos0:3,pos1:3,pos2:3,pos3:3,pos4:5} ;
State = s{pos0:3,pos1:3,pos2:3,pos3:3,pos4:4} ;
State = s{pos0:3,pos1:3,pos2:3,pos3:2,pos4:3} ;
State = s{pos0:3,pos1:3,pos2:3,pos3:2,pos4:2} ;
State = s{pos0:3,pos1:3,pos2:3,pos3:2,pos4:1} ;
State = s{pos0:3,pos1:3,pos2:3,pos3:2,pos4:5} ;
State = s{pos0:3,pos1:3,pos2:3,pos3:2,pos4:4} ;
State = s{pos0:3,pos1:3,pos2:3,pos3:1,pos4:3} ;
State = s{pos0:3,pos1:3,pos2:3,pos3:1,pos4:2} ;
...
Although the result is still good:
?-
findall(S1,state(S1),States),
sort(States,StatesSorted),
findall(S2,state_alt(S2),StatesAlt),
sort(StatesAlt,StatesAltSorted),
StatesSorted==StatesAltSorted.
succeeds.
Should I expect tabled predicates to strongly influence solution order?