On Friday, 8 February 2013 at 06:59:20 UTC, Marco Leise wrote:
Am Thu, 7 Feb 2013 13:52:01 -0800
schrieb "H. S. Teoh" <[email protected]>:
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.
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.
