Divide group of numbers into two groups of which the sums are equal

Question

I have a piece of code that divides a group of numbers into two groups of numbers of which the sums are equal.

I created this because of a Stack Overflow question:

For example:

• {10,15,20,5} will result in: {10,15} + {20,5}
• {1,2,3,4} will result in: {1,4} + {2,3}
• {5,5,5,15} will result in: {5,5,5} + {15}
• {5, 6} will fail.

This is the code:

static public bool Partition(IList<int> numbers, out IList<int> group0, out IList<int> group1)
{
    if (numbers == null)
        throw new ArgumentNullException("numbers");
    group0 = group1 = null;
    if (numbers.Count <= 1)
        return false;

    int totalSum = numbers.Sum();
    if (totalSum % 2 != 0)
        return false;
    int desiredSum = totalSum / 2;

    BitArray groupPerNumber = new BitArray(numbers.Count);
    while (true)
    {
        groupPerNumber.Increase(); // Increate the numberic value of the BitArray.
        if (groupPerNumber.IsEmpty()) // If all bits are zero, all iterations have been done.
            return false;

        // Fill the groups. The bit in the groups-array determines in which group a number will be place.
        int sumGroup1 = 0;
        for (int index = 0; index < numbers.Count; index++)
        {
            int number = numbers[index];
            if (groupPerNumber[index])
                sumGroup1 += number;
        }

        // If both sums are equal, exit.
        if (sumGroup1 == desiredSum)
        {
            group0 = new List<int>();
            group1 = new List<int>();
            for (int index = 0; index < numbers.Count; index++)
            {
                int number = numbers[index];
                if (!groupPerNumber[index])
                    group0.Add(number);
                else
                    group1.Add(number);
            }
            return true;
        }
    }
}

I created some supporting extension methods:

static public class BitSetExtensions
{
    /// <summary>
    /// Treats the bits as a number (like Int32) and increases it with one.
    /// </summary>
    static public void Increase(this BitArray bits)
    {
        for (int i = 0; i < bits.Length; i++)
        {
            if (!bits[i])
            {
                bits[i] = true;
                bits.SetAll(0, i - 1, false);
                return;
            }
            bits[i] = false;
        }
        bits.SetAll(false);
    }

    /// <summary>
    /// Sets the subset of bits from the start position till length with the given value.
    /// </summary>
    static public void SetAll(this BitArray bits, int start, int length, bool value)
    {
        while (length-- > 0)
            bits[start++] = value;
    }

    /// <summary>
    /// Returns true if all bits in the collection are false.
    /// </summary>
    static public bool IsEmpty(this BitArray bits)
    {
        for (int i = 0; i < bits.Length; i++)
            if (bits[i])
                return false;
        return true;
    }
}

Criteria:

• The group of numbers must have any size.
• Only two sets have to be found.
• The order of the numbers may be mixed up. So sorting is allowed.
• The numbers must be greater than 0.

The real question is: How can this code be made any faster?

Results so far:

Original posting (by myself):       3.657.559 ticks = factor   1.0 (baseline)
All combined trics (answer of myself):  8.563 ticks = factor 427.1
Code of Ivan:                          12.969 ticks = factor 282,0
Code of Stephen:                       34.415 ticks = factor 106,3
Code of Jesse:                      1.743.905 ticks = factor   2,097
Code of Eren:                      16.108.289 ticks = factor   0,2270
Code of Servy:                    225.239.100 ticks = factor   0,01623
Code of Bobson:                49.663.859.000 ticks = factor   0,000074

Things I have learned so far:

• Try to avoid interfaces if you have access to the real class. So int[] is faster than IList<int>.
• Try to avoid complex structures in you have a basic structure. So bool[] is faster than BitArray.
• Try to avoid any memory operations (like new).
• Try to avoid foreach. Use for. Every time you use foreach an IEnumerator is created, resulting in a memory operation.
• Try to avoid LINQ. LINQ is based on already existing methods. It is just one extra call. Further it relies on IEnumerable, which will create an IEnumerable at every call, resulting in a memory operation.
• My original code analyzed ALL combinations. The early out algorithm in my second posting saved me a lot of time.
• Skip on iteration by using the first number as a starting sum, instread of 0.
• Use for-loops counting back to 0.

The test

