Hello,
I have encountered a general programming problem that has turned out to be more nontrivial than I first thought. I have a function, let's say "f1", that has two single-dimensional int arrays, i.e. "a1" and "a2", with the length of both of these arrays being equal. a1 is a fixed array containing only positive integers. What I want to do is loop over ALL the different possible permutations of a2 such that each a2[i] goes from 0 to a1[i]-1.
This is analogous to a well-known "for" loop for a counter variable "c" that goes from 0 to n-1:
for (int c=0; c<n, c++)...
Except here, I would like to expand the array counter variable and maximum value to arrays themselves, as in one dimension higher. The elements of array "a2" are all collectively the counter (analogous to "c" above), and the elements of array a1 are each one greater than the maximum value of the corresponding element in a2 (i.e. "a1" is analogous to "n").
I already know that the number of permutations of the loop will be the product of the elements of a1.
To picture this, let's say I have this for a1, the "upper limit" of my loop:
int[] a1 = { 2 2 3 };
Then the total number of permutations is found by:
int npermutations=1;
for (int i=0; i<a1.length; i++){
npermutations*=a1;
}
... which in this case will be 2 * 2 * 3 = 12.
Then in this case the goal is to get array a2 to take on ALL of the following values (and perform a loop over them):
{0,0,0}
{0,0,1}
{0,0,2}
{0,1,0}
{0,1,1}
{0,1,2}
{1,0,0}
{1,0,1}
{1,0,2}
{1,1,0}
{1,1,1}
{1,1,2}
It is pretty obvious that if I KNEW what the length of a1 was at code-time, this would be a very simple problem, as in 3 nested for loops for 3 elements:
for (int i=0; i<a1[0].length;i++){
for (int j=0; j<a1[1].length; j++){
for (int k=0; k<a1[2].length; k++{
a2={i,j,k};
/* ... My code that uses a2 ... */
}
}
}However, the loops have to be generalized for ANY length of a1:
for (int i=0; i<a1[0].length;i++){
for (int j=0; j<a1[1].length; j++){
for (int k=0; k<a1[2].length; k++{
/* ... more and more nested for loops ... */
a2={i,j,k /* , ... more and more element counter variables ... */};
/* ... My code that uses a2 ... */
/* ... more and more nested ending brackets ... */
}
}
}Something tells me that this might be a little easier to do recursively, but to be more robust, perhaps an iterative way would be better (so as not to be limited by the depth of the recursion stack)? Where do I begin? How do I even set this up?
Thanks for any help.
Edited by: Mark001 on Apr 18, 2008 11:21 PM