random cover of a range

[Andrei Alexandrescu]

Denis Koroskin wrote:
> 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

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