CLP(FD): all_distinct/1 vs all_different/1?

[Julio Di Egidio]

Hi all,

With CLP(FD), can someone explain what is the exact difference between all_distinct/1 and all_different/1?

The docs for all_different/1 just state "Like all_distinct/1, but with weaker propagation", which is not very

informative: at the moment, I am choosing which one to use by timing the call to the predicate and checking

the number of inferences, but of course this is not ideal...

Thanks in advance for any insights,

Julio

[Jan Burse]

On the other hand the comment for all_distinct/1 gives an example how
it is stronger. "For example, all_distinct/1 can detect that not all variables
can assume distinct values given the following domains".

So basically all_distinct/1 takes the domains into account whereas
all_different/1 doesn't. Here you see the difference:

Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 7.3.24)
Copyright (c) 1990-2016 University of Amsterdam, VU Amsterdam

?- maplist(in, Vs,
           [1\/3..4, 1..2\/4, 1..2\/4, 1..3, 1..3, 1..6]),
   all_distinct(Vs).
false.

?- maplist(in, Vs,
           [1\/3..4, 1..2\/4, 1..2\/4, 1..3, 1..3, 1..6]),
   all_different(Vs).
Vs = [_G615, _G618, _G621, _G624, _G627, _G630],
_G615 in 1\/3..4,
all_different([_G615, _G618, _G621, _G624, _G627, _G630]),
_G618 in 1..2\/4,
_G621 in 1..2\/4,
_G624 in 1..3,
_G627 in 1..3,
_G630 in 1..6.

So all_distinct/1 can already fail without labeling all variables, thus reducing
the search space early on. But after labeling you should still get the same
results for both global constraints.

Bye

[Jan Burse]

As often Neng-Fa Zhou is quite informative, he writes:

      In terms of the propagation ability, the second implementation
      is the same as the first one. In some systems, consistency checks
      are done to detect failure as early as possible. It is very easy to
      introduce consistency checks into the implementation. To do so,
      we only need to define outof(X,Left,Right) as follows: [...]

      where consistency_check(X,Left,Right) does the consistency check.
      There are many possible algorithms. The one implemented in B-Prolog
      is as follows: Let $n$ be the size of the domain of X, and $m$ be the
      number of variables in Left and Right whose domains are subsets
      of that of X. [...]

      http://www.sci.brooklyn.cuny.edu/~zhou/bprolog/manual/node65.html

The above B-Prolog variant of all_distinct/1 seems to apply a Pigeonhole
principle to early on detect failure of the satisifiability of the difference among
the variables based on the actual domain information.

      https://en.wikipedia.org/wiki/Pigeonhole_principle

[Julio Di Egidio]

On Sunday, August 7, 2016 at 1:19:52 PM UTC+2, Jan Burse wrote:

> So all_distinct/1 can already fail without labeling all variables

I am still in doubt, as the spec for all_different/1 says "weaker propagation", it
does not say "no propagation at all until labelling time". So, is that it really?

There is also the fact that with all_distict/1 I have had predicates not terminate
(sorry, do not have examples handy), while they would terminate with
all_different/1: but, if the only difference between the two predicates is that
all_distinct/1 immediately propagates domain constraints between the variables,
no such thing should occur... no?

In any case, just examples won't cut it, hence I was asking for a specification,
for how informal. Indeed, something like Neng-Fa Zhou's for B-Prolog (thanks
for that reference), possibly even simpler, i.e. less in depth than that.

Julio

[Jan Burse]

In SWI-Prolog, all_distinct/1 is extremly weak, for example you get:

     ?- X#=Y, Y#=Z, all_different([X,Y,Z]).
     X = Y, Y = Z,
     all_different([Z, Z, Z]).

So its even weaker than dif/2:

     ?- X#=Y, Y#=Z, dif(X,Y), dif(Y,Z), dif(X,Z).
     false.

On the other hand all_distinct/1 is even stronger than dif/2.

Bye

[Jan Burse]

But all_different/1 is not completely propagation free. It is not a
wait until labeling only implementation. For example here you
see some domain ranges for Z created:

?- all_different([X,Y,Z]), X#=Y, Y#=Z.

X = Y, Y = Z,
all_different([Z, Z, Z]).

?- all_different([X,Y,Z]), X#=1, Y#=Z.
X = 1,
Y = Z,
Z in inf..0\/2..sup,
all_different([1, Z, Z]).

?- all_different([X,Y,Z]), X#=1, Y#=2.
X = 1,
Y = 2,
Z in inf..0\/3..sup,
all_different([1, 2, Z]).