I use a few arrays of numbers:

    var arrays = new int[][] 
    {
        new[]{ 1, 12, 10, 2, 23 },
        new[] {14,10,20,4},
        new[] {5, 5, 15, 5},
        new[] {1, 5, 30}, // Will fail.
        new[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, // Will fail.
        new[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16},
    };

The time of a Partion-function is measured as follows:

Stopwatch st0 = Stopwatch.StartNew();
for (int i = iterations - 1; i >= 0; i--)
    for (int n = arrays.Length - 1; n >= 0; n--)
        if (PartitionOriginal(arrays[n], out list0, out list1))
            sum = list0.Sum() + list1.Sum();
st0.Stop();

The value iterations is a constant, by default set with 1000. If the partition succeeds, the first result result set (some functions return more than one result set) are summed. The reason behind this summing is to ensure that all search work is done. Sometimes when an IEnumerable is returned, code (using yield return) still needs to be executed.

Answer 1

The main idea is to find a biggest element, place it in the first bin and start recursion from the second element saving lots of tree spanning.

UPDATED CODE

Main Method

public static class ASolution
{
    public static bool TryPartitionBySum(int[] values, out int[] fstBin, out int[] scndBin)
    {
        #region Part I

        if (values == null)
            throw new ArgumentNullException("values");

        fstBin = scndBin = null;

        if (values.Length <= 1)
            return false;

        int totalSum = 0;
        int maxIdx = -1;
        int maxVal = -1;
        for (int i = 0; i < values.Length; i++)
        {
            int tmp = values[i];
            if (tmp <= 0)
                throw new ArgumentException("Numbers is not allowed to contain values less than one.");
            if (tmp > maxVal)
            {
                maxVal = tmp;
                maxIdx = i;
            }
            totalSum += tmp;
        }

        #endregion

        if (totalSum % 2 != 0)
            return false;

        //  Put max val at the first place
        values[maxIdx] = values[0];
        values[0] = maxVal;

        var activeIdx = new bool[values.Length];
        activeIdx[0] = true;
        int targetSum = totalSum / 2 - maxVal;

        if (targetSum < 0)
            return false;

        bool isSuccess = targetSum == 0 || RecursiveTryPartition(values, activeIdx, 1, targetSum);

        #region PART III

        if (isSuccess)
        {
            int fstBinIdx = 0, scndBinIdx = 0;
            int size = 0;

            for (int i = 0; i < activeIdx.Length; i++)
            {
                if (activeIdx[i])
                    size++;
            }
            fstBin = new int[size];
            scndBin = new int[activeIdx.Length - size];

            for (int i = 0; i < activeIdx.Length; i++)
            {
                if (activeIdx[i])
                    fstBin[fstBinIdx++] = values[i];
                else
                    scndBin[scndBinIdx++] = values[i];
            }
        }

        #endregion

        return isSuccess;
    }

    private static bool RecursiveTryPartition(int[] numbers, bool[] isActive, int headIdx, int sumLeft)
    {
        if (headIdx == numbers.Length)
            return false;

        int currVal = numbers[headIdx];
        isActive[headIdx] = true;

        if (currVal < sumLeft && RecursiveTryPartition(numbers, isActive, headIdx + 1, sumLeft - currVal))
            return true;

        if (currVal == sumLeft)
            return true;

        isActive[headIdx] = false;
        return RecursiveTryPartition(numbers, isActive, headIdx + 1, sumLeft);
    }
}

TEST ITEM

Unfortunately you need to plug-in your method to which defines whether a sequence is partitionable.

public class TestCase
{
    private const string Delim = ",";
    public int ExperimentsCount { get { return Values.Length; } }
    public int VectorSize { get { return Values[0].Length; } }
    public int PartitionableCount { get; private set; }

    private int[][] Values { get; set; }

    private TestCase() { }

    public IEnumerable<int[]> TestSample
    {
        get
        {
            return Values.Select(f => f.ToArray());
        }
    }

    public void ToFile(string path)
    {
        System.IO.File.WriteAllText(path, PartitionableCount + "\n");
        System.IO.File.AppendAllLines(path, Values.Select(f => string.Join(Delim, f)));
    }

    public TestCase Read(string path)
    {
        var lines = System.IO.File.ReadAllLines(path);
        return new TestCase
        {
            PartitionableCount = int.Parse(lines[0]),
            Values = lines.Skip(1)
                          .Select(line => line.Split(Delim[0])
                                              .Select(int.Parse)
                                              .ToArray())
                          .ToArray()
        };
    }

    public static TestCase CreateSample(int experimentsCount, int vectorSize, double targetedSuccessRate
                                        , Func<int[], bool> isPartitionable)
    {
        if (targetedSuccessRate < 0 || targetedSuccessRate > 1)
            throw new ArgumentException("Success rate must be a percentage value", "targetedSuccessRate");
        if (experimentsCount < 0)
            throw new ArgumentException("Experiments count must be a positive number");
        if (vectorSize < 5)
            throw new ArgumentException("Vector size should be at least 5");

        var rnd = new Random();
        var tmp = new TestCase
        {
            Values = new int[experimentsCount][],
            PartitionableCount = (int)(targetedSuccessRate * experimentsCount)
        };

        var successTriesLeft = tmp.PartitionableCount;

        int successIdx = experimentsCount - successTriesLeft;
        int failIdx = successIdx - 1;

        while (successIdx < experimentsCount || failIdx >= 0)
        {
            var vec = Enumerable.Range(0, vectorSize)
                                .Select(_ => rnd.Next(1, vectorSize * 3))
                                .ToArray();

            if (isPartitionable(vec))
            {
                if (successIdx < experimentsCount)
                {
                    tmp.Values[successIdx++] = vec;
                }
            }
            else
            {
                if (failIdx >= 0)
                {
                    tmp.Values[failIdx--] = vec;
                }
            }
        }
        return tmp;
    }

}

TEST RUNNER

public static class TestRunner
{
    public delegate bool Partitioner(int[] values, out int[] fstBin, out int[] scndBin);

    public static long RunTest(TestCase testData, Partitioner function)
    {
        var vals = testData.TestSample.ToArray();
        var sw = System.Diagnostics.Stopwatch.StartNew();
        int count = 0;
        foreach (var vector in vals)
        {
            int[] fstBin, sndBin;
            if (function(vector, out fstBin, out sndBin))
            {
                count++;
                //System.Diagnostics.Trace.Assert(fstBin.Sum() == sndBin.Sum());
            }
        }
        sw.Stop();

        //System.Diagnostics.Trace.Assert(count == testData.PartitionableCount);
        return sw.ElapsedTicks; 
    }
}

SAMPLE OF CODE USAGE

        var iterCount = 10000;
        var vectorSizes = new[] { 5, 10, 25, 50};
        var successRate = new[] { 0, 0.2, 0.5, 0.8, 1.0};

        var testList = vectorSizes.SelectMany(v => 
            successRate.Select(r => new { VectorSize = v, SuccessRate = r }));

        Console.WriteLine("{0,-10}{1,-10}{2,10}{3,10}", "Rate,%", "Size", "M sol", "I sol");
        foreach (var item in testList)
        {
            int[] a, b;
            var tmp = TestCase.CreateSample(iterCount, item.VectorSize, 
                item.SuccessRate, vals => Mulders.Partition(vals, out a, out b));
            //var tmp = TestCase.Read("MySavedCase.csv");
            Console.WriteLine("{0,-10:P}{1,-10}{2,10:N0}{3,10:N0}",
                (double)tmp.PartitionableCount / tmp.ExperimentsCount,
                tmp.VectorSize,
                TestRunner.RunTest(tmp, Mulders.Partition),
                TestRunner.RunTest(tmp, ASolution.TryPartitionBySum));
        }

Hope it'll help to run some tests for all solutions.

Answer 2

Here's some stuff I did to increase the performance. If there's any parts that you'd like explained fuller, let me know and I will.

    private static readonly IList<int> emptyList = Enumerable.Empty<int>().ToList();

    public static bool Partition(IList<int> numbers, out IList<int> group0, out IList<int> group1)
    {
        if (numbers == null)
        {
            throw new ArgumentNullException("numbers");
        }

        if (numbers.Count <= 1)
        {
            group0 = group1 = emptyList;
            return false;
        }

        var totalSum = numbers.Sum();

        if (totalSum % 2 != 0)
        {
            group0 = group1 = emptyList;
            return false;
        }

        var desiredSum = totalSum / 2;
        var groupPerNumber = Enumerable.Repeat(false, numbers.Count).ToList();
        Func<bool, bool> bitOff = BitOff;
        Func<int, int, bool> whereBitsOn = new WhereBitsOnContainer(groupPerNumber).WhereBitsOn;

        do
        {
            groupPerNumber.Increase(); // Increase the numeric value of the BitArray.

            if (!groupPerNumber.All(bitOff))
            {
                continue;
            }

            // If all bits are zero, all iterations have been done.
            group0 = group1 = emptyList;
            return false;
        }
        while (numbers.Where(whereBitsOn).Sum() != desiredSum); // If both sums are equal, exit.

        // Fill the groups. The bit in the groups-array determines in which group a number will be place.
        var balancedSizeGuess = numbers.Count / 2;

        group0 = new List<int>(balancedSizeGuess);
        group1 = new List<int>(balancedSizeGuess);
        for (var index = 0; index < numbers.Count; index++)
        {
            (groupPerNumber[index] ? group1 : group0).Add(numbers[index]);
        }

        return true;
    }

    private static bool BitOff(bool bit)
    {
        return !bit;
    }

    private sealed class WhereBitsOnContainer
    {
        private readonly IList<bool> groupPerNumber;

        public WhereBitsOnContainer(IList<bool> groupPerNumber)
        {
            this.groupPerNumber = groupPerNumber;
        }

        public bool WhereBitsOn(int number, int index)
        {
            return this.groupPerNumber[index];
        }
    }
}

