c# - 如何制作相等的整数子集？

Question

假设我有一个数组如下

array[] = {14,10,20,4}

该数组可以分为子集 {14,10} 和 {20,4}，因为这两个具有相等的和。

另一个例子可能是

array[] = {5, 5, 15, 5}

该数组可以分为子集 {5,5,5} 和 {15}，因为这两个具有相等的和。

但

array[] = {1, 5, 30}

不能分成相等的集合，因为它们永远不可能相等。

我们怎么能这样做？

我的镜头

var result = string.Empty;
int highestNumber = input1[0];
int sum = 0;
string set = string.Empty;

foreach (int value in input1) 
    if (value > highestNumber) highestNumber = value;

for (int i = 0; i < input1.Length; i++)
{
    var elements = input1[i];
    if (elements > 0)
    {
        if (elements != highestNumber)
        {
            sum += elements;
            set += "," + elements; 
        }
    }
}

if (sum == highestNumber)
    result = "Yes it can be partitioned" 
else
    result = "No it cannot be";

Console.WriteLine(result);

它不适用于第一个。

这个程序怎么做？

score 4 · Accepted Answer

您希望将给定的 int 数组划分为 2 个分区，其中分区的总和相等。

该方法可以是：

查看所有项目的总和是否可以被2整除（否则无法分区）
获取数组的所有子集
找到总和为 [所有项目的总和] / 2 的子集

这是代码：

class Program
{
    static void Main(string[] args)
    {
        var arrays = new int[][] {
            new[]{ 1, 12, 10, 2, 23 },
            new[] {14,10,20,4},
            new[] {5, 5, 15, 5},
            new[] {1, 5, 30}
        };

        foreach (var array in arrays)
        {
            Console.WriteLine(String.Format("Results for {0}:", string.Join(",", array)));
            IEnumerable<IEnumerable<int>> partitions = Partition(array);
            if (!partitions.Any()) 
                Console.WriteLine("Cannot be partitioned.");
            else
                foreach (var item in partitions)
                {
                    Console.WriteLine(string.Join(",", item));
                }
            Console.WriteLine();
        }

        Console.ReadKey();
    }

    static IEnumerable<IEnumerable<int>> Partition(int[] array)
    {
        var sum = array.Sum();
        if ((sum % 2) == 1) return Enumerable.Empty<IEnumerable<int>>();

        return Subsequences(array).Where(ss => ss.Sum(item => item) == (sum / 2));
    }

    // http://stackoverflow.com/a/3750709/201088
    private static IEnumerable<IEnumerable<T>> Subsequences<T>(IEnumerable<T> source)
    {
        if (source.Any())
        {
            foreach (var comb in Subsequences(source.Skip(1)))
            {
                yield return comb;
                yield return source.Take(1).Concat(comb);
            }
        }
        else
        {
            yield return Enumerable.Empty<T>();
        }
    }
}

输出：

Results for 1,12,10,2,23:
12,10,2
1,23

Results for 14,10,20,4:
14,10
20,4

Results for 5,5,15,5:
15
5,5,5

Results for 1,5,30:
Cannot be partitioned.

score 1 · Accepted Answer

我在 C# 中创建了一个基于位数组（bitset）的解决方案bool[]。在我展示解决方案之前，我首先必须向 this 添加一些扩展方法bool[]。这些是通用功能，可用于其他解决方案。它位于此答案的底部。

正如我所说，它基于位集。bitset 将具有需要分组的数字数组的长度。bitset 将用 0 和 1 填充。每个位对应一个数字。因此，如果数字数组有 5 个元素，则 bitset 也将有 5 位。

如果有一点0，数字将被放置在group0. 如果位是1，数字将被放入group1。当两组的总和相同时，工作就完成了。

重复此循环，直到分析完所有组合。bitset 将从数值 op 1 开始（如果是 5 个数字：00001）。它将增加每次迭代（因此下一次迭代将是00010，然后00011，然后00100等）因此更改位集的位并重新组合数字。

