Click here to Skip to main content
Click here to Skip to main content
Alternative Tip
Go to top

Subset - Sum Problem with Numeric Collections

, 17 Apr 2014
Rate this:
Please Sign up or sign in to vote.
This is an alternative for "Subset - Sum Problem with Integer Arrays "

Introduction

Here, I am going to solve the Subset-sum problem using an indexable collection. We have to find a set of values where its sum is equal to or greater than some other value.

In this alternative, I've implemented a generic method to generate all of the combinations' indexes for a collection. (i.e., all of the sets of indexes corresponding to all of the combinations of elements.) With that, the extension to non-Integer collections is possible.

For example: Assume there is an integer array int[] values = { 1, 2, 4, 6 }; our problem is to find all the subsets where the sum of the indexed values is >= 10, and set of index's should be unique.

The result should be:

  1. 0,2,3
  2. 1,2,3
  3. 2,3
  4. 0,1,2,3

Using the Code

This is the complete implementation as a simple console application.

First, I calculate how many combinations there are for the collection. Then I iterate through that many combinations, using the current counter (bits) to generate the set of indexes corresponding to that combination. Since each index is represented by a bit in the bits value, all possible combinations will be generated.

using System;
using System.Collections.Generic;
using System.Linq;
 
namespace ConsoleApplication31
{
  class Program
  {
    static void Main(string[] args)
    {
      int[] test = new int[] { 1, 2, 4, 6 };
      int threshold = 10;
      foreach (var item in CombinationIndexes(test).Where(ii => ii.Sum(ix => test[ix]) >= threshold))
      {
        Console.WriteLine(string.Join(",", item.Select(i => i.ToString())));
      }
      Console.ReadLine();
    }
 
    const int BitsInUlong = 8 * sizeof(ulong);
    static IEnumerable<IEnumerable<int>> CombinationIndexes<T>(IList<T> collection)
    {
      if (collection.Count > BitsInUlong)
        throw new ArgumentOutOfRangeException("collection", "collection is too large");
      ulong count = (~(ulong)0) >> (BitsInUlong - collection.Count);
      for (ulong bits = 0; bits <= count; bits++)
      {
        yield return BitNumbers(bits);
      }
    }
 
    static IEnumerable<int> BitNumbers(ulong bits)
    {
      if (bits == 0)
        yield break;
      ulong mask = 1;
      for (int i = 0; i < BitsInUlong; ++i)
      {
        if ((bits & mask) != 0)
        {
          yield return i;
        }
        mask <<= 1;
      }
    }
  }
}

Points of Interest

I use a ulong to represent the indexable positions into the collection while generating the combinations, so the largest collection supported is 64 elements. However, there are 18,446,744,073,709,551,615 combinations of 64 elements, so the restriction isn't that significant!

I could have used BigInteger to remove the restriction on number of elements. That is left as an exercise for the reader.

History

  • First version of the alternative

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Matt T Heffron
Software Developer (Senior) AB Sciex
United States United States
I started programming in Basic on a DECSystem-10 as a Freshman at Caltech in 1974. I quickly transitioned to assembly language, Fortran, and Pascal. As a summer job at JPL, I did analysis of fuel consumption for the Viking Mars Orbiter attitude control system. I also spent a summer doing O/S maintenance at Digital Equipment Corporation.
After graduation, I started developing microprocessor development tools (e.g., cross-compiler, debugger) for Beckman Instruments, a scientific instrument company.
I've worked on custom file-systems, a real-time O/S for Z8000, Expert Systems (SpinPro & PepPro), and internal and external networking support (I was their first webmaster).
I've worked on the DNA analysis system.
I was the console/UI software architect for Ultracentrifuges and protein Capillary Electrophoresis systems.
After 35 years, Danaher having acquired Beckman (now Beckman Coulter), transferred the CE group to become part of AB Sciex (2014).

Comments and Discussions

 
-- There are no messages in this forum --
| Advertise | Privacy | Mobile
Web04 | 2.8.140916.1 | Last Updated 18 Apr 2014
Article Copyright 2014 by Matt T Heffron
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid