找到所有的数字该款项到指定的目标数（整数分区） [英] Finding all numbers that sum to a specified target number (integer partition)

问题描述

的首先，我想说我还在学习，所以我的编程技巧不是很好，我愿意接受您有任何意见。
第二我还在学习英语，所以我想说的不便表示抱歉。的

好我的问题是这一点，我需要帮助提高我的算法或任何关于它的信息，我不知道这个搜索用什么词。

Well my problem is this, i need help improving my algorithm or any information about it, i don't know what words use for searching this.

该算法应该找到所有的该加数字的组合是等于给定的号码。例如：如果我有我的结果应该是6号：[1,5]，[2,4]，[2,2,2]，[3,3]

The algorithm is supposed to find all the combinations of numbers that added is equal to a given number. Example: if i have the number 6 my results are supposed to be: [1,5],[2,4],[2,2,2],[3,3]

我有以下内容：

public List<List<int>> discompose(int number)
    {
        List<List<int>> discomposedPairs = new List<List<int>>();
        if (number <= 3)
            return discomposedPairs;
        int[] numsForCombine = new int[number-1];
        for(int i = 1; i < number;i++){
            numsForCombine[i - 1] = i;
        }
        int ini = 0;
        int end = numsForCombine.Length - 1;
        while (ini <= end)
        {
            List<int> pair = new List<int>();
            pair.Add(numsForCombine[ini++]);
            pair.Add(numsForCombine[end--]);
            discomposedPairs.Add(pair);
        }
        return discomposedPairs;
    }
    public List<List<int>> discomposePair(List<int> pair)
    {
        List<List<int>> parDisc = new List<List<int>>();
        for (int i = 0; i < pair.Count; i++) {
            if (pair[i] > 3)
            {
                List<List<int>> disc = discomposeList(discompose(pair[i]));
                foreach (List<int> item in disc)
                {
                    if (i > 0)
                    {
                        var temp = pair.GetRange(0, i);
                        temp.AddRange(item);
                        parDisc.Add(temp);
                    } else {
                        item.AddRange(pair.GetRange(i+1, pair.Count-(i+1)));
                        parDisc.Add(item);
                    }
                }
            }
        }
        return parDisc;
    }
    public List<List<int>> discomposeList(List<List<int>> list)
    {
        List<List<int>> mainDiscomposedList = new List<List<int>>();
        for (int i = 0; i < list.Count; i++)
        {
            mainDiscomposedList.Add(list[i]);
           List<List<int>> discomposedSubset = discomposePair(list[i]);
            foreach(List<int> item in discomposedSubset){
                mainDiscomposedList.Add(item);
            }
        }
        return mainDiscomposedList;
    }

descompose在加入对给定数量的第一种方法是相等的数目给定。
第二和第三种方法是它们是递归的，并有bucles所以他们没有任何出色的表现最丑陋的。两者之间产生与数字的列表作为我的问题，而是说有一些不便之处：
1）不要有良好的表现
2）给出了大量的重复序列这里
是输出为10号

The first method descompose the number given in pairs that added are equal the number given. The second and the third method are the ugliest they are recursive and have bucles so they don't have any good performance. Between the two generates a List with numbers as i the problem says but there are a few inconvenients: 1) Don't have good performance 2) Gives a lot of repetitive sequences here is the output for the number 10

[2,8,]
[2,2,6,]
[2,2,2,4,]
[2,2,2,2,2,]
[2,2,3,3,]
[2,3,5,]
[2,3,2,3,]<-------------repeated
[2,4,4,]
[2,2,2,4,]<-------------repeated
[2,4,2,2,]<-------------repeated
[3,7,]
[3,2,5,]<-------------repeated
[3,2,2,3,]<-------------repeated
[3,3,4,]
[3,3,2,2,]
[4,6,]
[2,2,6,]<-------------repeated
[4,2,4,]<-------------repeated
[4,2,2,2,]<-------------repeated
[4,3,3,]<-------------repeated
[5,5,]
[2,3,5,]<-------------repeated
[5,2,3,]<-------------repeated

最后我想提高性能，并有可能少重复的项目是一个重复的项目[1,1,3]，[1,3， 1]，[3,1,1]
[这里是整个项目的链接] 1

Finally i want to improve the performance and have the less possible repeated items being a repeated item [1,1,3], [1,3,1], [3,1,1] [Here is the full project link]1

推荐答案

这里有一个方法，首先构建组合成一个树状结构，然后安排他们进入名单 INT 取值：

Here's one approach that first builds the combinations into a tree structure, then arranges them into lists of ints:

internal class Combination
{
    internal int Num;
    internal IEnumerable<Combination> Combinations;
}

internal static IEnumerable<Combination> GetCombinationTrees(int num, int max)
{
    return Enumerable.Range(1, num)
                     .Where(n => n <= max)
                     .Select(n =>
                         new Combination
                         {
                             Num = n,
                             Combinations = GetCombinationTrees(num - n, n)
                         });
}

internal static IEnumerable<IEnumerable<int>> BuildCombinations(
                                               IEnumerable<Combination> combinations)
{
    if (combinations.Count() == 0)
    {
        return new[] { new int[0] };
    }
    else
    {
        return combinations.SelectMany(c =>
                              BuildCombinations(c.Combinations)
                                   .Select(l => new[] { c.Num }.Concat(l))
                            );
    }
}

public static IEnumerable<IEnumerable<int>> GetCombinations(int num)
{
    var combinationsList = GetCombinationTrees(num, num);

    return BuildCombinations(combinationsList);
}

public static void PrintCombinations(int num)
{
    var allCombinations = GetCombinations(num);
    foreach (var c in allCombinations)
    {
        Console.WriteLine(string.Join(", ", c));
    }
}

在与输入值运行 6 ，这将产生：

When run with the input value 6, this produces:

1, 1, 1, 1, 1, 1
2, 1, 1, 1, 1
2, 2, 1, 1
2, 2, 2
3, 1, 1, 1
3, 2, 1
3, 3
4, 1, 1
4, 2
5, 1
6

这篇关于找到所有的数字该款项到指定的目标数（整数分区）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！