CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 4 of 4
  1. #1
    Join Date
    May 2013
    Posts
    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.

  2. #2
    Join Date
    Apr 2000
    Location
    Belgium (Europe)
    Posts
    4,626

    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, ...

  3. #3
    Join Date
    May 2009
    Posts
    2,413

    Re: Algorithm for finding subset of permutations with maximum value

    Quote Originally Posted by OReubens View Post
    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 08:53 AM.

  4. #4
    Join Date
    May 2009
    Posts
    2,413

    Re: Algorithm for finding subset of permutations with maximum value

    Quote Originally Posted by mayeri View Post
    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 03: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
  •  





Click Here to Expand Forum to Full Width

Featured