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
// print all possible permutations of a given array
foreach (p; perms) {
// print a given permutation
foreach (e; p) {
write(e, " ");
}
writeln(); // new line
}
BTW, I think it's ok to have permutation generator that consumes O(N) memory
and runs at constant time.
It would be totally awesome if generator would accept temporary buffer as an
optional parameter:
auto range = ...;
auto buffer = cast(int*)alloca(int.sizeof * range.length)[0..range.length];
auto perms = permutations(range, buffer);
// same code afterwards
