Trouver tous les nombres dont la somme est égale à un nombre cible spécifié (partition en nombres entiers)

Question

Tout d'abord, je voudrais dire que je suis encore en train d'apprendre et que mes compétences en programmation ne sont pas très bonnes, et que je suis prêt à accepter tous les conseils que vous pourriez me donner. Deuxièmement, je suis encore en train d'apprendre l'anglais et je tiens à m'excuser pour la gêne occasionnée.

Bien Mon problème est le suivant J'ai besoin d'aide pour améliorer mon algorithme ou d'informations à ce sujet, je ne sais pas quels mots utiliser pour la recherche.

L'algorithme est censé trouver toutes les combinaisons de nombres dont la somme est égale à un nombre donné. Exemple : si j'ai le nombre 6, mes résultats sont censés être : [1,5],[2,4],[2,2,2],[3,3]

J'ai les éléments suivants :

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;
    }

La première méthode consiste à décomposer le nombre donné en paires dont l'addition est égale au nombre donné. La deuxième et la troisième méthode sont les plus laides, elles sont récursives et ont des bucles, elles ne sont donc pas très performantes. Entre les deux, une liste de nombres est générée, comme le dit le problème, mais il y a quelques inconvénients : 1) Les performances ne sont pas bonnes 2) Donne beaucoup de séquences répétitives voici le résultat pour le nombre 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

Enfin, je souhaite améliorer les performances et avoir le moins possible d'éléments répétés, à savoir un élément répété [1,1,3], [1,3,1], [3,1,1] [Voici le lien vers le projet complet]. 1

Answer 1

Voici une approche qui consiste d'abord à construire les combinaisons dans une structure arborescente, puis à les classer dans des listes de int s :

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));
    }
}

Lorsqu'il est exécuté avec la valeur d'entrée 6 Cela produit :

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