Inverse mechanism (find random X for which foo (X) is true)

Question

I know that languages ​​like Prolog let you write things like:

  mortal (X): - man (X).  % All men are mortal
 man (socrates).  % Socrates is a man

 ? - mortal (socrates).  % Is Socrates mortal?
 yes 

What I want is something like this, but back. Suppose I have this:

  mortal (X): - man (X).
 man (socrates).
 man (plato).
 man (aristotle). 

Then I ask him to give me a random X for which mortal (X) is true (thus, he should give me one of "socrates", "plato" or "aristotle" according to some random seed).

My questions:

• Does this kind of inverse output have a name?
• Are there any languages ​​or libraries that support it?

EDIT

As pointed out below, you can just ask the mortal (X), and he will return all X from which you can simply select a random one from the list. What if, however, this list is very large, possibly in billions? Obviously, in this case, he would not do to generate every possible result before choosing it.

To understand how this would be a practical problem, imagine a simple grammar that generated a random sentence of the form "adjective1 noun1 adverb transitive_verb adjective2 noun2". If lists of adjectives, nouns, verbs, etc. Very large, you can see how a combinatorial explosion is a problem. If there were 1000 words in each list, you would have 1000 ^ 6 possible sentences.

Answer 1

Instead of a deep Prolog search, a randomized forward search strategy can be easily implemented. All that is required is to randomize the program flow at the selection points so that every time a disjunction is reached, a random pole in the search tree (= prolog) is selected instead of the first one.

Although, note that this approach does not guarantee that all solutions will be equally likely. To guarantee this, you must know in advance how many decisions will be generated by each pole in order to weight randomization accordingly.

Answer 2

I never used Prolog or something like that, but judging by what Wikipedia says on this question , asking

?- mortal(X). 

should display all for which mortal true. After that, just select one of the results.

So, to answer your questions,

• I would go with a "query with a variable in it"
• From what I can say, Prolog itself should support it pretty well.

Answer 3

I do not think that you can calculate the nth solution directly, but you can calculate the n first solutions (n ​​randomly selected) and select the last. Of course, that would be problematic if n = 10 ^ (big_number) ...

You can also do something like

 mortal(ID,X) :- man(ID,X). man(X):- random(1,4,ID), man(ID,X). man(1,socrates). man(2,plato). man(3,aristotle). 

but the problem is that if not every person were mortal, for example, if only 1 in 1,000,000 was mortal, you would have to look a lot. It would be like looking for solutions to an equation using random numbers until you find them. You could develop some kind of heuristic in order to find a solution close to the number, but which can affect (negatively) randomness.

I suspect that there is no way to do this more efficiently: you need to either calculate a set of solutions or select one of the elements of a superset of all solutions until you find one solution. But don't take my word for xd