public static class BitSetExtensions
{
    /// <summary>
    /// Treats the bits as a number (like Int32) and increases it with one.
    /// </summary>
    public static void Increase(this IList<bool> bits)
    {
        for (var i = 0; i < bits.Count; i++)
        {
            if (!bits[i])
            {
                bits[i] = true;
                bits.SetAllFalse(i);
                return;
            }

            bits[i] = false;
        }

        bits.SetAllFalse(bits.Count);
    }

    /// <summary>
    /// Sets the subset of bits from the start position till length to false.
    /// </summary>
    private static void SetAllFalse(this IList<bool> bits, int length)
    {
        var start = 0;

        while (--length > 0)
        {
            bits[start++] = false;
        }
    }
}

Answer 3

I realize this isn't necessarily faster, but it will be much easier to maintain, and at least one example ought to be posted using LINQ.

So here's that example, using LINQ and the Combinatorics library to do it in a single statement, and in a more object-oriented manner*:

public IEnumerable<Group> Partition(IList<int> list)
{
    var results = new Permutations<int>(list)
                      .SelectMany(x => Enumerable.Range(1, list.Count() -1)
                                                 .Select(y => new Group{ 
                                                        Left = x.Take(y), 
                                                        Right = x.Skip(y)
                                                    }))
                      .Where(x => x.Left.Sum() == x.Right.Sum())
                      .Distinct();

    return results;
}

