[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