View source with raw comments or as raw
    1/*  Part of SWI-Prolog
    2
    3    Author:        R.A. O'Keefe, V.S. Costa, L. Damas, Jan Wielemaker
    4    E-mail:        J.Wielemaker@vu.nl
    5    WWW:           http://www.swi-prolog.org
    6    Copyright (c)  2011-2016, Universidade do Porto, University of Amsterdam,
    7                              VU University Amsterdam.
    8    All rights reserved.
    9
   10    Redistribution and use in source and binary forms, with or without
   11    modification, are permitted provided that the following conditions
   12    are met:
   13
   14    1. Redistributions of source code must retain the above copyright
   15       notice, this list of conditions and the following disclaimer.
   16
   17    2. Redistributions in binary form must reproduce the above copyright
   18       notice, this list of conditions and the following disclaimer in
   19       the documentation and/or other materials provided with the
   20       distribution.
   21
   22    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
   23    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
   24    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
   25    FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
   26    COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
   27    INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
   28    BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
   29    LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
   30    CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   31    LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
   32    ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
   33    POSSIBILITY OF SUCH DAMAGE.
   34*/
   35
   36:- module(random,
   37          [ random/1,                   % -Float (0,1)
   38            random_between/3,           % +Low, +High, -Random
   39
   40            getrand/1,                  % -State
   41            setrand/1,                  % +State
   42
   43            maybe/0,
   44            maybe/1,                    % +P
   45            maybe/2,                    % +K, +N
   46
   47            random_perm2/4,             % A,B, X,Y
   48
   49            random_member/2,            % -Element, +List
   50            random_select/3,            % ?Element, +List, -Rest
   51
   52            randseq/3,                  % +Size, +Max, -Set
   53            randset/3,                  % +Size, +Max, -List
   54            random_permutation/2,       % ?List, ?Permutation
   55
   56                                        % deprecated interface
   57            random/3                    % +Low, +High, -Random
   58          ]).   59:- use_module(library(pairs)).   60:- use_module(library(error)).   61:- use_module(library(lists)).

Random numbers

This library is derived from the DEC10 library random. Later, the core random generator was moved to C. The current version uses the SWI-Prolog arithmetic functions to realise this library. These functions are based on the GMP library.

author
- R.A. O'Keefe, V.S. Costa, L. Damas, Jan Wielemaker
See also
- Built-in function random/1: A is random(10) */
   74check_gmp :-
   75    current_arithmetic_function(random_float),
   76    !.
   77check_gmp :-
   78    print_message(warning, random(no_gmp)).
   79
   80:- initialization check_gmp.   81
   82
   83                 /*******************************
   84                 *         PRIMITIVES           *
   85                 *******************************/
 random(-R:float) is det
Binds R to a new random float in the open interval (0.0,1.0).
See also
- setrand/1, getrand/1 may be used to fetch/set the state.
- In SWI-Prolog, random/1 is implemented by the function random_float/0.
   95random(R) :-
   96    R is random_float.
 random_between(+L:int, +U:int, -R:int) is semidet
Binds R to a random integer in [L,U] (i.e., including both L and U). Fails silently if U<L.
  103random_between(L, U, R) :-
  104    integer(L), integer(U),
  105    !,
  106    U >= L,
  107    R is L+random((U+1)-L).
  108random_between(L, U, _) :-
  109    must_be(integer, L),
  110    must_be(integer, U).
 random(+L:int, +U:int, -R:int) is det
random(+L:float, +U:float, -R:float) is det
Generate a random integer or float in a range. If L and U are both integers, R is a random integer in the half open interval [L,U). If L and U are both floats, R is a float in the open interval (L,U).
deprecated
- Please use random/1 for generating a random float and random_between/3 for generating a random integer. Note that random_between/3 includes the upper bound, while this predicate excludes it.
  126random(L, U, R) :-
  127    integer(L), integer(U),
  128    !,
  129    R is L+random(U-L).
  130random(L, U, R) :-
  131    number(L), number(U),
  132    !,
  133    R is L+((U-L)*random_float).
  134random(L, U, _) :-
  135    must_be(number, L),
  136    must_be(number, U).
  137
  138
  139                 /*******************************
  140                 *             STATE            *
  141                 *******************************/
 setrand(+State) is det
 getrand(-State) is det
