Attempt to generate all sequences of given numbers up to the maximum amount

Question

Given the following list of downstream unique numbers (3,2,1), I want to generate all the sequences consisting of these numbers to the maximum amount.

Let's say that the amount should be below 10. Then the sequences following me:

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 am sure that there is a “standard” way to generate this.

I was thinking about using linq, but can't figure it out. Also, I'm trying to use the stack approach, but I still fail.

Any idea?

Answer 1

I think this is easiest to write recursively, that pure LINQ is not so good. Therefore, it is best to implement this as a regular recursive function. Pass as the parameter the amount remaining from your maximum value, and each time you add the en element, call the function recursively, reducing the total amount, respectively:

 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 

Please note that this is not the most effective solution.

Answer 2

I think you can solve this by building a tree. On each node you have a list of values. Assuming that the sum of this list is less than the required amount, let it call it S -, you can build no more than three children for this node: one, adding 1 to the list of this node, adding 2 and one by adding 3. The condition for building the child was that the sum of the new list will still be less than S. In the end, that is, when you cannot generate new nodes, you have all your sequences in the nodes of your tree.

EDIT: in C # my poor explanation would be this:

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 one:

 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 this is standard enough, but it roughly corresponds to the task. Hope this fits your needs ...

EDIT : to avoid generating the same sequences, we can “order” a tree: a node cannot create a child with a lower value than it. Thus, in the AddChild method, we run the loop on the “data”, and not on 1.

Answer 3

I do not know if this is “standard” as such, but it is not uncommon to start from the bottom and work.

There is 1 way to do 1.

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

To calculate ways to get N, consider ways to create N-1 starting at 1, ways to make N-2 starting at 2 or 1, and ways to make N-3 starting at 3, 2, or 1.

Answer 4

It seems to me that the “easiest” (if not the most efficient) way to do this is to simply take your set of numbers and take all its permutations, and then filter out those whose sum is above the cut-off point.

Answer 5

It seems you are interested in sections with a bit of twist. This function performs the trick. Basically, keep adding numbers to the stack until their sum is less than the target amount, and 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 result in a specific format or not, but you can probably work with this or other answers.