3 ms·
It is an overly strict interpretation of that rule to assume it prohibits any randomized algorithm. Aren't these the same steps for any given input? 1) Roll
by mkbosmans 5y ago
It is an overly strict interpretation of that rule to assume it prohibits any randomized algorithm.
Aren't these the same steps for any given input?
1) Roll dice to get random number N
2) Get the Nth permutation of the input sequence (for some ordering of permutations)
3) Permute input sequence
4) If sorted: done, else goto step 1
- olliej 5y agoYou have to specify the output of rolling the die. If you use an RNG you would provide the seed state for the RNG as an input to the algorithm. Think of it as “can I run this algorithm on a Turing machine”