[Haskell-cafe] What algorithm to use ?

Brandon S. Allbery KF8NH allbery at ece.cmu.edu
Mon Oct 22 06:36:10 EDT 2007

On Oct 22, 2007, at 4:09 , manu wrote:

> However looking at the number of permutations (26! =  
> 403291461126605635584000000), quickly dampened my enthusiasm...
> There must be some algorithm (dynamic programming ?), that cuts  
> down the number of calculations involved in order to find the right  
> combination. But I cannot identify the proper algorithm to use...

Being that I'm lousy at algorithms, I'm sure someone else will come  
up with something far better... but it occurs to me that you have  
enough information to reorder the search space such that you're more  
likely to find a combination which beats most of the search space  
early in an exhaustive search.  For example, combinations of even- 
length names and even-numbered programmers take a time hit of 2 hours  
right off the bat due to the common prime factor 2, so you can  
probably defer those until you've exhausted other possibilities; even  
more so for names with many vowels.  And if you find a combination  
whose time is less than some combination of delays, you can  
immediately drop any possibility which incurs those delays.

brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery at kf8nh.com
system administrator [openafs,heimdal,too many hats] allbery at ece.cmu.edu
electrical and computer engineering, carnegie mellon university    KF8NH

More information about the Haskell-Cafe mailing list