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

Posted by Stecy on Stack Overflow See other posts from Stack Overflow or by Stecy
Published on 2010-04-07T17:08:09Z Indexed on 2010/04/07 17:13 UTC
Read the original article Hit count: 298

Filed under:

LINQ

|

c#

|

algorithm

|

sequences

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?

© Stack Overflow or respective owner

Related posts about LINQ

LINQ to SQL, LINQ to XML and Accessing DataTable using LINQ

as seen on C# Corner - Search for 'C# Corner'
This article demonstrates how to use LINQ on DataTable, XML Data using LINQ to XML and SQL server data base using LINQ to SQL Classes. >>> More
Exception with Linq2SQL Query

as seen on Stack Overflow - Search for 'Stack Overflow'
I am running a query using Linq2SQL that comes down to following query: DateTime? expiration = GetExpirationDate(); IQueryable<Persons> persons = GetPersons(); IQueryable<Items> subquery = from i in db.Items where i.ExpirationDate >= expiration … >>> More
What is Linq?

as seen on ASP.net Weblogs - Search for 'ASP.net Weblogs'
The way data can be retrieved in .NET. LINQ provides a uniform way to retrieve data from any object that implements the IEnumerable<T> interface. With LINQ, arrays, collections, relational data, and XML are all potential data sources. Why LINQ?With LINQ, you can use the same syntax to retrieve… >>> More
Mixing Silverlight-Specific System.Xml.Linq dll with Non-Silverlight System.Xml.Linq dll

as seen on Stack Overflow - Search for 'Stack Overflow'
I have a Logic layer that references Silverlight's System.Xml.Linq dll and a GUI that is in WPF (hence using the non-Silverlight System.Xml.Linq dll). When I attempt to pass an XElement from GUI project to a method in the Logic project, I am getting (basically) "XElement is not of type XElement" errors… >>> More
Subsonic 3 LINQ vs LINQ to SQL

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, I am using SQL Server 2005 in a project. I have to decide about datalayer. I would like to use LINQ in my project. I saw SubSonic 3 supporting LINQ and I also have option for LINQ to SQL, because i can have typed lists from LINQ to SQL. I am wondering what is different between LINQ to SQL and… >>> More

Related posts about c#

.NET WebRequest.PreAuthenticate not quite what it sounds like

as seen on West-Wind - Search for 'West-Wind'
I’ve run into the problem a few times now: How to pre-authenticate .NET WebRequest calls doing an HTTP call to the server – essentially send authentication credentials on the very first request instead of waiting for a server challenge first? At first glance this sound like it should be easy:… >>> More
HttpWebRequest and Ignoring SSL Certificate Errors

as seen on West-Wind - Search for 'West-Wind'
Man I can't believe this. I'm still mucking around with OFX servers and it drives me absolutely crazy how some these servers are just so unbelievably misconfigured. I've recently hit three different 3 major brokerages which fail HTTP validation with bad or corrupt certificates at least according to… >>> More
The dynamic Type in C# Simplifies COM Member Access from Visual FoxPro

as seen on West-Wind - Search for 'West-Wind'
I’ve written quite a bit about Visual FoxPro interoperating with .NET in the past both for ASP.NET interacting with Visual FoxPro COM objects as well as Visual FoxPro calling into .NET code via COM Interop. COM Interop with Visual FoxPro has a number of problems but one of them at least got a lot… >>> More
Dynamic Type to do away with Reflection

as seen on West-Wind - Search for 'West-Wind'
The dynamic type in C# 4.0 is a welcome addition to the language. One thing I’ve been doing a lot with it is to remove explicit Reflection code that’s often necessary when you ‘dynamically’ need to walk and object hierarchy. In the past I’ve had a number of ReflectionUtils that used string based expressions… >>> More
Finding a Relative Path in .NET

as seen on West-Wind - Search for 'West-Wind'
Here’s a nice and simple path utility that I’ve needed in a number of applications: I need to find a relative path based on a base path. So if I’m working in a folder called c:\temp\templates\ and I want to find a relative path for c:\temp\templates\subdir\test.txt I want to receive back subdir\test… >>> More