Monday's programming question of the day
-
Let's say you have n combinations of v items, and you want create a sequential string that represents every non-duplicate combination of those v items. So, 3 combinations (3 columns) of 4 items (0 through 3 inclusive) would look like: 0 1 2 0 1 3 0 2 3 1 2 3 and you also want to create the same pattern in reverse: 1 2 3 0 2 3 0 1 3 0 1 2 However, you don't want to create the entire list in memory (because, for example, 8 combinations of 58 items will result in billions of rows). Instead, you want to get each combination sequentially, forward or reverse, as requested, given the last state. Here's a C++ implementation I wrote a while ago that iterates in the forward direction, using an array to manage the current state:
bool MyList::GetNext(int numCombinations)
{
if (numCombinations==-1)
{
return false;
}int q=list\[numCombinations\]; ++q; while (q >= numItems) { if (numCombinations==0) { return false; } if (!GetNext(numCombinations-1)) { return false; } q=list\[numCombinations-1\]+1; } list\[numCombinations\]=q; return true;}
Use your favorite language to write this. :) (Yeah, I must admit, I'm personally interested in cool C# 3.5 examples) Marc
C#3 list extension method:
public static IEnumerable< IList< T >> GetPremutations< T >(this IList< T > items, int columns)
{
for (int i = 0; i < (int)Math.Pow(items.Count, columns); i++)
{
IList< T > result = new List< T >();for (int k = 0; k < columns; k++) result.Add(items\[(i / (int)Math.Pow(items.Count,k) ) % items.Count\]); yield return result; }}
This will return a list of the elements for each premutation. (not a list with all premutations, a list for each entry in the premutation set... each entry is yielded by the enumerator) (However, this will crash and burn at large sets due to int overflows)
-
Let's say you have n combinations of v items, and you want create a sequential string that represents every non-duplicate combination of those v items. So, 3 combinations (3 columns) of 4 items (0 through 3 inclusive) would look like: 0 1 2 0 1 3 0 2 3 1 2 3 and you also want to create the same pattern in reverse: 1 2 3 0 2 3 0 1 3 0 1 2 However, you don't want to create the entire list in memory (because, for example, 8 combinations of 58 items will result in billions of rows). Instead, you want to get each combination sequentially, forward or reverse, as requested, given the last state. Here's a C++ implementation I wrote a while ago that iterates in the forward direction, using an array to manage the current state:
bool MyList::GetNext(int numCombinations)
{
if (numCombinations==-1)
{
return false;
}int q=list\[numCombinations\]; ++q; while (q >= numItems) { if (numCombinations==0) { return false; } if (!GetNext(numCombinations-1)) { return false; } q=list\[numCombinations-1\]+1; } list\[numCombinations\]=q; return true;}
Use your favorite language to write this. :) (Yeah, I must admit, I'm personally interested in cool C# 3.5 examples) Marc
-
Let's say you have n combinations of v items, and you want create a sequential string that represents every non-duplicate combination of those v items. So, 3 combinations (3 columns) of 4 items (0 through 3 inclusive) would look like: 0 1 2 0 1 3 0 2 3 1 2 3 and you also want to create the same pattern in reverse: 1 2 3 0 2 3 0 1 3 0 1 2 However, you don't want to create the entire list in memory (because, for example, 8 combinations of 58 items will result in billions of rows). Instead, you want to get each combination sequentially, forward or reverse, as requested, given the last state. Here's a C++ implementation I wrote a while ago that iterates in the forward direction, using an array to manage the current state:
bool MyList::GetNext(int numCombinations)
{
if (numCombinations==-1)
{
return false;
}int q=list\[numCombinations\]; ++q; while (q >= numItems) { if (numCombinations==0) { return false; } if (!GetNext(numCombinations-1)) { return false; } q=list\[numCombinations-1\]+1; } list\[numCombinations\]=q; return true;}
Use your favorite language to write this. :) (Yeah, I must admit, I'm personally interested in cool C# 3.5 examples) Marc
C'mon guys. Surely this can be done in a single line of code using LINQ, right? I'm not going to try it. I don't have my license yet, and I wouldn't want anyone to get hurt.
Software Zen:
delete this; -
C'mon guys. Surely this can be done in a single line of code using LINQ, right? I'm not going to try it. I don't have my license yet, and I wouldn't want anyone to get hurt.
Software Zen:
delete this;Gary Wheeler wrote:
C'mon guys. Surely this can be done in a single line of code using LINQ, right?
LOL! That's what I was thinking to. But actually not Linq, because it has to yield a return for each iteration. Marc
-
C#3 list extension method:
public static IEnumerable< IList< T >> GetPremutations< T >(this IList< T > items, int columns)
{
for (int i = 0; i < (int)Math.Pow(items.Count, columns); i++)
{
IList< T > result = new List< T >();for (int k = 0; k < columns; k++) result.Add(items\[(i / (int)Math.Pow(items.Count,k) ) % items.Count\]); yield return result; }}
This will return a list of the elements for each premutation. (not a list with all premutations, a list for each entry in the premutation set... each entry is yielded by the enumerator) (However, this will crash and burn at large sets due to int overflows)
RUN!!! It is to early for "Pre-mutations" please stick with "Permutations" ha ha, I love reading something and having mutated creatures being created in a loop.
-
Let's say you have n combinations of v items, and you want create a sequential string that represents every non-duplicate combination of those v items. So, 3 combinations (3 columns) of 4 items (0 through 3 inclusive) would look like: 0 1 2 0 1 3 0 2 3 1 2 3 and you also want to create the same pattern in reverse: 1 2 3 0 2 3 0 1 3 0 1 2 However, you don't want to create the entire list in memory (because, for example, 8 combinations of 58 items will result in billions of rows). Instead, you want to get each combination sequentially, forward or reverse, as requested, given the last state. Here's a C++ implementation I wrote a while ago that iterates in the forward direction, using an array to manage the current state:
bool MyList::GetNext(int numCombinations)
{
if (numCombinations==-1)
{
return false;
}int q=list\[numCombinations\]; ++q; while (q >= numItems) { if (numCombinations==0) { return false; } if (!GetNext(numCombinations-1)) { return false; } q=list\[numCombinations-1\]+1; } list\[numCombinations\]=q; return true;}
Use your favorite language to write this. :) (Yeah, I must admit, I'm personally interested in cool C# 3.5 examples) Marc
Looks like some college student is trying to get the community to get them an A.
-
Looks like some college student is trying to get the community to get them an A.
Member 3938395 wrote:
Looks like some college student is trying to get the community to get them an A.
I'm not a college student. I thought it would be an interesting exercise, as it's something I'm dealing with on a project. I particularly find it interesting that no one posted the reverse version. There's two ways of doing it, the easiest is to generate the forward item and subtract the values from the max item count and replace the string in reverse order so that the result is still incremental. Marc
-
Member 3938395 wrote:
Looks like some college student is trying to get the community to get them an A.
I'm not a college student. I thought it would be an interesting exercise, as it's something I'm dealing with on a project. I particularly find it interesting that no one posted the reverse version. There's two ways of doing it, the easiest is to generate the forward item and subtract the values from the max item count and replace the string in reverse order so that the result is still incremental. Marc
Is there any reason that you have the forward version and you still need the reverse version of the function? Or is it just purely academically pursue to find the reverse version just for sake of fun?
-
Is there any reason that you have the forward version and you still need the reverse version of the function? Or is it just purely academically pursue to find the reverse version just for sake of fun?
CBasicNet wrote:
Is there any reason that you have the forward version and you still need the reverse version of the function?
In a multicore system, one of the interesting things to do is to create a couple threads, one working through the list forward, the other reverse. Marc
-
CBasicNet wrote:
Is there any reason that you have the forward version and you still need the reverse version of the function?
In a multicore system, one of the interesting things to do is to create a couple threads, one working through the list forward, the other reverse. Marc
With a forward version and reverse version, you can only create 2 threads. By using Combinadic[^] , you can create as many threads as accordingly to the number of cores or SMP processors. This article below shows you how to find combinations using Combinadic and arbitrary number of threads. You might be interested to take a look. Combinations in C++, Part 2[^]
-
With a forward version and reverse version, you can only create 2 threads. By using Combinadic[^] , you can create as many threads as accordingly to the number of cores or SMP processors. This article below shows you how to find combinations using Combinadic and arbitrary number of threads. You might be interested to take a look. Combinations in C++, Part 2[^]
CBasicNet wrote:
With a forward version and reverse version, you can only create 2 threads.
Well no. First off, you can partition the forward and reverse pieces. Furthermore, you can have several cores working on the forward iterations and other cores working on the reverse iterations, you just do a lock when a thread is ready to get the next iteration.
CBasicNet wrote:
By using Combinadic[^]
Wow! Thanks for that great link! It also references an MSDN article, which provides an implementation. Geez. I've spent a lot of time debugging my algorithms. If only I'd seen this! Well, thanks again. Tomorrow I'm going to replace my algorithms with the code in either the C# version or your C++ version (my original code is in C++, BTW). Great article, also. I owe you one! Marc