Could you please expand on your linked code, not really a C++ programmer and line 22/25 confuse me a bit?
Unfortunately I don't understand how each element has the same probability of being chosen.
I.e. the first element seems to have a probability of 1/n, while the second has 1/n + 1/(n-1) etc. Am i wrong about this?
/* This is standard modern C++ random number generation.
It means, using the random generator "engine", return
a number according to distribution "dist". In this
"dist" is a uniform distribution from "i" to "max-min".
"auto" is the new way to type variables in C++: it
infers the type of the variable from the type of the
expression */
22: auto index = dist(engine);
/* The following lines are a bit more complex, as they
contain a nested expression. Let us focus on the inner
expression:
(index < size ) ? array[index]
: map.insert({index, min + index}).first->second
This is in the form:
test-expr ? when-true-expr
: when-false-expr
This expression is a ternary condition. What it means
is that the expression before the question mark is
computed (index < size), and if it evaluates to true,
the overall expression will resolve to the result of
the expression between the question mark and the colon,
otherwise it resolves to what is after the colon.
Here, it means that if "index" is smaller than "size",
use "array[index]", otherwise insert a new entry in the
map, with key "index" and value "min+index", then reuse
the result of the operation by accessing member "second"
of the member "first". I am not familiar with STL maps;
here is an explanation of the map::insert method from
cplusplus.com:
The single element versions (1) return a pair, with
its member pair::first set to an iterator pointing
to either the newly inserted element or to the
element with an equivalent key in the map. The
pair::second element in the pair is set to true if
a new element was inserted or false if an equivalent
key already existed.
*/
23: std::swap(array[i], index < size
24: ? array[index]
25: : map.insert({index, min + index}).first->second);
/* Then, the std::swap operation simply swaps the two indicated
values in the array. */
> Unfortunately I don't understand how each element has the same probability of being chosen. I.e. the first element seems to have a probability of 1/n, while the second has 1/n + 1/(n-1) etc. Am i wrong about this?
This is just a partial Fisher-Yates shuffle[1] using a sparse sequence instead of an array. Keep in mind that if an element is not chosen it is swapped with the chosen element and will be considered again. I think the best way to think about it is that you are choosing a random element from the set and then "removing" it from the set with the swap and then repeating.
Unfortunately I don't understand how each element has the same probability of being chosen. I.e. the first element seems to have a probability of 1/n, while the second has 1/n + 1/(n-1) etc. Am i wrong about this?