random_permutations

enum_fd_random(Var,Low,Up) :-
    init_random_permutations,
    IntervalLength is Up - Low + 1,
    get_num_bits(IntervalLength,MaxIdx,NumBits),
    get_masks(NumBits,LeftMask,RightMask),
    % the seed relies on the random predicate, not on now/1, thus prob can be made deterministic by setting a central random seed
    random(TempSeed),
    Seed is floor(TempSeed * 10000),
    enum_fd_random_aux(Var,0,MaxIdx,Low,Up,Seed,NumBits,LeftMask,RightMask).

enum_fd_random_aux(Var,CurIdx,MaxIdx,From,To,Seed,NumBits,LeftMask,RightMask) :-
    random_permutation_element(CurIdx,MaxIdx,From,To,Seed,NumBits,LeftMask,RightMask,Drawn,NextIdx),
    (Var=Drawn ; enum_fd_random_aux(Var,NextIdx,MaxIdx,From,To,Seed,NumBits,LeftMask,RightMask)).

foreign(get_num_bits, c, get_num_bits(+integer,-integer,-integer)).

foreign(draw_index, c, draw_index(+integer,+integer,+integer,+integer,+integer,+integer,+integer,+integer,-integer,-integer)).

foreign_resource(random_permutations,[get_num_bits,draw_index]).

get_masks(HalfNumBits,LeftMask,RightMask) :-
    RightMask is (1 << HalfNumBits) - 1,
    LeftMask is RightMask << HalfNumBits.

init_random_permutations :- is_initialised,!.

init_random_permutations :-
    safe_load_foreign_resource(random_permutations,random_permutations),
    assertz(is_initialised).

random_permutation_element(Index,MaxIndex,From,To,Seed,NumBits,LeftMask,RightMask,RandomElement,NextIndex) :-
    draw_index(Index,MaxIndex,Seed,NumBits,LeftMask,RightMask,From,To,DrawnElement,NextIndex),
    % working on a 4^x long interval. thus, we might pick a number that is too large
    % if this happens, we just pick a new one
    % to avoid context switching overhead, this is now done inside the C code
    RandomElement is DrawnElement + From.