Trying to generate all sequences of specified numbers up to a max sum

Question

Hi,

Given the following list of descending unique numbers (3,2,1) I wish to generate all the sequences consisting of those numbers up to a maximum sum.

Let's say that the sum should be below 10. Then the sequences I'm after are:

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

I'm sure that there's a "standard" way to generate this.

I thought of using linq but can't figure it out. Also, I am trying a stack based approach but I am still not successful.

Any idea?

Answer 1

I think you can solve that by building a tree. On each node you have a list of values. Assuming the sum of this list is less than the required sum - let's call it S -, you can build at most three children for this node: one by adding 1 to the list of this node, one by adding 2 and one by adding 3. The condition to build a child would be that the sum of the new list would still be less that S. At the end, i.e. when you can't generate new nodes, you have all your sequences in the nodes of your tree.

EDIT: in C# my poor explanation would give sth like that:

first:

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

then the main:

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
}

I don't know if it is standard enough but it does roughly the job. I hope it fits your need...

EDIT: to avoid the generation of same sequences, we can "order" the tree: a node can't generate a child with a lower value than its one. Thus, in the AddChild method, we start the loop at "data" and not at 1.

Answer 2

I think this is easiest to write recursively, something which pure LINQ isn't that great for. So it's probably best to implement this as an ordinary recursive function. Pass as a parameter the amount you have left from your maximum total and every time you add en element, call the function recursively, reducing the total appropriately:

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

Result:

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

Note that this isn't the most efficient solution.

Answer 3

I don't know whether this is "standard" as such, but it's not unusual to start at the bottom and work up.

There's 1 way to make 1.

There's 2 ways to make 2, divided into 3 categories: those starting with a 1, those starting with a 2, and those starting with a 3. The last category of course is empty.

To count the ways of making N, consider the ways of making N-1 starting with 1, the ways of making N-2 starting with 2 or 1, and the ways of making N-3 starting with 3, 2, or 1.

Answer 4

It seems to me that the 'easiest' (if not the most efficient) way of doing this would be to just take your number set, and take all the permutations of it, then filter out the ones whose sum is above the cutoff point.

Answer 5

It seems like you're interested in partitions, with a bit of a twist. This function does the trick. Basically, keep adding numbers to a stack while their sum is less than your target sum, then print the stack at each step.

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

I'm not sure if you need the output in a specific format or not, but you can probably work with this or the other answers.