Sign in to follow this  
AlphaCoder

Tough Recursion problem

Recommended Posts

I want to write a program that prints all ordered coordinates in an arbitrary amount of dimensions where each value goes from 1 to 10 (for simplicity) For example, in the case of two dimensions it would print all 100 of the ordered pairs from 1,1 to 10,10. In the case of three dimensions it would print all 1000 of the ordered triplets from 1,1,1 to 10,10,10. For a set amount of dimensions it's easy. You just write nested for loops. But what if the amount of dimensions is arbitrary (specified at run-time)? There's probably some clever recursive method for doing this but I can't figure it out. note: I'm using c++
#include <iostream>

using namespace std;

void someRecursiveFunction(int d)
{
 // and here's where i need help
}

int main()
{
 int numDimensions;
 cout << "Enter number of dimensions\n";
 cin >> numDimensions;
 someRecursiveFunction(numDimensions);
 return 0;
}


Also. I'd like to avoid using arrays. I'd like to do it using only couts, increments, decrements, and recursive calls. [Edited by - AlphaCoder on November 6, 2008 11:45:37 PM]

Share this post


Link to post
Share on other sites
This should get you thinking, can be solved non recursively.


void doThatThing( int Dimensions, int High )
{
unsigned int MaxCounts = pow( Dimensions, High );

unsigned int Current = 0;

while( Current < MaxCounts )
{
for( int x = 0; x < Dimensions; x++ )
{
//do the harder part here, it's too late for me :/ I was thinking some modulus majik
}

Current++;
}
}



Share this post


Link to post
Share on other sites
Yes I've already figured out the modulus transforms to go from n-dimensional coordinates to an integer and to extract n-dimensional coordinates from an integer. This is actually the technique I'm using to write a program that generates a maze of arbitrary dimensions.

But I'm looking for a recursive solution to the above problem. Just for curiosity's sake.

Share this post


Link to post
Share on other sites
Here's one possible solution:
void recursive_list(unsigned dimensions, struct count { struct count *link; unsigned val; } *list) {
if(dimensions--) {
struct count head = { list, 1 };

do {
recursive_list(dimensions, &head);
} while(++head.val <= 10);
} else {
while(list) {
printf("%u%c", list->val, list->link ? ',' : '\n');
list = list->link;
}
}
}

Share this post


Link to post
Share on other sites
Quote:
Original post by AlphaCoder
note: I'm using c++

Since you're using C++, I suggest writing a user-defined data type that produces the combinations.

#include <vector>
#include <iostream>

class Combinations
{
int dimensions;
int min_value;
int max_value;
std::vector<int> current_value;

public:
Combinations(int dimensions, int min_value, int max_value) :
dimensions(dimensions),
min_value(min_value),
max_value(max_value),
current_value(dimensions, min_value)
{}

bool next()
{
for (int i = 0; i < dimensions; ++i)
if (++current_value[i] <= max_value)
return true;
else
current_value[i] = min_value;
return false;
}

friend std::ostream& operator<<(std::ostream& os, const Combinations& com)
{
for (int i = com.dimensions - 1; i > 0; --i)
os << com.current_value[i] << ',';
os << com.current_value[0];
return os;
}
};

int main()
{
int numDimensions;
std::cout << "Enter number of dimensions\n";
std::cin >> numDimensions;
Combinations com(numDimensions, 1, 10);
do
std::cout << com << std::endl;
while (com.next());
}

Share this post


Link to post
Share on other sites
Quote:
Original post by AlphaCoder
I want to write a program that prints all ordered coordinates in an arbitrary amount of dimensions where each value goes from 1 to 10 (for simplicity)

For example, in the case of two dimensions it would print all 100 of the ordered pairs from 1,1 to 10,10. In the case of three dimensions it would print all 1000 of the ordered triplets from 1,1,1 to 10,10,10.

For a set amount of dimensions it's easy. You just write nested for loops. But what if the amount of dimensions is arbitrary (specified at run-time)? There's probably some clever recursive method for doing this but I can't figure it out.

note: I'm using c++

*** Source Snippet Removed ***

Also. I'd like to avoid using arrays. I'd like to do it using only couts, increments, decrements, and recursive calls.


It's the same as this problem, except that for each element you have 10 specific symbols (always the same) instead of a varying set of 3 symbols (chosen according to a corresponding input symbol).

Basically: for each possible symbol S for the first element, for each possible output O for the other elements (which you determine recursively), you output S followed by O. Since communicating the set O back from the recursive call would mean returning all those elements in a container (which you want to avoid, and which would potentially mean very large containers!), you instead communicate the symbol S (rather, the current prefix P composed of all known symbols up to this point in the recursion) forward to the recursive call. Thus, for each prefix-set P of symbols representing already-processed elements, for each symbol S for the current element, generate results by using prefix P + S for the remaining elements (this is where you make the recursive call); if there are no remaining elements, then P + S is a complete result, which you then output.

Share this post


Link to post
Share on other sites
Quote:
Original post by DevFred
Quote:
Original post by AlphaCoder
note: I'm using c++

Since you're using C++, I suggest writing a user-defined data type that produces the combinations.

*** Source Snippet Removed ***


Yep this is the way I originally did it. But I learned a lot from your code. Specifically about vectors and that you can overload things like '<<'

Share this post


Link to post
Share on other sites
In case anyone's using this for a reference in the future, here's the easiest(and possibly fastest?) way i found.


void PrintDimensions( int Dimensions, int High )
{
unsigned int Max = (unsigned int)pow( High, Dimensions );
unsigned int Count = 0;

while( Count < Max )
{
for( int x = Dimensions - 1; x >= 0; x-- )
{
if( x == 0 )
{
cout << Count % High << endl;
}
else
{
cout << (Count / (unsigned int)pow( High, x )) % High << ",";
}
}

cout << endl;

Count++;
}
}

Share this post


Link to post
Share on other sites
My suggestion would be:

template<typename F> 
void all_tuples(unsigned max, std::size_t d, F f)
{
std::vector<unsigned> v(d,1);
std::vector<unsigned>::reverse_iterator i = v.rbegin();
while ( i != v.rend() )
if (*i == max)
{ *i++ = 1; }
else
{ (*i)++; i = v.rbegin(); f(v.begin(), v.end()); }
}


It implements the "add one" arithmetic operation. The iterator serves as a carry bit.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this