Query/set the state of the random generator. This is intended for restarting the generator at a known state only. The predicate setrand/1 accepts an opaque term returned by getrand/1. This term may be asserted, written and read. The application may not make other assumptions about this term.

For compatibility reasons with older versions of this library, setrand/1 also accepts a term rand(A,B,C), where A, B and C are integers in the range 1..30,000. This argument is used to seed the random generator. Deprecated.

Errors
- existence_error(random_state, _) is raised if the underlying infrastructure cannot fetch the random state. This is currently the case if SWI-Prolog is not compiled with the GMP library.
See also
- set_random/1 and random_property/1 provide the SWI-Prolog native implementation.
  164setrand(rand(A,B,C)) :-
  165    !,
  166    Seed is A<<30+B<<15+C,
  167    set_random(seed(Seed)).
  168setrand(State) :-
  169    set_random(state(State)).
  170
  171:- if(current_predicate(random_property/1)).  172getrand(State) :-
  173    random_property(state(State)).
  174:- else.  175getrand(State) :-
  176    existence_error(random_state, State).
  177:- endif.  178
  179
  180                 /*******************************
  181                 *            MAYBE             *
  182                 *******************************/
 maybe is semidet
Succeed/fail with equal probability (variant of maybe/1).
  188maybe :-
  189    random(2) =:= 0.
 maybe(+P) is semidet
Succeed with probability P, fail with probability 1-P
  195maybe(P) :-
  196    must_be(between(0.0,1.0), P),
  197    random_float < P.
 maybe(+K, +N) is semidet
Succeed with probability K/N (variant of maybe/1)
  203maybe(K, N) :-
  204    integer(K), integer(N),
  205    between(0, N, K),
  206    !,
  207    random(N) < K.
  208maybe(K, N) :-
  209    must_be(nonneg, K),
  210    must_be(nonneg, N),
  211    domain_error(not_less_than_zero,N-K).
  212
  213
  214                 /*******************************
  215                 *          PERMUTATION         *
  216                 *******************************/
 random_perm2(?A, ?B, ?X, ?Y) is semidet
Does X=A,Y=B or X=B,Y=A with equal probability.
  222random_perm2(A,B, X,Y) :-
  223    (   maybe
  224    ->  X = A, Y = B
  225    ;   X = B, Y = A
  226    ).
  227
  228
  229                 /*******************************
  230                 *    SET AND LIST OPERATIONS   *
  231                 *******************************/
 random_member(-X, +List:list) is semidet
X is a random member of List. Equivalent to random_between(1, |List|), followed by nth1/3. Fails of List is the empty list.
Compatibility
- Quintus and SICStus libraries.
  240random_member(X, List) :-
  241    must_be(list, List),
  242    length(List, Len),
  243    Len > 0,
  244    N is random(Len),
  245    nth0(N, List, X).
 random_select(-X, +List, -Rest) is semidet
random_select(+X, -List, +Rest) is det
Randomly select or insert an element. Either List or Rest must be a list. Fails if List is the empty list.
Compatibility
- Quintus and SICStus libraries.
  255random_select(X, List, Rest) :-
  256    (   '$skip_list'(Len, List, Tail),
  257        Tail == []
  258    ->  true
  259    ;   '$skip_list'(RLen, Rest, Tail),
  260        Tail == []
  261    ->  Len is RLen+1
  262    ),
  263    !,
  264    Len > 0,
  265    N is random(Len),
  266    nth0(N, List, X, Rest).
  267random_select(_, List, Rest) :-
  268    partial_list(List), partial_list(Rest),
  269    instantiation_error(List+Rest).
  270random_select(_, List, Rest) :-
  271    must_be(list, List),
  272    must_be(list, Rest).
 randset(+K:int, +N:int, -S:list(int)) is det
