2

首先我想说我还在学习所以我的编程技能不是很好，我愿意接受你的任何建议。其次，我还在学习英语，所以我想对给您带来的不便表示歉意。

那么我的问题是这个，我需要帮助改进我的算法或任何关于它的信息，我不知道用什么词来搜索这个。

该算法应该找到添加等于给定数字的所有数字组合。示例：如果我有数字 6，我的结果应该是：[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;
    }

第一种方法分解成对给出的数字，相加等于给定的数字。第二种和第三种方法是最丑陋的，它们是递归的并且有 bucles，所以它们没有任何好的性能。正如问题所说，两者之间会生成一个带有数字的列表，但有一些不便之处：1）性能不佳 2）给出了很多重复序列这里是数字 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

4

1 回答 1

6

这是一种方法，它首先将组合构建成树结构，然后将它们排列到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，这会产生：

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
于 2013-02-24T04:39:28.437 回答