CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 9 of 9
  1. #1
    Join Date
    Jan 2015
    Posts
    2

    How to partitioning a list

    I get one problem with how to partitioning a integer list. I would like to divide this list into N sublist, where the sum of all entries is M. For example, let the list be

    list ={1, 2, 3, 4, 5, 4, 5}.

    I would like to divid this group into 3 sub-list, where the sum of all entries of each sub-list is 8. We have list_1 = {1, 2, 5}, list_2 = {3, 5} and list_3 = {4, 4}.

    Could anyone give me a bit hint of this? Thanks very much!

  2. #2
    Join Date
    Jul 2013
    Posts
    576

    Re: How to partitioning a list

    Can list numbers be negative? That radically would change the complexity of the problem.

    Is there some particular reason you wanted exactly 3 sublists? Why not 1 or 4 or all?

    I guess one solution would be to generate all sublists exhaustively and simply pick those that sum up to M. The list cannot be too long because the number of sublists quickly becomes untractably many. But still, it's general and can handle negative numbers. How long lists do you have?

  3. #3
    Join Date
    Jan 2015
    Posts
    2

    Re: How to partitioning a list

    Thanks very much, Razzle, for your reply. The list has to be positive and has, say less than 500 entries. The way of partitioning is not unique but always exists. For this problem, I am not interested in find out all the possible solutions.

    I am thinking to setup a rule to exhaust all the combinations of the list. Once the first solution is found, then stop the process, record the sublist, reduce these entries entries from the big list and repeat this loop again. What do you think?

  4. #4
    Join Date
    Jul 2013
    Posts
    576

    Re: How to partitioning a list

    Quote Originally Posted by wideli View Post
    I am thinking to setup a rule to exhaust all the combinations of the list.
    To produce all possible sublist of a 500 numbers long list simply isn't tractable. If I recall correctly there will be 2^500 sublists and that's astronomical. I'd say the practical limit is 25 numbers or something.

    Another approach would be to focus on M. It's possible to efficiently generate all partitions of an integer. Say M=6 then all partitions would be,

    6
    5+1
    4+2
    4+1+1
    3+3
    3+2+1
    3+1+1+1
    2+2+2
    2+2+1+1
    2+1+1+1+1
    1+1+1+1+1+1

    The task then instead becomes to check what partitions are present in the list. For this the list is better turned into a hash table. Unfortunately the number of partitions grow quickly with M so it's only tractable for small M, maybe M<50 or so.

    As a summary an exhaustive solution is feasible only for short lists or small M. That's the curse of combinatorics.
    Last edited by razzle; January 29th, 2015 at 01:09 AM.

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

    Re: How to partitioning a list

    Quote Originally Posted by razzle View Post
    2^500 sublists and that's of the order of all atoms in the known universe.
    2^500 or about 3.27 x 10^150 is hugely larger than the current estimate for the atoms in the univers which is estimated at about 10^80 atoms (assuming all mass would be hydrogen atoms). Some mass isn't even atoms but elementary particles, then there's the still unresolved issues of dark matter and dark energy (and mass = energy ofc)

  6. #6
    Join Date
    Oct 2008
    Posts
    1,456

    Re: How to partitioning a list

    note that the redundancy of the solution could work in your favour for a big list of marginally uniformly distributed numbers and a sufficiently small N.

    more specifically, given the input list a[1],a[2],...,a[K], let s[j] be the partial sum s[j]:=sum_from_1_to_j_of{ a[j] }, then it must be s[K]=N*M

    and let divide the list into N groups a[1],..,a[j[1]],a[j[1]+1],...,a[j[2]],...,a[ j[N] = k ] such as

    s[j[q]]<=q*M and s[j[q]+1]>q*M for every 1<=q<N ( in other words, split the list where the running sum passes through a multiple of M )

    and let d[q] := q*M - s[j[q]]

    clearly, if d[q] == 0 for every q in [1,N] then the list partition given by the j[q]'s is a solution to the problem.

    now, let's suppose d[q] == 0 only up to some q = q'>=0
    then, if there exist items a[u] in the (q'+1)th group and a[v] in the (q'+2)th group in such a way that d[q'+1] = a[v]-a[u], then exchanging a[u] and a[v] would make the new list a solution up to q = q'' = q' + 1, and so on ... up to N
    so, what's the probability that such ordered exchanges exist ?

    hard to tell in general ( because the numbers cannot be statistically indipendent ) but, if we assume the groups asymptotically pair-wise indipendent for K -> infinity ( which is true for any reasonable input distribution ), then I'd say the wanted probability should goes to 1 for K -> infinity and N,M fixed ( I'll post some calculation if you like and I have time ).

    BTW, note that the O(K^2) algorithm above works for your small example list too:

    1, 2, 3, 4, 5, 4, 5 --> divide into 1, 2, 3| 4, 5| 4, 5 --> swap 4-2 = 2 ... nope ( the last group doesn't fit ), then try swap 3 and 5 --> 1, 2, 5| 4, 3| 4, 5 --> swap 4 and 5 --> 1, 2, 5| 5, 3| 4, 4 --> found !

    although it's probably just by chance in this case ...

  7. #7
    Join Date
    Jul 2013
    Posts
    576

    Re: How to partitioning a list

    Quote Originally Posted by superbonzo View Post
    although it's probably just by chance in this case ...
    Well, regardless of how you skin this problem it's going to be NP-complete (SUBSET-SUM). But there is a pseudo-polynominal algorithm based on dynamic programming available which probably is the OPs best hope.
    Last edited by razzle; January 30th, 2015 at 09:33 AM.

  8. #8
    Join Date
    Oct 2008
    Posts
    1,456

    Re: How to partitioning a list

    Quote Originally Posted by razzle View Post
    Well, regardless of how you skin this problem it's going to be NP-complete (SUBSET-SUM). But there is a pseudo-polynominal algorithm based on dynamic programming available which probably is the OPs best hope.
    uhm, no, the fact that an algorithm is NP-complete does not mean that it doesn't have a polynomial ( avarage or worst case ) solution for given subset of input, or input distribution.

    Indeed, the wikipedia algorithm of subset-sum links to the partition problem, that in turn mentions a "differencing" heuristics that as far as I can tell is exactly the algorithm I described above. If the OP (really) expects a uniform distribution of numbers in some fixed range then the probability that this algorithm fails to give a solution should be ~0 for big lists with K/N sufficiently big; this is a valuable info as one could always revert to the full-algo ( or just refuse to give a response ) in the rare case it fails.

  9. #9
    Join Date
    Jul 2013
    Posts
    576

    Re: How to partitioning a list

    Quote Originally Posted by superbonzo View Post
    the fact that an algorithm is NP-complete does not mean that it doesn't have a polynomial ( avarage or worst case ) solution for given subset of input, or input distribution.
    SUBSET-SUM is only "softly" or "weakly" NP-complete. This means it reacts pseudo-polynomically (as I mentioned) to certain inputs. By restricting the input the effective size of the input may be reduced.

    This can be applied ad absurdum. Lets say the list may contain 1's only. Then it's just to scan it and add up the 1's. If this sum equals M before the end is reached you have your partition. Perfectly polynominal, even linear.

    I'm sure your approach is more ambitious than that but let's not resort to wishful thinking. Even though this problem may be tractable for quite substantial inputs it's still NP-complete and intractable for long lists and large M. That's the bottom line.

    Again, this problem is solvable in pseudo-polynominal time. There are well known general standard algorithms that take advantage of this fact available for the OP to investigate.
    Last edited by razzle; February 4th, 2015 at 02:59 AM.

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