nextPermutation and ranges

[Marco Leise]

Am Thu, 7 Feb 2013 13:52:01 -0800
schrieb "H. S. Teoh" <hsteoh at quickfur.ath.cx>:

> On Thu, Feb 07, 2013 at 09:42:34PM +0100, bearophile wrote:
> > H. S. Teoh:
> > 
> > >Combinatorial puzzles come to mind (Rubik's cube solvers and its ilk,
> > >for example).  Maybe other combinatorial problems that require some
> > >kind of exhaustive state space search. Those things easily go past
> > >20!  once you get beyond the most trivial cases.
> > 
> > I know many situations/problems where you have more than 20! cases,
> > but in those problems you don't iterate all permutations, because the
> > program takes ages to do it. In those programs you don't use
> > nextPermutation, you scan the search space in a different and smarter
> > way.
> > 
> > I don't know of any use case for permuting so large sets of items.
> [...]
> 
> It depends, sometimes in complex cases you have no choice but to do
> exhaustive search. I agree that it's very rare, though.
> 
> 
> T
> 

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.

-- 
Marco