Попытка сгенерировать все последовательности указанных чисел до максимальной суммы

Question

Учитывая следующий список нисходящих уникальных чисел (3,2,1), я хочу сгенерировать все последовательности, состоящие из этих чисел, вплоть до максимальной суммы.

Скажем, что сумма должна быть ниже 10Тогда последовательности, за которыми я следую:

3 3 3
3 3 2 1
3 3 2
3 3 1 1 1
3 3 1 1
3 3 1
3 3
3 2 2 2
3 2 2 1 1
3 2 2 1
3 2 2
3 2 1 1 1 1
3 2 1 1 1
3 2 1 1
3 2 1
3 2
3 1 1 1 1 1 1
3 1 1 1 1 1
3 1 1 1 1
3 1 1 1
3 1 1
3 1
3
2 2 2 2 1
2 2 2 2
2 2 2 1 1 1
2 2 2 1 1
2 2 2 1
2 2 2
2 2 1 1 1 1 1
2 2 1 1 1 1
2 2 1 1 1
2 2 1 1
2 2 1
2 2
2 1 1 1 1 1 1 1
2 1 1 1 1 1 1
2 1 1 1 1 1
2 1 1 1 1
2 1 1 1
2 1 1
2 1
2
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1
1 1 1 1
1 1 1
1 1
1

Я уверен, что есть "стандартный" способ создать это.

Я думал об использовании linq, но не могу понятьэто из.Кроме того, я пытаюсь использовать подход, основанный на стеке, но я все еще не успешен.

Есть идеи?

Answer 1

Я думаю, что проще всего написать рекурсивно, для чего чистый LINQ не слишком хорош.Так что, вероятно, лучше всего реализовать это как обычную рекурсивную функцию.Передайте в качестве параметра сумму, которую вы оставили от своего максимального итога, и каждый раз, когда вы добавляете элемент en, рекурсивно вызывайте функцию, соответственно уменьшая итоговую сумму:

IEnumerable<IEnumerable<int>> sequences(IEnumerable<int> set, int maxTotal)
{
    foreach (int i in set.Where(x => x <= maxTotal))
    {
        yield return new int[] { i };
        foreach (var s in sequences(set.Where(x => x <= i), maxTotal - i))
            yield return (new int[] { i }).Concat(s);
    }
}

void Run()
{
    foreach (var z in sequences(new int[] { 3, 2, 1 }, 10))
    {
        Console.WriteLine(
            string.Join(" ", z.Select(x => x.ToString()).ToArray())
        );
    }
}

Результат:

3
3 3
3 3 3
3 3 3 1
3 3 2
3 3 2 2
3 3 2 1
3 3 2 1 1
3 3 1
3 3 1 1
3 3 1 1 1
...
1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1

Обратите внимание, что это не самое эффективное решение.

Answer 2

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

class Program
{
    static void Main()
    {
        GeneratePossibilites(new int[] {3, 2, 1}, 10, 0, new List<int>());
    }

    static void GeneratePossibilites(int[] array, int maxSum, int crSum, List<int> stack)
    {
        for (int i = 0; i < stack.Count; ++i )
            Console.Write(array[ stack[i] ].ToString() + " ");

        int start = 0;
        if (stack.Count > 0)
        {
            start = stack[stack.Count - 1];
            Console.WriteLine();
        }
        for (int i = start; i < array.Length; ++i)
            if (crSum + array[i] < maxSum)
            {
                stack.Add(i);
                GeneratePossibilites(array, maxSum, crSum + array[i], stack);
                stack.RemoveAt(stack.Count - 1);
            }
    }
}

Я не уверен, что вам нужен вывод в определенном формате илинет, но вы, вероятно, можете работать с этим или другими ответами.

Answer 3

Мне кажется, что «самый простой» (если не самый эффективный) способ сделать это - просто взять ваш набор чисел и взять все его перестановки, а затем отфильтровать те, сумма которых вышеточка отсечения.

Answer 4

Я не знаю, является ли это «стандартом» как таковым, но нередко начинать снизу и работать вверх.

Есть 1 способ сделать 1.

Есть 2 способа сделать 2, разделенных на 3 категории: те, которые начинаются с 1, те, которые начинаются с 2, и те, которые начинаются с 3. Последняя категория, конечно, пуста.

Чтобы подсчитать способы изготовления N, рассмотрим способы изготовления N-1, начиная с 1, способы изготовления N-2, начиная с 2 или 1, и способы изготовления N-3, начиная с 3, 2, или 1.

Answer 5

Я думаю, вы можете решить это, построив дерево. На каждом узле у вас есть список значений. Предполагая, что сумма этого списка меньше требуемой суммы - назовем это S - вы можете создать не более трех дочерних элементов для этого узла: один, добавив 1 в список этого узла, один, добавив 2, и один, добавив 3 Условием для создания ребенка будет то, что сумма в новом списке будет по-прежнему меньше, чем S. В конце, то есть когда вы не можете генерировать новые узлы, у вас есть все ваши последовательности в узлах вашего дерева.

РЕДАКТИРОВАТЬ: в C # мое плохое объяснение даст что-то вроде этого:

первый:

public class Node
{
    public Node()
    {
        Children = new List<Node>();
    }

    public static int SumMax { get; set; }

    public List<int> Values { get; set; }

    public List<Node> Children { get; set; }

    public void AddChild(int data)
    {
        if (Values.Sum() + data < SumMax)
        {
            Node child = new Node();
            child.Values = new List<int>(Values);
            child.Values.Add(data);
            Children.Add(child);

            for (int = data; i < 4; i++)
            {
                child.AddChild(i);
            }
        }
    }

    public void FillSequences(List<List<int>> sequences)
    {
        if (Values.Count != 0)
        {
            sequences.Add(Values);
        }

        foreach (Node child in Children)
        {
            child.FillSequences(sequences);
        }
    }
}

тогда основной:

void Main()
{
    Node.SumMax = 10;
    Node root = new Node();
    root.Values = new List<int>();
    for (int i = 1; i < 4; i++)
        root.AddChild(i);

    List<List<int>> sequences = new List<List<int>>();
    root.FillSequences(sequences);

    //here you've got your sequences results in "sequences" and you can do what you want
}

Я не знаю, достаточно ли это стандартно, но примерно выполняет свою работу. Я надеюсь, что это соответствует вашим потребностям ...

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