patterncsharpMinor
Divide group of numbers into two groups of which the sums are equal
Viewed 0 times
dividegroupsthegroupareintonumbersequaltwosums
Problem
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:
This is the code:
I created some supporting extension methods:
Criteria:
The real question is: How can this code be made any faster?
Re
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 numbers, out IList group0, out IList group1)
{
if (numbers == null)
throw new ArgumentNullException("numbers");
group0 = group1 = null;
if (numbers.Count ();
group1 = new List();
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
{
///
/// Treats the bits as a number (like Int32) and increases it with one.
///
static public void Increase(this BitArray bits)
{
for (int i = 0; i
/// Sets the subset of bits from the start position till length with the given value.
///
static public void SetAll(this BitArray bits, int start, int length, bool value)
{
while (length-- > 0)
bits[start++] = value;
}
///
/// Returns true if all bits in the collection are false.
///
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?
Re
Solution
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 emptyList = Enumerable.Empty().ToList();
public static bool Partition(IList numbers, out IList group0, out IList group1)
{
if (numbers == null)
{
throw new ArgumentNullException("numbers");
}
if (numbers.Count bitOff = BitOff;
Func 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(balancedSizeGuess);
group1 = new List(balancedSizeGuess);
for (var index = 0; index groupPerNumber;
public WhereBitsOnContainer(IList groupPerNumber)
{
this.groupPerNumber = groupPerNumber;
}
public bool WhereBitsOn(int number, int index)
{
return this.groupPerNumber[index];
}
}
}
public static class BitSetExtensions
{
///
/// Treats the bits as a number (like Int32) and increases it with one.
///
public static void Increase(this IList bits)
{
for (var i = 0; i
/// Sets the subset of bits from the start position till length to false.
///
private static void SetAllFalse(this IList bits, int length)
{
var start = 0;
while (--length > 0)
{
bits[start++] = false;
}
}
}Code Snippets
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;
}
}
}Context
StackExchange Code Review Q#25980, answer score: 2
Revisions (0)
No revisions yet.