And here's the Group class I used:

class Group
{
    public IEnumerable<int> Left { get; set;}
    public IEnumerable<int> Right { get; set;}

    public override bool Equals(object b) {
        if (!(b is Group)) return false;
        var a1 = this.Left.OrderBy(x => x);
        var a2 = this.Right.OrderBy(x => x);
        var b1 = ((Group)b).Left.OrderBy(x => x);
        var b2 = ((Group)b).Right.OrderBy(x => x);
        return ((a1.SequenceEqual(b1) && a2.SequenceEqual(b2))
            || (a1.SequenceEqual(b2) && a2.SequenceEqual(b1)));
    }

    public override int GetHashCode() {
        return this.Left.OrderBy(x => x).Concat(this.Right.OrderBy(x => x))
                .Aggregate(0, (h, v) => h ^ v.GetHashCode());
    }

}

---

* Each grouping of numbers is an instance of a Group object, and we test if two Groups are equal based on the items in each Group.

Answer 4

I wanted to keep this a simple as possible, not creating any extra method calls if I did not have too.

I wanted to traverse the list in desending order. I wanted to fit the larger items into the the lists first. Then fill in with the smaller values.

I am using Linq for the order by, but could just have easily used the sort option and traversed the list from the last index to the first. (still might do that).

  static public bool Partition(IList<int> numbers, out IList<int> group0, out IList<int> group1)
  {
    if (numbers == null)
    {
      throw new ArgumentException("numbers");
    }

    group0 = null;
    group1 = null;

    var totalSum = numbers.Sum();
    if (totalSum % 2 == 1)
    {
      return false;
    }

    var listSum = totalSum / 2;

    var sorted = numbers.OrderByDescending(i => i).ToList();

    var group0Sum = 0;
    var rejects = new Stack<int>();
    var holder = new Stack<int>();        
    var tries = 0;
    var index = 0;

    group0 = new List<int>();
    rejects.Push(int.MaxValue);

    while (sorted.Count > 0)
    {
      if (sorted[index] < rejects.Peek() && group0Sum + sorted[index] <= listSum)
      {
        group0Sum += sorted[index];
        holder.Push(sorted[index]);
        sorted.RemoveAt(index);
      }

      if(group0Sum == listSum)
      {
        group0 = new List<int>(holder);
        group1 = new List<int>(sorted);
        return true;
      }

      index++;

      if(index >= sorted.Count && sorted.Count > 0)
      {
        index = ++tries;

        if (index >= sorted.Count)
        {
          return false;
        }

        while (holder.Count > tries)
        {
          group0Sum -= holder.Peek();
          rejects.Push(holder.Peek());
          sorted.Insert(0, holder.Pop());
        }
      }          
    }

    return false;
  }

