Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight
 
PerlMonks  

Re^3: Another word puzzle with too many permutations

by oiskuu (Friar)
on Oct 15, 2013 at 22:13 UTC ( #1058362=note: print w/ replies, xml ) Need Help??


in reply to Re^2: Another word puzzle with too many permutations
in thread Another word puzzle with too many permutations

This looks like a multiple-constrained Knapsack problem. All bets are off...


Comment on Re^3: Another word puzzle with too many permutations
Replies are listed 'Best First'.
Re^4: Another word puzzle with too many permutations (multiple dimensions)
by LanX (Canon) on Oct 16, 2013 at 16:07 UTC
    > This looks like a multiple-constrained Knapsack problem.

    Yes, kind off.

    > All bets are off...

    Well IMHO the multidimensionality makes it much easier to solve.

    The trick is always to always concentrate on the smallest dimension.

    E.g. there is no V allowed, about 6 dog-names have a V, so they can be excluded right away for the rest of the search.

    Then there is only 1 Z allowed, only about 7 dog-names include a Z.

    After trying each Z-names out in the first level, all other Z-Names must be excluded for the next levels.

    And trying one Z-name also diminishes other characters which become minimal now, so other names can be excluded for the subtree. (e.g. Xoloitzcuintli includes an X, but only one X was allowed, all other X-names must be excluded now, and so on)

    IMHO the search tree becomes comparatively small with this strategy. (brute force has a worst case of faculty(n) combinations to check with n=100 here)

    Cheers Rolf

    ( addicted to the Perl Programming Language)

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1058362]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (11)
As of 2015-07-30 09:20 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (270 votes), past polls