# Tabling changes order of solutions - Expected?

**URL:** <https://swi-prolog.discourse.group/t/tabling-changes-order-of-solutions-expected/3602>\
**Category:** Help!\
**Tags:** tabling\
**Created:** [February 13, 2021, 11:34am UTC](https://swi-prolog.discourse.group/t/tabling-changes-order-of-solutions-expected/3602 "2021-02-13T11:34:06Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![dtonhofer](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/dtonhofer/32/902_2.png) [@dtonhofer](https://swi-prolog.discourse.group/u/dtonhofer)\
**Post date:** [February 13, 2021, 11:34am UTC](https://swi-prolog.discourse.group/t/tabling-changes-order-of-solutions-expected/3602/1 "2021-02-13T11:34:06Z")

</div>

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:

```prolog
% 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):

```prolog
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:

```prolog
?- 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:

```prolog
?- table state/3.
true.

```

But now the ordering of the solutions is really unexpected:

```prolog
?- 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:

```prolog
?- 
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?

---

<div class="post-metadata">

**Author:** ![Boris](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/boris/32/7486_2.png) [@Boris](https://swi-prolog.discourse.group/u/Boris)\
**Post date:** [February 13, 2021, 12:40pm UTC](https://swi-prolog.discourse.group/t/tabling-changes-order-of-solutions-expected/3602/2 "2021-02-13T12:40:03Z")

</div>

See [this thread](https://swi-prolog.discourse.group/t/are-there-table-ordering-guarantees/3458).

---

<div class="post-metadata">

**Author:** ![dtonhofer](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/dtonhofer/32/902_2.png) [@dtonhofer](https://swi-prolog.discourse.group/u/dtonhofer)\
**Post date:** [February 13, 2021, 12:54pm UTC](https://swi-prolog.discourse.group/t/tabling-changes-order-of-solutions-expected/3602/3 "2021-02-13T12:54:25Z")

</div>

Thanks Boris. sorting it is then.