12,635,816 members (25,184 online)
Alternative Tip/Trick
alternative version

5.1K views
6 bookmarked
Posted

Subset - Sum Problem with Numeric Collections

, 17 Apr 2014 CPOL
 Rate this:
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())));
}
}

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;
}
}
}
}
}```

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

Share

 Software Developer (Senior) Sciex 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 Sciex (2014).