CODEWITHSUNDEEP
prolog
vincent
vincent

Reputation: 101

Pick 2 random values from a set of constants

In Prolog, how do I randomly pick 2 values from a set of 52 cards? i.e. Player1(X,Y), X will be any card out of 52 and Y another and they have to be different. Player2 will get the same treatment and his cards must differ from the ones already picked. Thanks.

Upvotes: 0

Views: 209

Answers (3)

jschimpf
jschimpf

Reputation: 5034

If you want to draw random cards repeatedly, it is probably best to shuffle the whole list in one go, and then simply pick cards from the front. Some Prologs (e.g. ECLiPSe) have a library predicate for this, so you could just call

lists:shuffle(Cards, [Card1,Card2|Rest]).

If you want to write the shuffling yourself, here is a neat trick:

shuffle(Xs, Rs) :-
    add_random_keys(Xs, KXs),  % add random key to each list element
    keysort(KXs, KRs),         % sort by keys, perturbing original order
    strip_keys(KRs, Rs).       % remove the keys again

add_random_keys([], []).
add_random_keys([X|Xs], [K-X|KXs]) :-
    random(K),
    add_random_keys(Xs, KXs).

strip_keys([], []).
strip_keys([_K-X|KXs], [X|Xs]) :-
    strip_keys(KXs, Xs).

Upvotes: 1

Sergii Dymchenko
Sergii Dymchenko

Reputation: 7229

Basically, the task is to sample 4 different elements from set [1..52].

In Python, for example, there is a standard function for this, and the code would be 

random.sample(range(1, 52 + 1), 4)

I've looked how Python implements random.sample(range(1..N + 1), K) - it's basically just K steps of generating random numbers [1..N], and on every step just keep trying generate random numbers while currently generated number already selected in a previous step. It looks inefficient, but it's probably needed to archive uniformity of the distribution.

Let's create a similar (but simplified) sample predicate for Prolog.

sample(N, K, Sample) :-
    sample(N, K, [], Sample).

sample(_, 0, _, []).
sample(N, K, Selected, [X | Rest]) :-
    K > 0,
    new_random_index(N, Selected, X),
    NewSelected = [X | Selected],
    NewK is K - 1,
    sample(N, NewK, NewSelected, Rest).

new_random_index(N, Selected, X) :-
    ( 
        % Can be implementation-specific. Works in B-Prolog and ECLiPSe CLP.
        X is (random mod N) + 1, 
        \+ membchk(X, Selected) 
    ; 
        new_random_index(N, Selected, X)
    ).

Couple of test runs:

| ?- sample(52, 4, Sample).
sample(52, 4, Sample).
Sample = [40,23,38,44] ?
yes
| ?- sample(52, 4, Sample).
sample(52, 4, Sample).
Sample = [2,28,39,17] ?
yes

Efficiency of the program can be greatly improved if membchk test changed to a predicate that test membership using sets, not lists. But this is very implementation-specific.

Upvotes: 1

CapelliC
CapelliC

Reputation: 60034

In SWI-Prolog I would do a pick_card/3

pick_card(Cards, Card, Rest) :-
  length(Cards, N), random_between(1, N, R), nth1(R, Cards, Card, Rest).

and apply it 2 times

pick_two_cards(Cards, C1,C2, Rest) :-
  pick_card(Cards, C1, R1),
  pick_card(R1, C2, Rest).

Upvotes: 1

Related Questions