
May 23rd, 2013, 05:48 AM
#1
Algorithm for finding subset of permutations with maximum value
Hello,
Can anyone help with suggestions for implementation of an efficient algorithm for the following issue:
Given a list of permutations with a score for each permutation, we need to find a subset of permutations with the highest summed score, given the condition that any one of permutation in the subset will not intersect or be contained with another permutation in the subset.
For example, given the following list of permutations, marked as Index: start, end, score, permutation A cannot be in the same subset with permutation B, since they intersect with each other. Permutation C cannot be in the same subset with permutation F, since permutation F is contained within permutation C.
A: 43 70 27
B: 45 74 26
C: 3 28 24
D: 65 99 45
E: 20 39 26
F: 10 18 20
G: 78 97 23
I guess the challenge is to implelent this in O(NlogN) rather than the naïve implemention of O(N2)
Thanks in advance!
Tom.

May 23rd, 2013, 10:02 AM
#2
Re: Algorithm for finding subset of permutations with maximum value
This is essentially a "knapsack" problem (see wikipedia), and is loosely in the same type of problems as the travelling salesman.
or in short, no actual algorithm exists for this.
for small datasets you can bruteforce an answer
for large datasets, you can only find a "good" answer within a certain amount of time but you can't guarantee "the best" answer in a reasonable amount of time.
A variety of different methods have been used to find solutions to this with various success and performance. such as ant farms, genetic algorithms, ...

May 23rd, 2013, 04:50 PM
#3
Re: Algorithm for finding subset of permutations with maximum value
Originally Posted by OReubens
or in short, no actual algorithm exists for this.
Of course there exists an algorithm. This for example,
1. Generate all possible subsets of the N "permutations". There are 2^N such subsets.
2. From all possible subsets select the valid (no conflicting "permutations") subsets.
3. From all valid subsets pick the one(s) with the highest score sum.
This is not a polynominal algorithm (it's something like O(2^N * N * logN)) so it's intractable for big N, still it's a working algorithm.
Last edited by nuzzle; May 24th, 2013 at 09:53 AM.

May 23rd, 2013, 04:56 PM
#4
Re: Algorithm for finding subset of permutations with maximum value
Originally Posted by mayeri
I guess the challenge is to implelent this in O(NlogN) rather than the naïve implemention of O(N2)
Well if you have an O(N^2) algorithm already you've come quite far.
To me it looks like your problem is equivalent to the Weighted Interval Scheduling Problem. To see that you only have to view your "permutations" as weighted time intervals (jobs) with a start time, an end time and a weight (score).
http://pages.cs.wisc.edu/~shuchi/cou...notes/lec3.pdf
According to the article there's an O(N * logN) algorithm available indeed for this problem.
Last edited by nuzzle; May 24th, 2013 at 04:57 AM.
Tags for this Thread
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
This is a Codeguru.com survey!
