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
Here is a C# enhanced version
static IEnumerable<int> GetPermutation(int index, int selcount, int objcount)
{
List<int> list = new List<int>(objcount);
for (int i = 0; i < objcount; i++)
list.Add(i);
for (int i = 0; i < selcount; i++)
{
int N = list.Count;
int k = index % N;
index /= N;int result = list\[k\]; list.RemoveAt(k); yield return result; }}
A train station is where the train stops. A bus station is where the bus stops. On my desk, I have a work station.... _________________________________________________________ My programs never have bugs, they just develop random features.
modified on Tuesday, September 16, 2008 1:06 AM
-
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
I already did this, albeit without the reversal (which could trivially be added in the caller): http://www.codeproject.com/KB/recipes/combinations.aspx
-
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++) forward only (not just for 0-9)
void doit( int nitems, int col, vector v=vector(), int colval=0 )
{
if ( col==0 ){
for (int i(0); i < v.size(); ++i) cout << " " << v[i];
cout << endl;
return;
}for( int i(colval); i < nitems; ++i ){
vector v1 = v;
v1.push_back(i);
doit( nitems, col - 1, v1, i+1 );
}
}kick it off with
doit( nitems, ncols)
modified on Tuesday, September 16, 2008 1:31 AM
-
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
OK - an outline sketch of part of the problem in my language of choice, Haskell (a lazy, pure functional language)
indices :: Num a => [a] -> a -> Maybe [a]
indices [] _ = Nothing
indices l max =
if (last l)==max
then indices (init l) (max-1) >>= \stub -> return $ stub ++ [(last stub)+1]
else Just $ (init l) ++ [(last l)+1]loop :: (Num a, Enum a) => a -> a -> Maybe [a]
loop count max =
loop' [0..count-1] max
where
loop' l max = indices l max >>= \next -> loop' next maxindicestakes a list of indices (which would be used to de-reference the list of items usingmap (items !!) index_list) and the max count and returns the next list of indices in the required sequence. The list is wrapped in theMaybetype, so returnsJust _the list_when there are still items in the sequence orNothingwhen the sequence is complete. The one point of interest is thethenbranch of theif, which makes use of the monadic nature ofMaybeto propagateNothingor manipulate the returned sub-list.looptakes the # combinations and # items and iterates through the sequence vialoop'untilindicesreturnsNothing. Again, the monadic nature ofMaybeis used, to terminate the sequence. So, the 'state' is the index list, passed intoindicesand then (Maybe :-)) returned fromindices. As Haskell is pure functional (therefore, no mutable state), that's how you have to manage state. OK, it doesn't do the whole problem, but it illustrates the flavour of a possible Haskell solution. Basic garbage collection profiling shows that memory in use remains constant, independent of the parameters passed toloop, so that satisfies the condition that you don't generate all items of the sequence in memory at once. -
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