一种算法，用于查找一个数字与特定数字集的所有加法组合

本文关键字：数字 组合 一个 算法 一种 用于 查找 | 更新日期: 2023-09-27 17:59:31

我有一个关于数字加法组合的问题。

例如，我有一个函数，它使用2个整数参数来查找给定参数的所有加法组合。

举例说明：

public List<List<int>> getcombinations(int numbercount, int target){
....
return List;
}

让我们通过虚构来确定论点：

numbercount=3 //it will be calculated with 3 integers
target=9 // final number to find

函数的输出应该是这样的：

{{1,1,7},{1,2,6},{1,3,5},{1,4,4},{2,2,5},{2,3,4},{3,3,3}}

当另外使用3个整数时，我们的目标数可以找到7种可能性。

再举一个例子：

numbercount=2
target=7
//Output should be like this:
{{1,6},{2,5},{3,4}} // 3 possibilities when 2 integers is used in addition.

我试图找到解决这个问题的办法。但我找不到解决问题的方法。你建议搜索或了解什么来解决它？

一种算法，用于查找一个数字与特定数字集的所有加法组合

这应该是一个起点，根据需要进行细化，阅读相关链接，了解有关生成组合的精彩解释。

 class Program
{
    static void Main(string[] args)
    {
        foreach (var set in GetCombinations(3, 9))
        {
            Console.WriteLine("{{{0}}}", string.Join(",", set));
        }
        Console.ReadKey();
    }

    public static IEnumerable<IEnumerable<int>> GetCombinations(int length, int targetSum)
    {
        var combinations = Enumerable.Range(1, length)
            .Select(x => Enumerable.Range(1, targetSum - length+1)).CartesianProduct();
        combinations=combinations
            .Where(x => x.Sum(y => y) == targetSum);
        return combinations.Distinct(new Comparer()).ToList();
    }
}
public class Comparer : IEqualityComparer<IEnumerable<int>>
{
    public bool Equals(IEnumerable<int> x, IEnumerable<int> y)
    {
        var isEqual= x.OrderBy(a => a).SequenceEqual(y.OrderBy(b => b));
        return isEqual;
    }
    public int GetHashCode(IEnumerable<int> obj)
    {
        return obj.Sum(); //lazy me, just indicate collection is same if their sum is same.
    }
}
public static class Extensions
{
   public static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences)
    {
        IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() };
        return sequences.Aggregate(
            emptyProduct,
            (accumulator, sequence) =>
                from accseq in accumulator
                from item in sequence
                select accseq.Concat(new[] { item }));
    }
}

组合生成的可拓方法是李珀特的一个著名代表作。

此代码明显更快：

using System;
using System.Collections.Generic;

namespace konsol
{
class Program
{
    private static List<List<int>> combinations = new List<List<int>>();
    private static void Main(string[] args)
    {
        int length = 4
        Generate(length , 10, 0, 1, 0, new int[length]);

        foreach (var varibles in combinations)
        {
            Console.WriteLine(String.Join(",", variables));
        }
        Console.ReadKey();
    }

    private static void Generate(int length, int target, int k, int last, int sum, int[] a)
    {
        if (k == length- 1)
        {
            a[k] = target - sum;
            combinations.Add(new List<int>(a));
        }
        else
        {
            for (int i = last; i < target - sum - i + 1; i++)
            {
                a[k] = i;
                Generate(length, target, k + 1, i, sum + i, a);
            }
        }
    }
}
}
相关文章：