Public Group

Tough Recursion problem

This topic is 3656 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

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 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 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 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 on other sites
Quote:
 Original post by AlphaCodernote: 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 <= max_value)                return true;            else                current_value = 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 << ',';        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 on other sites
Quote:
 Original post by AlphaCoderI 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 on other sites
Thank you for your help. I'll have to study these answers for a bit before I understand them but they're clearly what I was looking for.

Share on other sites
Quote:
Original post by DevFred
Quote:
 Original post by AlphaCodernote: 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 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 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.

1. 1
Rutin
36
2. 2
3. 3
4. 4
5. 5

• 12
• 14
• 9
• 9
• 14
• Forum Statistics

• Total Topics
633344
• Total Posts
3011438
• Who's Online (See full list)

There are no registered users currently online

×