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 random_subseq/3, % ?List, ?Subseq, ?Complement 52 53 randseq/3, % +Size, +Max, -Set 54 randset/3, % +Size, +Max, -List 55 random_permutation/2, % ?List, ?Permutation 56 random_numlist/4, % +P, +L, +U, -List 57 58 % deprecated interface 59 random/3 % +Low, +High, -Random 60 ]). 61:- autoload(library(apply),[maplist/2]). 62:- autoload(library(error), 63 [must_be/2,domain_error/2,instantiation_error/1]). 64:- autoload(library(lists),[nth0/3,nth0/4,append/3]). 65:- autoload(library(pairs),[pairs_values/2]). 66 67 68/** <module> Random numbers 69 70This library is derived from the DEC10 library random. Later, the core 71random generator was moved to C. The current version uses the SWI-Prolog 72arithmetic functions to realise this library. These functions are based 73on the GMP library. 74 75@author R.A. O'Keefe, V.S. Costa, L. Damas, Jan Wielemaker 76@see Built-in function random/1: A is random(10) 77*/ 78 79check_gmp :- 80 current_arithmetic_function(random_float), 81 !. 82check_gmp :- 83 print_message(warning, random(no_gmp)). 84 85:- initialization check_gmp. 86 87 88 /******************************* 89 * PRIMITIVES * 90 *******************************/ 91 92%! random(-R:float) is det. 93% 94% Binds R to a new random float in the _open_ interval (0.0,1.0). 95% 96% @see setrand/1, getrand/1 may be used to fetch/set the state. 97% @see In SWI-Prolog, random/1 is implemented by the function 98% random_float/0. 99 100random(R) :- 101 R is random_float. 102 103%! random_between(+L:int, +U:int, -R:int) is semidet. 104% 105% Binds R to a random integer in [L,U] (i.e., including both L and 106% U). Fails silently if U<L. 107 108random_between(L, U, R) :- 109 integer(L), integer(U), 110 !, 111 U >= L, 112 R is L+random((U+1)-L). 113random_between(L, U, _) :- 114 must_be(integer, L), 115 must_be(integer, U). 116 117 118%! random(+L:int, +U:int, -R:int) is det. 119%! random(+L:float, +U:float, -R:float) is det. 120% 121% Generate a random integer or float in a range. If L and U are 122% both integers, R is a random integer in the half open interval 123% [L,U). If L and U are both floats, R is a float in the open 124% interval (L,U). 125% 126% @deprecated Please use random/1 for generating a random float 127% and random_between/3 for generating a random integer. Note that 128% random_between/3 includes the upper bound, while this 129% predicate excludes it. 130 131random(L, U, R) :- 132 integer(L), integer(U), 133 !, 134 R is L+random(U-L). 135random(L, U, R) :- 136 number(L), number(U), 137 !, 138 R is L+((U-L)*random_float). 139random(L, U, _) :- 140 must_be(number, L), 141 must_be(number, U). 142 143 144 /******************************* 145 * STATE * 146 *******************************/ 147 148%! setrand(+State) is det. 149%! getrand(-State) is det. 150% 151% Query/set the state of the random generator. This is intended 152% for restarting the generator at a known state only. The 153% predicate setrand/1 accepts an opaque term returned by 154% getrand/1. This term may be asserted, written and read. The 155% application may not make other assumptions about this term. 156% 157% For compatibility reasons with older versions of this library, 158% setrand/1 also accepts a term rand(A,B,C), where A, B and C are 159% integers in the range 1..30,000. This argument is used to seed 160% the random generator. Deprecated. 161% 162% @see set_random/1 and random_property/1 provide the SWI-Prolog 163% native implementation. 164% @error existence_error(random_state, _) is raised if the 165% underlying infrastructure cannot fetch the random state. 166% This is currently the case if SWI-Prolog is not compiled 167% with the GMP library. 168 169setrand(rand(A,B,C)) :- 170 !, 171 Seed is A<<30+B<<15+C, 172 set_random(seed(Seed)). 173setrand(State) :- 174 set_random(state(State)). 175 176:- if(current_predicate(random_property/1)). 177getrand(State) :- 178 random_property(state(State)). 179:- else. 180getrand(State) :- 181 existence_error(random_state, State). 182:- endif. 183 184 185 /******************************* 186 * MAYBE * 187 *******************************/ 188 189%! maybe is semidet. 190% 191% Succeed/fail with equal probability (variant of maybe/1). 192 193maybe :- 194 random(2) =:= 0. 195 196%! maybe(+P) is semidet. 197% 198% Succeed with probability P, fail with probability 1-P 199 200maybe(P) :- 201 must_be(between(0.0,1.0), P), 202 random_float < P. 203 204%! maybe(+K, +N) is semidet. 205% 206% Succeed with probability K/N (variant of maybe/1) 207 208maybe(K, N) :- 209 integer(K), integer(N), 210 between(0, N, K), 211 !, 212 random(N) < K. 213maybe(K, N) :- 214 must_be(nonneg, K), 215 must_be(nonneg, N), 216 domain_error(not_less_than_zero,N-K). 217 218 219 /******************************* 220 * PERMUTATION * 221 *******************************/ 222 223%! random_perm2(?A, ?B, ?X, ?Y) is semidet. 224% 225% Does X=A,Y=B or X=B,Y=A with equal probability. 226 227random_perm2(A,B, X,Y) :- 228 ( maybe 229 -> X = A, Y = B 230 ; X = B, Y = A 231 ). 232 233 234 /******************************* 235 * SET AND LIST OPERATIONS * 236 *******************************/ 237 238%! random_member(-X, +List:list) is semidet. 239% 240% X is a random member of List. Equivalent to random_between(1, 241% |List|), followed by nth1/3. Fails of List is the empty list. 242% 243% @compat Quintus and SICStus libraries. 244 245random_member(X, List) :- 246 must_be(list, List), 247 length(List, Len), 248 Len > 0, 249 N is random(Len), 250 nth0(N, List, X). 251 252%! random_select(-X, +List, -Rest) is semidet. 253%! random_select(+X, -List, +Rest) is det. 254% 255% Randomly select or insert an element. Either List or Rest must 256% be a list. Fails if List is the empty list. 257% 258% @compat Quintus and SICStus libraries. 259 260random_select(X, List, Rest) :- 261 ( '$skip_list'(Len, List, Tail), 262 Tail == [] 263 -> true 264 ; '$skip_list'(RLen, Rest, Tail), 265 Tail == [] 266 -> Len is RLen+1 267 ), 268 !, 269 Len > 0, 270 N is random(Len), 271 nth0(N, List, X, Rest). 272random_select(_, List, Rest) :- 273 partial_list(List), partial_list(Rest), 274 instantiation_error(List+Rest). 275random_select(_, List, Rest) :- 276 must_be(list, List), 277 must_be(list, Rest). 278 279%! random_subseq(+List, -Subseq, -Complement) is det. 280%! random_subseq(-List, +Subseq, +Complement) is semidet. 281% 282% Selects a random subsequence Subseq of List, with Complement 283% containing all elements of List that were not selected. Each element 284% of List is included with equal probability in either Subseq or 285% Complement. 286% 287% random_subseq/3 may also be called with Subseq and Complement bound 288% and List unbound, which will recreate List by randomly interleaving 289% Subseq and Complement. This mode may fail randomly, matching SICStus 290% behavior. The failure probability corresponds to the probability of 291% the "forward" mode selecting a Subseq/Complement combination with 292% different lengths. 293% 294% @compat SICStus 4 295 296random_subseq([], [], []). 297random_subseq([Head|Tail], Subseq, Complement) :- 298 ( maybe 299 -> Subseq = [Head|SubTail], 300 Complement = CompTail 301 ; Subseq = SubTail, 302 Complement = [Head|CompTail] 303 ), 304 random_subseq(Tail, SubTail, CompTail). 305 306%! randset(+K:int, +N:int, -S:list(int)) is det. 307% 308% S is a sorted list of K unique random integers in the range 1..N. 309% The implementation uses different techniques depending on the ratio 310% K/N. For small K/N it generates a set of K random numbers, removes 311% the duplicates and adds more numbers until |S| is K. For a large K/N 312% it enumerates 1..N and decides randomly to include the number or 313% not. For example: 314% 315% == 316% ?- randset(5, 5, S). 317% S = [1, 2, 3, 4, 5]. (always) 318% ?- randset(5, 20, S). 319% S = [2, 7, 10, 19, 20]. 320% == 321% 322% @see randseq/3. 323 324randset(K, N, S) :- 325 must_be(nonneg, K), 326 K =< N, 327 ( K < N//7 328 -> randsetn(K, N, [], S) 329 ; randset(K, N, [], S) 330 ). 331 332randset(0, _, S, S) :- !. 333randset(K, N, Si, So) :- 334 random(N) < K, 335 !, 336 J is K-1, 337 M is N-1, 338 randset(J, M, [N|Si], So). 339randset(K, N, Si, So) :- 340 M is N-1, 341 randset(K, M, Si, So). 342 343randsetn(K, N, Sofar, S) :- 344 length(Sofar, Len), 345 ( Len =:= K 346 -> S = Sofar 347 ; Needed is K-Len, 348 length(New, Needed), 349 maplist(srand(N), New), 350 ( Sofar == [] 351 -> sort(New, Sorted) 352 ; append(New, Sofar, Sofar2), 353 sort(Sofar2, Sorted) 354 ), 355 randsetn(K, N, Sorted, S) 356 ). 357 358srand(N, E) :- 359 E is random(N)+1. 360 361%! randseq(+K:int, +N:int, -List:list(int)) is det. 362% 363% S is a list of K unique random integers in the range 1..N. The 364% order is random. Defined as 365% 366% ``` 367% randseq(K, N, List) :- 368% randset(K, N, Set), 369% random_permutation(Set, List). 370% ``` 371% 372% @see randset/3. 373 374randseq(K, N, Seq) :- 375 randset(K, N, Set), 376 random_permutation_(Set, Seq). 377 378%! random_permutation(+List, -Permutation) is det. 379%! random_permutation(-List, +Permutation) is det. 380% 381% Permutation is a random permutation of List. This is intended to 382% process the elements of List in random order. The predicate is 383% symmetric. 384% 385% @error instantiation_error, type_error(list, _). 386 387random_permutation(List1, List2) :- 388 is_list(List1), 389 !, 390 random_permutation_(List1, List2). 391random_permutation(List1, List2) :- 392 is_list(List2), 393 !, 394 random_permutation_(List2, List1). 395random_permutation(List1, List2) :- 396 partial_list(List1), partial_list(List2), 397 !, 398 instantiation_error(List1+List2). 399random_permutation(List1, List2) :- 400 must_be(list, List1), 401 must_be(list, List2). 402 403random_permutation_(List, RandomPermutation) :- 404 key_random(List, Keyed), 405 keysort(Keyed, Sorted), 406 pairs_values(Sorted, RandomPermutation). 407 408key_random([], []). 409key_random([H|T0], [K-H|T]) :- 410 random(K), 411 key_random(T0, T). 412 413%! random_numlist(+P, +L, +U, -List) is det. 414% 415% Unify List with an ascending list of integers between L and U 416% (inclusive). Each integer in the range L..U is included with 417% probability P. 418% 419% @compat SICStus 4 420 421random_numlist(P, L, U, List) :- 422 must_be(between(0.0, 1.0), P), 423 must_be(integer, L), 424 must_be(integer, U), 425 random_numlist_(P, L, U, List). 426random_numlist_(_P, L, U, List) :- 427 L > U, 428 !, 429 List = []. 430random_numlist_(P, L, U, List) :- 431 ( maybe(P) 432 -> List = [L|Tail] 433 ; List = Tail 434 ), 435 L1 is L + 1, 436 random_numlist_(P, L1, U, Tail). 437 438%! partial_list(@Term) is semidet. 439% 440% True if Term is a partial list. 441 442partial_list(List) :- 443 '$skip_list'(_, List, Tail), 444 var(Tail). 445 446:- multifile 447 prolog:message//1. 448 449prologmessage(random(no_gmp)) --> 450 [ 'This version of SWI-Prolog is not compiled with GMP support.'-[], nl, 451 'Floating point random operations are not supported.'-[] 452 ]