Как узнать все перестановки чисел на сумму до 100 - PullRequest
Новая
       31

Как узнать все перестановки чисел на сумму до 100

0 голосов
/ 18 апреля 2020

Я пытаюсь найти эффективный способ создания метода, который использует словарь, содержащий несколько списков последовательных целых чисел (каждый список должен начинаться с 0 или выше и заканчиваться на 100 или ниже, но точные числа могут отличаться) и возвращает список словарей, содержащих все перестановки, где сумма всех чисел равна 100.

Например, для 4 категорий: 10 + 20 + 10 + 60 = 100

Каждый словарь в результирующий список должен храниться с одним целочисленным значением для каждого ключа.

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

using System;
using System.Collections.Generic;
using System.Linq;

namespace recursiveTest
{
    class Program
    {
        static void Main(string[] args)
        {
            Dictionary<string, List<int>> data = new Dictionary<string, List<int>>();
            data.Add("A", Enumerable.Range(0, 100).ToList());
            data.Add("B", Enumerable.Range(0, 100).ToList());
            data.Add("C", Enumerable.Range(0, 100).ToList());
            data.Add("D", Enumerable.Range(0, 100).ToList());
            // I would like to add a few entries more...

            List<Dictionary<string, int>> permutations = new List<Dictionary<string, int>>();

            foreach (var a in data["A"])
            {
                foreach (var b in data["B"])
                {
                    foreach (var c in data["C"])
                    {
                        foreach (var d in data["D"])
                        {
                            if (a + b + c + d == 100)
                            {
                                var current = new Dictionary<string, int>()
                                {
                                    ["A"] = a,
                                    ["B"] = b,
                                    ["C"] = c,
                                    ["D"] = d,
                                };
                                permutations.Add(current);
                            }
                        }
                    }
                }
            }

            Console.WriteLine($"Found (foreach): {permutations.Count()}");
            Console.ReadKey();
        }
    }
}

Альтернатива с использованием LINQ: 

            List<Dictionary<string, int>> permutations2 = (from a in data["A"]
                                                           from b in data["B"]
                                                           from c in data["C"]
                                                           from d in data["D"]
                                                           where a + b + c + d == 100
                                                           let current = new Dictionary<string, int>()
                                                           {
                                                               ["A"] = a,
                                                               ["B"] = b,
                                                               ["C"] = c,
                                                               ["D"] = d,
                                                           }
                                                           select current).ToList();

            Console.WriteLine($"Found (LINQ): {permutations2.Count()}");
            Console.ReadKey();

Это было не очень сложной задачей до того, как количество категорий (словарных ключей) и чисел начало расти ... Так как количество словарных ключей (категорий) может изменяться, это, кажется, потенциальный кандидат для рекурсии, но я не смог заставить его работать. Эти две версии имеют несколько очевидных недостатков:

  1. Как только количество элементов и / или категорий увеличивается, производительность неожиданно падает.
  2. Код в форме стрелки выглядит как рецепт для катастрофа.
  3. Он пытается обойти все возможные комбинации, хотя на самом деле полезны лишь немногие (те, которые суммируются до 100).

Каков наилучший способ достижения целочисленный результат, короткий и читаемый код и хорошая производительность?

Есть ли способ отфильтровать ненужные циклы при попытке найти эти 100 значений сумм?

РЕДАКТИРОВАТЬ : Для пояснения, моя идея состоит в том, чтобы иметь возможность определять метод с такой сигнатурой: 

private static List<Dictionary<string, int>> GetValidPermutations(Dictionary<string, List<int>> data)

Затем вызывать его так: 

List<Dictionary<string, int>> permutations = GetValidPermutations(data);

1 Ответ

1 голос
/ 18 апреля 2020

Для повышения производительности ключ заключается в сокращении количества ненужных итераций: 