S is a sorted list of K unique random integers in the range 1..N. The implementation uses different techniques depending on the ratio K/N. For small K/N it generates a set of K random numbers, removes the duplicates and adds more numbers until |S| is K. For a large K/N it enumerates 1..N and decides randomly to include the number or not. For example:
?- randset(5, 5, S).
S = [1, 2, 3, 4, 5].          (always)
?- randset(5, 20, S).
S = [2, 7, 10, 19, 20].
See also
- randseq/3.
  292randset(K, N, S) :-
  293    must_be(nonneg, K),
  294    K =< N,
  295    (   K < N//7
  296    ->  randsetn(K, N, [], S)
  297    ;   randset(K, N, [], S)
  298    ).
  299
  300randset(0, _, S, S) :- !.
  301randset(K, N, Si, So) :-
  302    random(N) < K,
  303    !,
  304    J is K-1,
  305    M is N-1,
  306    randset(J, M, [N|Si], So).
  307randset(K, N, Si, So) :-
  308    M is N-1,
  309    randset(K, M, Si, So).
  310
  311randsetn(K, N, Sofar, S) :-
  312    length(Sofar, Len),
  313    (   Len =:= K
  314    ->  S = Sofar
  315    ;   Needed is K-Len,
  316        length(New, Needed),
  317        maplist(srand(N), New),
  318        (   Sofar == []
  319        ->  sort(New, Sorted)
  320        ;   append(New, Sofar, Sofar2),
  321            sort(Sofar2, Sorted)
  322        ),
  323        randsetn(K, N, Sorted, S)
  324    ).
  325
  326srand(N, E) :-
  327    E is random(N)+1.
 randseq(+K:int, +N:int, -List:list(int)) is det
S is a list of K unique random integers in the range 1..N. The order is random. Defined as
randseq(K, N, List) :-
      randset(K, N, Set),
      random_permutation(Set, List).
See also
- randset/3.
  342randseq(K, N, Seq) :-
  343    randset(K, N, Set),
  344    random_permutation_(Set, Seq).
 random_permutation(+List, -Permutation) is det
random_permutation(-List, +Permutation) is det
Permutation is a random permutation of List. This is intended to process the elements of List in random order. The predicate is symmetric.
Errors
- instantiation_error, type_error(list, _).
  355random_permutation(List1, List2) :-
  356    is_list(List1),
  357    !,
  358    random_permutation_(List1, List2).
  359random_permutation(List1, List2) :-
  360    is_list(List2),
  361    !,
  362    random_permutation_(List2, List1).
  363random_permutation(List1, List2) :-
  364    partial_list(List1), partial_list(List2),
  365    !,
  366    instantiation_error(List1+List2).
  367random_permutation(List1, List2) :-
  368    must_be(list, List1),
  369    must_be(list, List2).
  370
  371random_permutation_(List, RandomPermutation) :-
  372    key_random(List, Keyed),
  373    keysort(Keyed, Sorted),
  374    pairs_values(Sorted, RandomPermutation).
  375
  376key_random([], []).
  377key_random([H|T0], [K-H|T]) :-
  378    random(K),
  379    key_random(T0, T).
 partial_list(@Term) is semidet
True if Term is a partial list.
  385partial_list(List) :-
  386    '$skip_list'(_, List, Tail),
  387    var(Tail).
  388
  389:- multifile
  390    prolog:message//1.  391
  392prolog:message(random(no_gmp)) -->
  393    [ 'This version of SWI-Prolog is not compiled with GMP support.'-[], nl,
  394      'Floating point random operations are not supported.'-[]
  395    ]