5

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.

  • 2
    Really, it doesn't make much sense to ask for *efficient* randomness. – CapelliC Jan 01 '17 at 12:01
  • @CapelliC With neural networks using [Stochastic gradient descent](https://en.wikipedia.org/wiki/Stochastic_gradient_descent#Iterative_method) it is a standard step to randomly shuffle examples in the training set.. – Guy Coder Jan 01 '17 at 14:28
  • 3
    You should expand on what you mean by "too expensive in my case". Do you have too many solutions? Is `random_member/2` somehow too slow? As far as I know, pure Prolog has no way of "shuffling" the order of solutions to non-deterministic predicates. –  Jan 01 '17 at 15:18
  • 2
    How do you expect the first random element is chosen without ever knowing the total number of elements? Also, show an example where findall is not efficient enough! – false Jan 01 '17 at 19:52
  • @Boris For my real-world case, I have many variables and subgoals, so there are too many solutions to calculate them with findall. –  Jan 01 '17 at 21:18
  • @false I don't think the total number of solutions is needed beforehand, because I don't need a uniform random selection. An alternative way to ask my question might be, "is there a way to shuffle disjunctive clauses after invocation?" –  Jan 01 '17 at 21:21
  • I'd say, look at [`call_nth/2`](http://stackoverflow.com/a/11400256/772868). – false Jan 01 '17 at 21:24
  • @false Does call_nth have to generate all the N solutions? – 2bigpigs Jan 02 '17 at 05:49
  • This feels like a misguided question. The concept of picking out something at random assumes you have a bag of things to pick from. In the case of say integers, it is enough to define a range, but for things that have to be computed first, well, you would have to compute them first, in _some_ order. If you don't care what the order is, why isn't the default order as good as any other order? PS: If you want useful answers you need to provide more context. Picking a random integer between 1 and 4 is a solved problem. –  Jan 02 '17 at 08:34
  • "is there a way to shuffle disjunctive clauses after invocation?" Yes, there is: collect them, then shuffle them. Go ahead and read what "shuffling" means. –  Jan 02 '17 at 08:37
  • @Boris I updated the question with a possibly clearer example. I'm using it for AI-generated content, so always using the default order would produce boring results, and the solution space is too large to collect all solutions and then pick a random one. –  Jan 02 '17 at 09:52
  • @2bigpigs: `call_nth(Goal_0, 10)` has to generate all 9 preceding solutions. That's inevitable. If you want to avoid that you will have to change `Goal_0` somehow. – false Jan 02 '17 at 10:58
  • 1
    If you can enumerate the atomic solutions to each subgoal, you can simplify this to generating pseudorandom integers in a range, then map those to the solutions –  Jan 02 '17 at 11:42

1 Answers1

1

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!

mat
  • 40,498
  • 3
  • 51
  • 78
  • 2
    The combination of random_permutation/2 and member/2 is indeed the way to solve my problem. I see how to adapt my program to that style. Thank you! –  Jan 02 '17 at 13:33
  • I see that `random_member/2` is [already defined](http://www.swi-prolog.org/pldoc/man?predicate=random_member/2). Is it necessary to redefine it as in your solution? If so, how's your `random_member/2` different? – Zhanwen Chen May 19 '19 at 17:30