请注意：我创建此方法时只考虑其功能。我不介意任何性能问题。当然，这个例程可以做得更快（即不是每次迭代都创建新列表等），但这会降低代码的可读性。我试图使这段代码尽可能地可读。

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

    bool[] groupPerNumber = new bool[](numbers.Count);
    while (true)
    {
        groupPerNumber.Increase(); // Increate the numberic value of the array of bits.
        if (groupPerNumber.IsEmpty()) // If all bits are zero, all iterations have been done.
            break;

        // Create the new groups.
        group0 = new List<int>();
        group1 = new List<int>();

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

        // If both sums are equal, exit.
        if (group0.Sum() == group1.Sum())
            return true;
    }
    group0 = group1 = null;
    return false;
}

布尔扩展数组

static public class BoolArrayExtensions
{
    /// <summary>
    /// Treats the bits as a number (like Int32) and increases it with one.
    /// </summary>
    static public void Increase(this bool[] 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 bool[] 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 bool[] bits)
    {
        for (int i = 0; i < bits.Length; i++)
            if (bits[i])
                return false;
        return true;
    }
}

编辑

我创建了另一个这样的解决方案并将其放在 codereview 中。它的功能基本相同，但这次优化了表单速度。感兴趣的？看看：https ://codereview.stackexchange.com/questions/25980/performance-devide-group-of-numbers-into-two-groups-of-which-the-sums-are-equal

score 0 · Accepted Answer

计算数组的总和并将其除以二。现在您知道了您的集合所需的规范（总和值）。

根据您的性能要求和预期大小，您可以使用简单的回溯算法来了解所有可能性。由于您知道集合必须具有的确切总和，因此您可以显着限制搜索。

score -1 · Accepted Answer

首先，您可以从获取列表中项目组合的方法开始。这最容易通过创建数字组合然后将其从数字转换为集合的索引来解决：

public static IEnumerable<IEnumerable<T>> Combinations<T>(this IList<T> source, int n)
{
    return Combinations(source.Count, n)
        .Select(combination => combination.Select(i => source[i]));
}

public static IEnumerable<IEnumerable<int>> Combinations(int n, int p)
{
    //this is logically treated as a stack except that when enumerated it's enumerated as the 
    //reverse of a stack, which is desirable.  There is no efficient way to get the reverse iterator
    //of System.Collections.Stack so easily.  All mutations are to the end of the list.
    var stack = Enumerable.Range(0, p).ToList();

    while (stack[stack.Count - 1] < n)
    {
        //the ToList can be removed if previous sub-sequences won't be iterated 
        //after the outer sequence moves to the next item.
        yield return stack.ToList();
        int lastValue = stack.Pop();

        while (stack.Any() && lastValue + 1 > n - (p - stack.Count))
        {
            lastValue = stack.Pop();
        }

        while (stack.Count < p)
        {
            lastValue += 1;
            stack.Add(lastValue);
        }
    }
}

//simple helper method to get & remove last item from a list
public static T Pop<T>(this List<T> list)
{
    T output = list[list.Count - 1];
    list.RemoveAt(list.Count - 1);
    return output;
}

使用它创建一个获取集合的所有组合的方法是一件简单的事情，而不仅仅是特定大小的组合：

public static IEnumerable<IEnumerable<T>> AllCombinations<T>(this IList<T> source)
{
    IEnumerable<IEnumerable<T>> output = Enumerable.Empty<IEnumerable<T>>();
    for (int i = 1; i < source.Count; i++)
    {
        output = output.Concat(Combinations(source, i));
    }
    return output;
}

现在我们能够获取列表的所有组合，我们可以使用 LINQ 来完成这项工作：

List<int> list = new List<int>() { 5, 5, 15, 5 };

var groups = list.AllCombinations()
    .GroupBy(combination => combination.Sum());

使用它，您现在拥有总和相同值的所有组合组。

c# - 如何制作相等的整数子集？

4 回答 4

Related

Reference