Блог

Вот что я имею в виду. Предположим S = {1, 4} , и N = 5 . Упорядоченные расположения элементов в наборе S будут выглядеть так

{1}, {4}, {1,1}, {1,4}, {4,1}, {4,4}, {1,1,1}, ....

и те, которые N в сумме составляют

{1,4}, {4, 1}, {1,1,1,1,1}

Мне нужен алгоритм, который находит их эффективно.

Мой способ «грубой силы» был бы таким

 static IEnumerable<IEnumerable<int>> OrderedArrangements(IEnumerable<int> nums, int k)
{
    var singles = nums.Select(i => new int[] {i} );
    var cumulative = singles;
    for(int j = 2; j <= k;   j)
    {
        var last = cumulative.Where(list => list.Count() == (j - 1));
        var next = from x in singles
                   from y in last
                   select x.Concat(y);
        cumulative = cumulative.Concat(next);           
    }
    return cumulative;
}
  

и затем

 int sumToN = OrderedArrangements(new int[] {1, 4}, N)
                .Where(x => x.Sum() == N);
  

но мне интересно, есть ли очевидный и более эффективный способ сделать это.

На всякий случай, если приведенный выше ответ недостаточно ясен, вы можете попробовать прямую рекурсию, например

      ...
    /       
   (1)     (4)          
  /       /  
 (1)(4)   (1)(4)
  

 static void f(int sum, int n, String str, int[] arr){
    if (n == sum){
        Console.WriteLine(str);
        return;
    }
    if (n > sum) return;
    for (int i = 0; i < arr.Length; i  ){
        f(sum, n   arr[i], str   arr[i].ToString(), arr);
    }
}

static void Main(string[] args){
    int[] arr =  { 1, 4 };
    f(5, 0, "", arr);
}
  

Где sum находится N в вашем вопросе, n инициализируется 0 , str инициализируется "" и arr находится S в вашем вопросе.

вывод:

 11111
14
41
  

Это работает для меня:

 static IEnumerable<IEnumerable<int>> OrderedArrangements(IEnumerable<int> nums, int k)
{
    return
        k <= 0
            ? new [] { Enumerable.Empty<int>() }
            : nums
                .SelectMany(
                    n => OrderedArrangements(nums, k - n),
                    (n, ns) => new [] { n }.Concat(ns))
                .Where(ns => ns.Sum() == k);
}
  

Результатом OrderedArrangements(new [] { 1, 4 }, 5) является:

Я запустил этот код тестирования производительности:

 Func<Func<IEnumerable<IEnumerable<int>>>, double> measure = f =>
{
    var sw = Stopwatch.StartNew();
    var result = f();
    sw.Stop();
    return sw.Elapsed.TotalMilliseconds;
};

var n = 200;
var a = 0.0;
var b = 0.0;
for (var i = 0; i < n; i  )
{
    a  = measure(() => OrderedArrangements_A(new [] { 1, 4, 9, 13 }, 50000));
    b  = measure(() => OrderedArrangements_B(new [] { 1, 4, 9, 13 }, 50000));
}
  

OrderedArrangements_A это код OP и OrderedArrangements_B мой.

Я получил в среднем 15,6 мс для «A» и 0,004 мс для «B». Мой код для этого теста выполняется примерно в 3895 раз быстрее.