static List<Dictionary<string, int>> GetValidPermutations(int target, Dictionary<string, List<int>> data)
{
    return GetValidPermutations(target, data, 0, new int[data.Count])
            .Select(perm => CreateDictionary(data.Keys, perm))
            .ToList();
}

static Dictionary<string, int> CreateDictionary(IEnumerable<string> keys, IEnumerable<int> values)
{
    return keys.Zip(values, KeyValuePair.Create)
               .ToDictionary(pair => pair.Key, pair => pair.Value);
}

static IEnumerable<int[]> GetValidPermutations(int target, Dictionary<string, List<int>> data, int level, int[] sequence)
{
    if (level < sequence.Length)
    {
        var currentList = data.ElementAt(level).Value;
        var subsequentLists = data.Skip(level + 1).Select(x => x.Value);
        int start = Math.Max(currentList[0], target - subsequentLists.Sum(x => x.Last()));
        int end = Math.Min(currentList.Last(), target - subsequentLists.Sum(x => x[0]));
        for (sequence[level] = start; sequence[level] <= end; sequence[level]++)
        {
            int subTarget = target - sequence[level];
            foreach (var perm in GetValidPermutations(subTarget, data, level + 1, sequence))
            {
                yield return perm;
            }
        }
    }
    else
    {
        var perm = sequence.Append(target);
        System.Diagnostics.Debug.Assert(perm.Sum() == 100);
        yield return perm.ToArray();
    }
}

Вышеприведенные значения start и end тщательно рассчитываются для включения только необходимых итераций. Другие значения пропускаются, потому что они не могут сформировать перестановку.

Затем вы можете вызвать метод следующим образом: 

var p4 = GetValidPermutations(100, data);
Console.WriteLine($"Found (Recursion): {p4.Count()}");

Может быть, трудно сначала понять версию рекурсии, там это эквивалент для l oop, вы можете видеть, что некоторые разделы кода повторяются: 

const int TARGET = 100;
var permutations3 = new List<Dictionary<string, int>>();

int aStart = Math.Max(data["A"][0], TARGET - data["B"].Last() - data["C"].Last() - data["D"].Last());
int aEnd = Math.Min(data["A"].Last(), TARGET - data["B"][0] - data["C"][0] - data["D"][0]);
for (int a = aStart; a <= aEnd; a++)
{
    int bStart = Math.Max(data["B"][0], TARGET - a - data["C"].Last() - data["D"].Last());
    int bEnd = Math.Min(data["B"].Last(), TARGET - a - data["C"][0] - data["D"][0]);
    for (int b = bStart; b <= bEnd; b++)
    {
        int cStart = Math.Max(data["C"][0], TARGET - a - b - data["D"].Last());
        int cEnd = Math.Min(data["C"].Last(), TARGET - a - b - data["D"][0]);
        for (int c = cStart; c <= cEnd; c++)
        {
            var perm = new Dictionary<string, int>
            {
                { "A", a },
                { "B", b },
                { "C", c },
                { "D", TARGET - a - b - c }
            };
            System.Diagnostics.Debug.Assert(perm["D"] >= data["D"][0] && perm["D"] <= data["D"].Last());
            permutations3.Add(perm);
        }
    }
}
Console.WriteLine($"Found (for): {permutations3.Count()}");

Пропускающая логика c может быть проиллюстрирована следующими примерами:

Предположим, что максимальные значения B, C, D равны 10, 20, 30 соответственно, тогда A должно быть не менее 40, чтобы иметь сумму 100. Таким образом, A может начинаться с 40, а 0-39 пропускаются (если доступно) .

Аналогичные логи c могут применяться для пропуска более высоких диапазонов. Предположим, что минимальные значения B, C, D равны 5, 10, 15 соответственно, тогда A не может превышать 70. Поскольку сумма будет превышать 100, если это так. Поэтому мы можем прекратить зацикливание, когда A превысит 70.

Применение лога пропуска c для всех категорий может привести к приведенному выше коду. Кроме того, последняя категория может быть рассчитана напрямую, без циклов.

...