Answer 5

This is a revised solution. It is way faster than my original posting. I replace the BitArray by a bool[] which had a little performance boost (hinted by Jesse). Also, I used recursion with an early out algorithm.

static public bool Partition(int[] numbers, out int[] group0, out int[] group1)
{
    if (numbers == null)
        throw new ArgumentNullException("numbers");
    group0 = group1 = null;

    if (numbers.Length <= 1)
        return false;

    int totalSum = 0;
    for (int i = 0; i < numbers.Length; i++)
    {
        int n = numbers[i];
        if (n <= 0)
            throw new ArgumentException("Numbers is not allowed to contain values less than one.");
        totalSum += n;
    }
    if (totalSum % 2 != 0)
        return false;
    int desiredSum = totalSum / 2;

    bool[] groupPerNumber = new bool[numbers.Length];

    if (!AnalyzeCombination(numbers, groupPerNumber, 0, 0, desiredSum))
        return false;

    int groupSize0 = 0;
    for (int i = 0; i < groupPerNumber.Length; i++)
        if (!groupPerNumber[i])
            groupSize0++;
    group0 = new int[groupSize0];
    group1 = new int[numbers.Length - groupSize0];

    int groupIndex0 = 0;
    int groupIndex1 = 0;
    for (int i = 0; i < numbers.Length; i++)
        if (!groupPerNumber[i])
            group0[groupIndex0++] = numbers[i];
        else
            group1[groupIndex1++] = numbers[i];
    return true;
}

static public bool AnalyzeCombination(int[] numbers, bool[] groupPerNumber, int position, int runningSum, int desiredSum)
{
    if (position == numbers.Length)
        return false;

    int currentNumber = numbers[position];
    runningSum += currentNumber;
    if (runningSum < desiredSum)
    {
        groupPerNumber[position] = true;
        if (AnalyzeCombination(numbers, groupPerNumber, position + 1, runningSum, desiredSum))
            return true;
        runningSum -= currentNumber;
        groupPerNumber[position] = false;
    }
    else if (runningSum == desiredSum)
    {
        groupPerNumber[position] = true;
        return true;
    }
    if (AnalyzeCombination(numbers, groupPerNumber, position + 1, runningSum, desiredSum))
        return true;

    return false;
}

Answer 6

You make it faster using a faster algorithm.

If the total is 2N, then you need a set of integers adding up to N. With dynamic programming, you check which sizes sets of the first k integers can produce. In your example, 10, 15, 20, 5 with N = 25, using or not using the first number 10 gives you set sizes 0 or 10. Adding or not adding 15 gives you set sizes 0, 10, 15, and 25. A solution is already found.

You need storage proportional to N. And each of k numbers is combined with existing set sizes from 0 to N, so this runs in k * N operations. There are 2^k subsets, testing them all would take at least 2^k operations. This is slower if N is not too large, for example 50 numbers up to a million is no big deal using dynamic programming, but very hard with recursion.

It doesn't work well if you have 10 numbers up to a billion each, so you need to look at your input first, then decide what method to use.

And you get a fast algorithm by implementing something, figuring out when and why it is slow, and modifying the algorithm to make it faster. If you have many numbers that are quite large, you might be able to show that you can produce any total l ≤ total ≤ r using the first k numbers. If the next large number is x, and l + x ≤ r + 1 then you can produce any l ≤ total ≤ r + x using the first k+1 numbers with constant effort. This solves the test case of all numbers from 1 to 16, or all numbers from 1 to a million, in a trivial way. It allows you to solve "split the first k primes for odd k into two sets with equal sum" for k = 1,000,001 quite easily.

How does it split the sum of the first k integers? Sort the numbers. For k = 1, 2, 5, 6, 9, 10, 13, 14 etc. the sum is odd so the numbers cannot be split into equal halves.

Using the number 1 we can have sums 0 to 1. Adding or not adding 2, we can have any sum from 0 to 3. Adding or not adding 3 produces 0 to 6, adding or not adding 4 produces 0 to 10 and so on. For k = 16 the sum is k(k+1)/2 = 8*17 = 136, half of that is 78 which happens to be the sum of 0 to 12. So one subset is the integers from 1 to 12.