Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine
 
PerlMonks  

Re^3: Another word puzzle with too many permutations

by oiskuu (Pilgrim)
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
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 surveying the Monastery: (7)
As of 2014-07-11 11:47 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    When choosing user names for websites, I prefer to use:








    Results (224 votes), past polls