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)). 62 63/** <module> Random numbers 64 65This library is derived from the DEC10 library random. Later, the core 66random generator was moved to C. The current version uses the SWI-Prolog 67arithmetic functions to realise this library. These functions are based 68on the GMP library. 69 70@author R.A. O'Keefe, V.S. Costa, L. Damas, Jan Wielemaker 71@see Built-in function random/1: A is random(10) 72*/ 73 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 *******************************/ 86 87%! random(-R:float) is det. 88% 89% Binds R to a new random float in the _open_ interval (0.0,1.0). 90% 91% @see setrand/1, getrand/1 may be used to fetch/set the state. 92% @see In SWI-Prolog, random/1 is implemented by the function 93% random_float/0. 94 95random(R) :- 96 R is random_float. 97 98%! random_between(+L:int, +U:int, -R:int) is semidet. 99% 100% Binds R to a random integer in [L,U] (i.e., including both L and 101% U). Fails silently if U<L. 102 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). 111 112 113%! random(+L:int, +U:int, -R:int) is det. 114%! random(+L:float, +U:float, -R:float) is det. 115% 116% Generate a random integer or float in a range. If L and U are 117% both integers, R is a random integer in the half open interval 118% [L,U). If L and U are both floats, R is a float in the open 119% interval (L,U). 120% 121% @deprecated Please use random/1 for generating a random float 122% and random_between/3 for generating a random integer. Note that 123% the random_between/3 includes the upper bound, while this 124% predicate excludes the upper bound. 125 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 *******************************/ 142 143%! setrand(+State) is det. 144%! getrand(-State) is det. 145% 146% Query/set the state of the random generator. This is intended 147% for restarting the generator at a known state only. The 148% predicate setrand/1 accepts an opaque term returned by 149% getrand/1. This term may be asserted, written and read. The 150% application may not make other assumptions about this term. 151% 152% For compatibility reasons with older versions of this library, 153% setrand/1 also accepts a term rand(A,B,C), where A, B and C are 154% integers in the range 1..30,000. This argument is used to seed 155% the random generator. Deprecated. 156% 157% @see set_random/1 and random_property/1 provide the SWI-Prolog 158% native implementation. 159% @error existence_error(random_state, _) is raised if the 160% underlying infrastructure cannot fetch the random state. 161% This is currently the case if SWI-Prolog is not compiled 162% with the GMP library. 163 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 *******************************/ 183 184%! maybe is semidet. 185% 186% Succeed/fail with equal probability (variant of maybe/1). 187 188maybe :- 189 random(2) =:= 0. 190 191%! maybe(+P) is semidet. 192% 193% Succeed with probability P, fail with probability 1-P 194 195maybe(P) :- 196 must_be(between(0.0,1.0), P), 197 random_float < P. 198 199%! maybe(+K, +N) is semidet. 200% 201% Succeed with probability K/N (variant of maybe/1) 202 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 *******************************/ 217 218%! random_perm2(?A, ?B, ?X, ?Y) is semidet. 219% 220% Does X=A,Y=B or X=B,Y=A with equal probability. 221 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 *******************************/ 232 233%! random_member(-X, +List:list) is semidet. 234% 235% X is a random member of List. Equivalent to random_between(1, 236% |List|), followed by nth1/3. Fails of List is the empty list. 237% 238% @compat Quintus and SICStus libraries. 239 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). 246 247%! random_select(-X, +List, -Rest) is semidet. 248%! random_select(+X, -List, +Rest) is det. 249% 250% Randomly select or insert an element. Either List or Rest must 251% be a list. Fails if List is the empty list. 252% 253% @compat Quintus and SICStus libraries. 254 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). 273 274%! randset(+K:int, +N:int, -S:list(int)) is det. 275% 276% S is a sorted list of K unique random integers in the range 277% 1..N. Implemented by enumerating 1..N and deciding whether or 278% not the number should be part of the set. For example: 279% 280% == 281% ?- randset(5, 5, S). 282% S = [1, 2, 3, 4, 5]. (always) 283% ?- randset(5, 20, S). 284% S = [2, 7, 10, 19, 20]. 285% == 286% 287% @see randseq/3. 288% @bug Slow if N is large and K is small. 289 290randset(K, N, S) :- 291 must_be(nonneg, K), 292 K =< N, 293 randset(K, N, [], S). 294 295randset(0, _, S, S) :- !. 296randset(K, N, Si, So) :- 297 random(N) < K, 298 !, 299 J is K-1, 300 M is N-1, 301 randset(J, M, [N|Si], So). 302randset(K, N, Si, So) :- 303 M is N-1, 304 randset(K, M, Si, So). 305 306 307%! randseq(+K:int, +N:int, -List:list(int)) is det. 308% 309% S is a list of K unique random integers in the range 1..N. The 310% order is random. Works as if defined by the following code. 311% 312% == 313% randseq(K, N, List) :- 314% randset(K, N, Set), 315% random_permutation(Set, List). 316% == 317% 318% @see randset/3. 319 320 321randseq(K, N, S) :- 322 randseq(K, N, L, []), 323 keysort(L, R), 324 pairs_values(R, S). 325 326randseq(0, _, S, S) :- !. 327randseq(K, N, [Y-N|Si], So) :- 328 random(N) < K, 329 !, 330 random(Y), 331 J is K-1, 332 M is N-1, 333 randseq(J, M, Si, So). 334randseq(K, N, Si, So) :- 335 M is N-1, 336 randseq(K, M, Si, So). 337 338%! random_permutation(+List, -Permutation) is det. 339%! random_permutation(-List, +Permutation) is det. 340% 341% Permutation is a random permutation of List. This is intended to 342% process the elements of List in random order. The predicate is 343% symmetric. 344% 345% @error instantiation_error, type_error(list, _). 346 347random_permutation(List1, List2) :- 348 is_list(List1), 349 !, 350 random_permutation_(List1, List2). 351random_permutation(List1, List2) :- 352 is_list(List2), 353 !, 354 random_permutation_(List2, List1). 355random_permutation(List1, List2) :- 356 partial_list(List1), partial_list(List2), 357 !, 358 instantiation_error(List1+List2). 359random_permutation(List1, List2) :- 360 must_be(list, List1), 361 must_be(list, List2). 362 363random_permutation_(List, RandomPermutation) :- 364 key_random(List, Keyed), 365 keysort(Keyed, Sorted), 366 pairs_values(Sorted, RandomPermutation). 367 368key_random([], []). 369key_random([H|T0], [K-H|T]) :- 370 random(K), 371 key_random(T0, T). 372 373%! partial_list(@Term) is semidet. 374% 375% True if Term is a partial list. 376 377partial_list(List) :- 378 '$skip_list'(_, List, Tail), 379 var(Tail). 380 381:- multifile 382 prolog:message//1. 383 384prologmessage(random(no_gmp)) --> 385 [ 'This version of SWI-Prolog is not compiled with GMP support.'-[], nl, 386 'Floating point random operations are not supported.'-[] 387 ].