CODEWITHSUNDEEP
c++algorithmsorting
Derrick Johnson
Derrick Johnson

Reputation: 385

How to efficiently calculate the top permutations

I have a 2D array of letters, each with a score. For example:

J-95 O-90 H-92 N-99
I-91 0-89 L-55
1-80
T-55

From the above array, I would like to get a list of the top 20 or so permutations (by score) quickly. In the above example, the list would be:

JOHN
IOHN
J0HN
I0HN
... etc

I'm currently doing this in a recursive function -- but it is slower than I'd like. Is there any good way to get a top N list quickly? My code is C++ (if there are good library suggestions).

Thanks

Edit:

I solved this using a combination of Sneftel and Ethan's answers. I used a pruning function to reduce the possible characters based on the weights, then calculated the permutations from that.

Upvotes: 0

Views: 479

Answers (3)

ritual_code
ritual_code

Reputation: 147

for examples of perm code rosetta code has some great examples in many languages this is in c++. Once you get your permutations code working you can make a return biggestscore function and maybe use a map to map words to scores. 

    char** permutations(char *word, int len){
        ... //the perm code
    }
    //returns array of cstrings permutations

    char** returnBiggestScore(char **permutations, int len){
        ...// your score logic goes here
    }
    //would return the top five say,

In your main program you can do something like this:

returnBiggestScores(permutations("hello"));

How you code your return biggest score is up to you, but I suggest using a map object, that way you can check for the score of any arbitrary letter in constant time like so:

score['B']; //fast and convinient returns score value for key 'B'

Upvotes: 1

Sneftel
Sneftel

Reputation: 41474

This problem is actually NP-complete; it is a form of the "Multiple Choice Knapsack Problem" (MCKP).

A simple approach which may work out for you is to generate combinations from the top 1 letter in each slot, then the top 2 letters in each slot, then the top 3, etc., and stop once two iterations in a row produce the same top 20 scores. This isn't guaranteed to be any more efficient than a brute force search, but it's simple to implement and will work well for the "general" case.

Upvotes: 2

Ethan Fang
Ethan Fang

Reputation: 1269

First of all, you need to sort your candidates. It takes O(nlgn) time.

N-99 J-95 H-92 I-91 O-90 0-89 1-80 L-55 T-55

Secondly, depending on how many best scores you need, you choose the top n number of characters to do the permutation.

(n)*(n-1)*(n-2)*(n-3) / (1 * 2 * 3 * 4) >= m.

n is the number of candidates you choose. m is the number of best scores you need. For example, if you need 20 best scores, you only do set of 7 characters. Probably the problem you face is that you do the permutation with all candidates while it is a waste to do it with some very low candidates.

Third step is get all the permutations you need, then sort it and print.

Upvotes: 3

Related Questions