Denis Koroskin wrote:
On Fri, 13 Feb 2009 19:04:54 +0300, Andrei Alexandrescu
<seewebsiteforem...@erdani.org> wrote:
bearophile wrote:
Andrei Alexandrescu>The quest for finding a random cover of an array
with as little extra memory consumed and with good complexity is on!<
This thread is very long and complex, I am unable to understand where
to start reading, etc. So can someone explain the problem to me, so I
may be able to suggest some idea/code?
Given an array of length m, return a range that iterates the array in
random order such that the entire array is visited without going
through the same element more than once. Consume minimal amounts of
memory and time. Baseline solution: allocate an array of indices,
shuffle it, then follow indices stored in the array.
Andrei
In ideal world I'd like to see the following permutations generator in
std library, instead:
auto range = [0, 1, 2, 3, 4, 5];
auto perms = permutations(range); // a random-access range that returns
lazy permutation generators.
auto permutation = perms[0]; // get first permutation out of range.length!
// auto permutation = perms(uniform(0, perms.length)); // get random
permutation
That can be done easily if you settle for forward iteration. The problem
is that there are N! permutations of N objects, so reaching any
interesting permutation will take a long time.
Andrei
