Thread: Algorithm to separate a vector into two others

  1. #1
    Registered User
    Join Date
    Nov 2008
    Posts
    3

    Algorithm to separate a vector into two others

    Hello !

    I have a question.
    I need to make an algorithm to separate a vector of 2*n ints into two vector of n ints, but the sum of both vectors (absolute) must be the lowest.

    Example :
    Code:
    The "big" vector : 1000 2 3 4 5 6 7 2000
    n = 4
    The two vectors must be :
    - 2000 2 3 4 ; sum = 2009
    - 1000 5 6 7 ; sum = 1018
    abs(2009 - 1018) = 991  (which is the lowest)
    I searched all the web to find an algorithm like this, but i didn't found it.


    If you can help me, it would be very nice

  2. #2
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    I am still trying to wrap my head around your question... What? Are you just arbitrarily splitting up a large vector or is there some rationale behind how it is split?

  3. #3
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    This is a variant of the Partitioning Problem. In this case you're looking for the closest approximation to the exact partition.

  4. #4
    Registered User
    Join Date
    Nov 2008
    Posts
    3
    First I thinked it was a partitioning problem.
    But, in the partitoning problem, you don't have two vectors of the same size...

  5. #5
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    But perhaps you can modify an algorithm that solves the Partitioning Problem to suit your current problem?

  6. #6
    Registered User
    Join Date
    Nov 2008
    Posts
    3
    Yes, I think it is what I will do.
    If it don't work, I will find the algorithm alone... (I began, but it isn't very optimizated)

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Implement of a Fast Time Series Evaluation Algorithm
    By BiGreat in forum C Programming
    Replies: 7
    Last Post: 12-04-2007, 02:30 AM
  2. Replies: 4
    Last Post: 12-10-2006, 07:08 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM