nextPermutation and ranges

[John Colvin]

On Saturday, 9 February 2013 at 01:07:13 UTC, H. S. Teoh wrote:
> On Sat, Feb 09, 2013 at 01:37:34AM +0100, John Colvin wrote:
>> On Friday, 8 February 2013 at 21:07:58 UTC, Era Scarecrow 
>> wrote:
>> >On Friday, 8 February 2013 at 12:27:50 UTC, John Colvin wrote:
>> >>On Friday, 8 February 2013 at 06:59:20 UTC, Marco Leise 
>> >>wrote:
>> >>>
>> >>>So right now we can handle 20! = 2,432,902,008,176,640,000
>> >>>permutations. If every check took only 20 clock cycles of a 
>> >>>4
>> >>>Ghz CPU, it would take you ~386 years to go through the 
>> >>>list.
>> >>>For the average human researcher this is plenty of time.
>> >>
>> >>On a modern supercomputer this would take well under 2 
>> >>months.
>> >>(I calculated it as ~44 days on Minerva at Warwick,  UK). 19!
>> >>would take less than 3 days.
>> >>
>> >>In a parallel setting, such large numbers are assailable.
>> >
>> > If we have such a large number of computations, then either 
>> > cent
>> >will have to be implemented, use BigInt, or an internal array 
>> >that
>> >handles locational information. That would remove the 
>> >limitations
>> >of 20 to either 255, or 65535 (assuming you EVER need that 
>> >many).
>> >Course rummaging through the array for the next computation
>> >becomes more difficult the larger the number of elements.
>> 
>> Seeing as 61! is of the order of the number of atoms in the
>> observable universe, i don't think there's much need to plan 
>> for any
>> higher than that!
>
> That doesn't prevent mathematicians from grappling with numbers 
> like
> Graham's number (see wikipedia entry), the magnitude of which 
> exploded
> my perception of infinity several times over, and it's still 
> *finite*.
> ;-)
>
> Iterating over such inconceivably huge numbers is, of course, a 
> fool's
> errand.
>
> But being able to *index* a large set of permutations is 
> actually
> valuable. In this sense, bearophile's factorial method, suitably
> extended to some BigInt index, is superior, not because you 
> want to
> iterate over the entire gigantic list of possibilities, but 
> because
> using BigInt allows you to index a particular entry in that 
> list without
> having to go through them all.
>
>
> T

This is a fair point. Being able to obtain the kth permutation of 
a large set would indeed be useful, even if iteration is not 
feasible. For example, you might want to examine the k=2^n  
perturbations, as you have some a priori knowledge that they 
contain the solution you're looking for.

In that case we'd want to be able to index with an effectively 
arbitrary size index. I don't have any experience with bigint but 
I presume it's the correct tool for the job.