1		% (c) 2009-2026 Lehrstuhl fuer Softwaretechnik und Programmiersprachen,
2		% Heinrich Heine Universitaet Duesseldorf
3		% This software is licenced under EPL 1.0 (http://www.eclipse.org/org/documents/epl-v10.html)
4
5		:- module(random_permutations, [get_num_bits/3,
6		get_masks/3,
7		random_permutation_element/10,
8		init_random_permutations/0,
9
10		enum_fd_random/3 % high-level predicate
11		]).
12
13		:- use_module(probsrc(module_information),[module_info/2]).
14		:- module_info(group,cbc).
15		:- module_info(description,'This module provides on-the-fly construction of random permutations of intervals (no longer used in SICStus 4.10 or newer).').
16
17		foreign_resource(random_permutations,[get_num_bits,draw_index]).
18		foreign(get_num_bits, c, get_num_bits(+integer,-integer,-integer)).
19		foreign(draw_index, c, draw_index(+integer,+integer,+integer,+integer,+integer,+integer,+integer,+integer,-integer,-integer)).
20
21		:- dynamic is_initialised/0.
22
23		:- use_module(probsrc(pathes_lib),[safe_load_foreign_resource/2]).
24
25		init_random_permutations :- is_initialised,!.
26		init_random_permutations :-
27		safe_load_foreign_resource(random_permutations,random_permutations),
28		assertz(is_initialised).
29
30
31		get_masks(HalfNumBits,LeftMask,RightMask) :-
32		RightMask is (1 << HalfNumBits) - 1,
33		LeftMask is RightMask << HalfNumBits.
34
35		random_permutation_element(Index,MaxIndex,From,To,Seed,NumBits,LeftMask,RightMask,RandomElement,NextIndex) :-
36		draw_index(Index,MaxIndex,Seed,NumBits,LeftMask,RightMask,From,To,DrawnElement,NextIndex),
37		% working on a 4^x long interval. thus, we might pick a number that is too large
38		% if this happens, we just pick a new one
39		% to avoid context switching overhead, this is now done inside the C code
40		RandomElement is DrawnElement + From.
41
42
43		:- use_module(library(random),[random/3]).
44		:- use_module(library(between),[between/3]).
45		% enumerate Prolog/FD variable between low and up in random order
46		% in SICStus 4.10 we have random labeling option which does the same; but seems much slower
47		% | ?- statistics(walltime,_),(random_permutations:enum_fd_random(Var,1,200000),fail ; statistics(walltime,W)).
48		% W = [141558,50] ?
49		% | ?- statistics(walltime,_),(X in 1..2000, labeling([random],[X]), fail ; statistics(walltime,W)).
50		% W = [372383,34] ?
51		% | ?- statistics(walltime,_),(X in 1..20000, labeling([random],[X]), fail ; statistics(walltime,W)).
52		% W = [118049,1943] ?
53		% | ?- statistics(walltime,_),(X in 1..200000, labeling([random],[X]), fail ; statistics(walltime,W)).
54		% W = [323412,198936] ?
55		% see also comments in clpfd_interface.pl
56		% with [enum,random] it is ok
57		% ?- statistics(walltime,_),(X in 1..200000, labeling([enum,random],[X]), fail ; statistics(walltime,W)).
58		% W = [331248,122] ?
59		enum_fd_random(Var,Low,Up) :-
60		init_random_permutations,
61		IntervalLength is Up - Low + 1,
62		( IntervalLength =< 1 << 62, % get_num_bits fails for longer intervals
63		get_num_bits(IntervalLength,MaxIdx,NumBits)
64		-> get_masks(NumBits,LeftMask,RightMask),
65		% the seed relies on the random predicate, not on now/1,
66		% thus prob can be made deterministic by setting a central random seed
67		SeedBound is 1 << 31, % random/3 does not evaluate its bounds
68		random(0,SeedBound,Seed),
69	?	enum_fd_random_aux(Var,0,MaxIdx,Low,Up,Seed,NumBits,LeftMask,RightMask)
70		; % too long for a random permutation: enumerate in order
71		between(Low,Up,Var)
72		).
73
74		enum_fd_random_aux(Var,CurIdx,MaxIdx,From,To,Seed,NumBits,LeftMask,RightMask) :-
75		random_permutation_element(CurIdx,MaxIdx,From,To,Seed,NumBits,LeftMask,RightMask,Drawn,NextIdx),
76	?	(Var=Drawn ; enum_fd_random_aux(Var,NextIdx,MaxIdx,From,To,Seed,NumBits,LeftMask,RightMask)).
77
78
79		% -------------------
80		% Testing predicates
81		% -------------------
82		% unused at the moment:
83		%:- public shuffle/2.
84		%:- use_module(library(system)).
85		%shuffle(From,To) :-
86		% init_random_permutations,
87		% IntervalLength is To - From + 1,
88		% get_num_bits(IntervalLength,MaxIndex,NumBits),
89		% get_masks(NumBits,LeftMask,RightMask),
90		% now(Seed),
91		% shuffle(From,0,To,MaxIndex,Seed,NumBits,LeftMask,RightMask).
92		%shuffle(From,CurIdx,To,MaxIndex,Seed,NumBits,LeftMask,RightMask) :-
93		% random_permutation_element(CurIdx,MaxIndex,From,To,Seed,NumBits,LeftMask,RightMask,Drawn,NextIdx),
94		% format('Drawing index ~w resulted in ~w~n',[CurIdx,Drawn]),
95		% shuffle(From,NextIdx,To,MaxIndex,Seed,NumBits,LeftMask,RightMask).
96		%shuffle(_,_,_,_,_,_,_,_).