CODEWITHSUNDEEP
prolog
user3435636
user3435636

Reputation:

In Prolog, can solutions be chosen in random order?

If I have the following:

a(X) :- X = 1; X = 2; X = 3; X = 4.

I can produce solutions in deterministic order:

?- a(X).
X = 1 ;
X = 2 ;
X = 3 ;
X = 4.

Is there any method of asking the system to produce solutions in non-deterministic, random order? For example:

?- a(X).
X = 4 ;
X = 1 ;
X = 3 ;
X = 2.

I'm aware that I can find all solutions then select one at random (findall(X, a(X), Y), random_member(Z, Y).) but this is too expensive in my case.

Possibly clearer example:

p(X,Y,Z) :-
  (X = a; X = b; X = c; X = d),   % (D1)
  (Y = a; Y = b; Y = c),          % (D2)
  (Z = a; Z = b; Z = c; Z = d).   % (D3)

When deterministic, generating the solution X = d, Y = c, Z = d using ?- p(X,Y,Z). will always go through the 47 previous solutions (4 * 3 * 4 = 48). However, if disjunctions are selected in non-deterministic order, the system might choose X = d at D1, Y = c at D2, Z = d at D3, generating it as the first solution.

This is being used for constrained AI-generated content, so there are many more variables in the real-world use-case.

Upvotes: 5

Views: 1007

Answers (1)

mat
mat

Reputation: 40768

From what you say in the comments, my impression is that a more important question for your use case is:

Can solutions be created in random order?

(This is because you say that you cannot create them all, and then choose a random one.)

To create them in a different order, Boris has hinted at a good way: Simply reorder the disjunctions!

For example, in the case you show:

p(X, Y, Z) :-
  (X = a; X = b; X = c; X = d),   % (D1)
  (Y = a; Y = b; Y = c),          % (D2)
  (Z = a; Z = b; Z = c; Z = d).   % (D3)

You could (automatically) create such declaratively equivalent versions of this snippet by exchanging the order if the disjunctions, such as: (X = c ; X = b ; etc.), and each of these snippets may yield the solutions in a different order.

However, it may be easier to first rewrite this to the equivalent version:

p(X, Y, Z) :-
    member(X, [a,b,c,d]),
    member(Y, [a,b,c]),
    member(Z, [a,b,c,d]).

This way, it is easier to shuffle the lists and use the randomized lists to generate solutions.

For example, you can change this to:

p(X, Y, Z) :-
    random_member(X, [a,b,c,d]),
    random_member(Y, [a,b,c]),
    random_member(Z, [a,b,c,d]).

random_member(X, Ls0) :-
    random_permutation(Ls0, Ls),
    member(X, Ls).

Now, you will get answers like:

?- p(X, Y, Z).
X = d,
Y = Z, Z = b ;
X = Z, Z = d,
Y = b ;
X = d,
Y = b,
Z = c ;
etc.

Note that this way to incorporate randomness to your code is impure: There is now implicit global state in your program, and you can no longer easily reproduce results that you need when describing test cases etc. for such programs. A solution preserving has to make this state explicit, for example by carrying the random seed as one of the arguments, so that each run is completely reproducible.

Note that reordering conjunctions and/or goals like this works only for the pure and monotonic subset of Prolog, so make sure that you use declarative features like constraints to safely exchange goals, and to increase the generality of your code!

Upvotes: 1

Related Questions