[Jan Burse]

But whats for sure, when Neng-Fa Zhou writes There are many
possible algorithms, then this is true. For example SICStus Prolog
mentions [Regin 94] and [Lopez-Oritz 03]:

https://sicstus.sics.se/sicstus/docs/4.3.2/html/sicstus/Arithmetic_002dLogical-Constraints.html

Alle these variants vary in the degree they propagate and/or
in the degree they can early on fail. And even if some Prolog
system takes one of the literature references as a template to
implement a certain constraint,

Different Prolog system implementations might nevertheless
turn out differently.

Bye


Am Sonntag, 7. August 2016 22:15:02 UTC+2 schrieb Jan Burse:

[Julio Di Egidio]

On Sunday, August 7, 2016 at 10:20:10 PM UTC+2, Jan Burse wrote:

> But whats for sure, when Neng-Fa Zhou writes There are many
> possible algorithms, then this is true.

You miss the point: I am not asking about "any implementation", I'm asking the spec for SWI's.

> For example SICStus Prolog mentions [Regin 94] and [Lopez-Oritz 03]:

> https://sicstus.sics.se/sicstus/docs/4.3.2/html/sicstus/Arithmetic_002dLogical-Constraints.html

It not only provide references, there is an informal explanation (exactly of the kind I was after), too.

OTOH, in SWI there is neither, only examples along with the usual misguided indoctrination.

Indeed, all I can find is https://github.com/triska/clpfd, then

https://github.com/triska/clpfd/blob/master/n_factorial.pl on the specific question

I was asking here: neither of which helps if not to remind that a "superb implementation"

is rather in SICStus...

Anyway, for obvious reasons I am not expecting any more answers, so I'll rather

take the chance to add some more criticism, still on the docs and how the whole thing is

presented, not the library per se: while the specification is seriously lacking, the docs

stay totally biased towards a misguided idea of purity and declarativeness, but not even

the examples, the only thing we are really given, are faithful.  Try the following, and time it...

% (SWI-Prolog)

:- use_module(library(clpfd)).

factorial_c(0, 1).
factorial_c(N, F) :-
    N #> 0,
    N0 #= N - 1,
    F #= N * F0,
    factorial_c(N0, F0).

factorial_a(N, F) :-
    between(0, inf, N),
    factorial_a__do(N, 1, FT),
    (   var(F)
    ->  F = FT
    ;   FT >= F
    ->  !,
        FT =:= F
    ).

factorial_a__do(0, F, F) :- !.
factorial_a__do(N, A, F) :-
    A1 is A * N,
    N0 is N - 1,
    factorial_a__do(N0, A1, F).

HTH,

Julio

[Julio Di Egidio]

On Monday, August 8, 2016 at 4:25:25 PM UTC+2, Julio Di Egidio wrote:

On Sunday, August 7, 2016 at 10:20:10 PM UTC+2, Jan Burse wrote:

> But whats for sure, when Neng-Fa Zhou writes There are many
> possible algorithms, then this is true.

You miss the point: I am not asking about "any implementation", I'm asking the spec for SWI's.

> For example SICStus Prolog mentions [Regin 94] and [Lopez-Oritz 03]:

> https://sicstus.sics.se/sicstus/docs/4.3.2/html/sicstus/Arithmetic_002dLogical-Constraints.html

It not only provide references, there is an informal explanation (exactly of the kind I was after), too.

OTOH, in SWI there is neither, only examples along with the usual misguided indoctrination.

Indeed, all I can find is https://github.com/triska/clpfd, then

https://github.com/triska/clpfd/blob/master/n_factorial.pl on the specific question

I was asking here: neither of which helps if not to remind that a "superb implementation"

is rather in SICStus...

Ah, and this, which is an answer by Markus Triska to my same question, and he simply

suggests the trial and error I am already doing:

https://github.com/JCumin/Brachylog/issues/25

Julio

[Jan Burse]

1) Start SWI-Prolog

2) Type:
?- use_module(library(clpfd)).

3) Type:
?- edit(all_distinct/1).

4) Type:
?- edit(all_different/1).

Compare the two windows.

Here is my feature request for SWI-Prolog:
- SWI-Prolog has coloring of Prolog texts in the window that
   is shown after edit/1.
- If I hoover over a predicate name, I can use the menu item
   browse | find definition.
  (for example I click inside the predicate name of the goal
   make_propagator( ) , it then takes me to the definition of
   predicate make_propagator/2 , but I have an intervening
   dialog box )
- What about the same effect when I Ctrl-Click on a predicate name?