nextPermutation and ranges

[H. S. Teoh]

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

-- 
Perhaps the most widespread illusion is that if we were in power we
would behave very differently from those who now hold it---when, in
truth, in order to get power we would have to become very much like
them. -- Unknown