random cover of a range

[Denis Koroskin]

On Fri, 13 Feb 2009 19:04:54 +0300, Andrei Alexandrescu <SeeWebsiteForEmail at 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