Re: Is Prolog a good language for generating semi-random, constrained solutions?

Kaitain,

To give people here something to pull to pieces, I've written a toy
program that follows your rules. It works, but it's not particularly
elegant and the rules are opaque.

/* legal(ExistingList,Candidate) */
legal(L,b) :- length(L,3), \+memberchk(b,L), !.
legal(L,b) :- length(L,4), subtract(L,[b],L1), length(L1,3), !.
legal(_,a).
legal(_,b).
legal(_,c).
legal(L,d) :- memberchk(a,L), memberchk(b,L), \+((memberchk(c,L),memberchk(e,L))), length(L,N), \+between(5,7,N).
legal(L,e) :- memberchk(c,L).

/* Add a legal element at the head of list L */
add_element(L,[NewElement|L]) :- findall(C,legal(L,C),Candidates), any_of(Candidates,NewElement).
any_of(List,Element) :- length(List,L), Pick is random(L), nth0(Pick,List,Element).

/* Generate a legal list of N elements */
legal_list(N,[]) :- N=<0, !.
legal_list(N,L) :- N1 is N-1, legal_list(N1,L0), add_element(L0,L). 

3 ?- legal_list(8,L).
L = [b, e, c, b, a, a, a, b].

4 ?- legal_list(8,L).
L = [e, b, b, b, a, b, c, a].

5 ?- legal_list(6,L).
L = [e, b, b, a, e, c].

6 ?- legal_list(6,L).
L = [b, b, a, c, b, a].

If you want the rules to be really arbitrary, coding them directly in
Prolog is probably the most powerful way to do it but, as here, the
rules are going to look awkward. For example, it's probably not obvious
at a glance, that the first two clauses of my legal/2 relate to your
rule about there having to be at least two 'b's in the first five elements.

On 14/03/2014 08:30, Kaitain Jones wrote:
> I've been working on something in the last week for which I assumed Prolog
> would be a good tool, but I'm slightly on the fence about its suitability
> now.
>
> Essentially I am trying to use Prolog to generate a single, semi-random
> sequence of entries that needs to meet some loose criteria only. For the
> sake of simplicity, let's assume I want to create a list of atoms. For each
> atom considered as a candidate to be added to the end of a list under
> construction, there are some constraints on which ones are legal. Let's say
> (arbitrarily) that
> 1. I can add an a,b or c as a new entry at any time.
> 2. I can add a new entry d if a and b are already in the list (at least one
> of each).
> 3. I can add an e if there is already at least one c.
> 4. If there is both an entry c and an entry e in the list then I can no
> longer add d.
> These sorts of things (waves hand). Details are not important.
>
> Using these kinds of addition rules, I want to ask the system to generate
> me a (semi-) random sequence of a given length whose only requirements are
> that each entry added must obey all given rules at the time of its addition
> to the sequence. I don't require an enumeration of all legal sequences; I
> just want one each time I execute the program. So
> [a,b,a,b,a,b,c]
> ...is legal (assuming I asked for a list of length 7), as is
> [a,b,c,d,e,a,b]
> ....but
> [a,b,c,d,e,b,d]
> ...is not (the final d violates rule 4).
>
> I might then add some further constraints: I'd like the system to create
> such a sequence, but with some additional macro-level requirements:
>
> * There must be 2 bs in the first five entries. (This would rule out the
> second list above, but the first would be accepted.)
> * There cannot be any ds between entries five and seven inclusive.
> etc.
>
> I have built such a program, but it feels a little inelegant and slightly
> arbitrary, and although Prolog helps make the writing of the
> rules/constraints easy, I feel a bit uncertain that my program is
> particularly idiomatic. I can't enumerate all solution lists and then pick
> one at random, because the state space is too large. Also, I can't see how
> it's easy to build a list with a mixture of bound and unbound members and
> use that to help guide the search efficiently, because I don't always know
> precisely which members should be bound, and the possible combinations of
> such semi-bound lists can themselves be very large in number.
>
> What I'm doing right now is creating the list a few entries at a time (e.g.
> five at a time). For each added member, I consider the list of all new
> entry candidates that would be legal using the universal rules, and pick
> one of these at random to add to the end of the list. When five have been
> added, I apply my extra constraint checks to see if these all pass. If they
> do, I move on to adding the next batch of five. If not, I try again. (Why
> five? That's the arbitrary part. Perhaps I'd be better off applying those
> constraints for every single entry added. But the macro constraints don't
> always apply to individual entries, but rather to the list as a whole, or
> subsequences of it.)
>
> This current approach does work, certainly for small-ish sequences (20-30)
> and a set of perhaps a dozen general rules and some mild macro-level list
> constraints. But I'm not sure that this is the best or most efficient way
> to approach the problem. It is really a hybrid imperative-declarative
> design (the control of the batched search in chunks of five is controlled
> by a C algorithm that calls into Prolog to execute the search itself). I
> would prefer a more idiomatic Prolog approach, but perhaps the language
> simply isn't especially well-suited to this task? (It is first and foremost
> designed to provide a total enumeration of solution state space.)
>
> I would welcome any thoughts/suggestions.
>
> KJ
> -------------- next part --------------
> HTML attachment scrubbed and removed
> _______________________________________________
> SWI-Prolog mailing list
> [email protected]
> https://lists.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog
>