combination of strings

[shankhs]

I have a problem in printing out the permutation of various characters grouped together like
string 0 has"ABC"
1: "DEF"
2:"GHI"
3:"JKL"
4."MNO"
5."PRS"
6."TUV"
7."WXY"

now i have to print all the permutation of the characters to form 1 letter to 12 letter words
lets say i have 2512
then my possible permutation will be 81 strings like GPDG GPDH GPDI GPEG GPEH GPEI GPFG GPFH GPFI GRDG GRDH GRDI ........

and the number can be even 25123 or longer
so one of the possible approach is recursion:
so I tried:

char rec(string in[],vector<int> brand,int i,int j,int l)
{	
	if(j==l){
		j=0;
		name+=rec(in,brand,++i,++j,l);
		--l;
		return in[brand[i]][j];
	}
	if(l==-1)
	{
		l=2;j=0;i+=1;
	}
	name+=rec(in,brand,i,++j,l);
}

PLZ help me as I am learning recursion by myself and its a very hard topic.......

[bulg]

The best way to start to learn recursion is to check out a Binary tree, and try some of the sorting routines associated w/ them... that should be very easy to understand.

[Duoas]

I don't imagine that recursion and permutations are very safe together without tail recursion.

Use a modulo counter. For example, in the Arabic number system we use we have ten digits for each power.
0 1 2 3 4 5 6 7 8 9

To count through them all, just start counting.

// Print 0123456789... ad infinitum
for (unsigned u = 0; ; u++)
  cout << (u % 10);

Take it one step further, and the thing you print doesn't actually have to be the digit, it can be anything you can index in a ten-element array.

// Print abcdefghij... ad infinitum
char letters[] = "abcdefghij";
for (unsigned u = 0; ; u++)
  cout << letters[ u % 10 ];

The modulus doesn't need to be ten. It can be anything you want, like three.

That should be enough to get you started.

[Compton11]

shanksh, why don't you use the next_permutation() function in the <algorithm> library? I'm not sure if you are allowed to use it for your assignment, but if you can, here's a very helpful link on how to use it:

http://www.cplusplus.com/reference/algorithm/next_permutation.html

Hope this helps...

[shankhs]

hi compton11 thanx for the link look i have 2 reasons not to use next_permutation:
1.I am learnung recursion (dat btw i am doing it by myself no instructor)
2.next_permutation gives permutation of characters in a set not from different sets....
So only technique left is RECURSION.
Thanx for ur help

[shankhs]

hi compton11 thanx for the link look i have 2 reasons not to use next_permutation:
1.I am learnung recursion (dat btw i am doing it by myself no instructor)
2.next_permutation gives permutation of characters in a set not from different sets....
So only technique left is RECURSION.
Ok if u havent understood the question the problem is to permute the characters taking from different sets.....
LIKE if you have to take sets 2512:
then there will be 81 strings of length 4 and characters for every string is taken in order {"char from2","char from 5","char from1","char from2",}(this is one string).....
So i think i am now clear?????
Thanx for ur help

[VernonDozier]

hi compton11 thanx for the link look i have 2 reasons not to use next_permutation:
1.I am learnung recursion (dat btw i am doing it by myself no instructor)
2.next_permutation gives permutation of characters in a set not from different sets....
So only technique left is RECURSION.
Ok if u havent understood the question the problem is to permute the characters taking from different sets.....
LIKE if you have to take sets 2512:
then there will be 81 strings of length 4 and characters for every string is taken in order {"char from2","char from 5","char from1","char from2",}(this is one string).....
So i think i am now clear?????
Thanx for ur help

I understand what you are doing, but I don't understand the algorithm you are trying to implement using that recursive function. For me, at least, I'd need some comments as to what each variable represents and I'd like to see the call from the main function in order to get my hands around what you are trying to do. Somewhere you need a vector of strings (or some other form of storage of multiple strings) unless you are displaying them immediately and not storing them. At some point you end up with 81 (in this case) strings. Where are those strings stored? I see a recursive function that returns a char and uses a variable called name which is apparently defined somewhere, but I don't know where. What is originally calling the rec function and how many times is rec non-recursively called from main or some other function?

[Duoas]

Recursion and iteration are two sides of the same coin.

The difference is, in C++, you have the potential of blowing your stack. So on Windows, if you have more than sizeof(Available RAM + Swap Space)/sizeof(Stack Frame) permutations, you'll crash your computer. Even if you don't get that high though... once you exceed RAM size your program will begin to slow considerably.

All that aside, recursion keeps state ("remembers" things) by passing and returning values.

As a simple example, the Fibonacci sequence is defined as:
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)

A simple iterative solution might look something like

unsigned long long i_fib( unsigned n )
  {
  switch (n)
    {
    case 0: return 0;
    case 1: return 1;
    default:
      unsigned long long f_of_n_minus_1 = 1;
      unsigned long long f_of_n_minus_2 = 0;
      unsigned long long f_of_n         = 1;
      for (; n > 1; n--)
        {
        f_of_n = f_of_n_minus_1 + f_of_n_minus_2;
        f_of_n_minus_2 = f_of_n_minus_1;
        f_of_n_minus_1 = f_of_n;
        }
      return f_of_n;
    }
  }

To make that recursive, we have to identify our state variables: F(n-1), F(n-2), F(n), and of course, n.
The current sum is dependent on the previous iterations, so that should be a return value, while everything else is dependent on 'n'.

So, that same routine in recursion would be

unsigned long long r_fib( unsigned n )
  {
  switch (n) 
    {
    case 0: return 0;
    case 1: return 1;
    default: return r_fib(n-1) + r_fib(n-2)
    }
  }

While this looks prettier, it actually causes a problem: each call to r_fib() generates two additional calls. So the number of times it is called grows exponentially as 'n' gets larger (and threatens to take us to see the BSOD).

So, lets rethink again. The iterative version is very small and fast, whereas the recursive version explodes.
If you look closely, you'll see that the reason is that we essentially compute the value of F(n-1) twice for each call.
We'd sure like to use the power of addition from the iterative version in our recursive version.

You can always stop here and think about it a moment, or just keep on reading.

unsigned long long fib(
  unsigned n,
  unsigned long long f_n_minus_1 = 1,
  unsigned long long f_n_minus_2 = 0
  ) {
  switch (n) 
    {
    case 0:
      return f_n_minus_2;
//  case 1:
//    return f_n_minus_1;
    default:
      unsigned long long f_n = f_n_minus_1 + f_n_minus_2;
      return fib( n-1, f_n, f_n_minus_1 );
    }
  }

In this case, we've kept our additive state in the arguments and done something tricky. We reversed the role of 'n': we count backwards up to F(n). You'll also notice how the final number accumulates into 'f_n_minus_2', so we can just return that. Finally, case 1 becomes completely unnecessary.
I'm sorry if this last one is a little tough, but you'll have to use inductive reasoning to see it. (I'm running out of time so I'm going to wrap up.)

So, why all this post for your problem?
Because it bears directly upon the solution. As I indicated the last time, you can easily generate permutations by counting and modulus. This lends itself to an iterative approach. But, since recursion and iteration are so closely related, you can move things around the same way to make the routine both recursive and efficient.

Identify your state variables, and whether they are dependent on the next iteration or not, then put them in your argument list.

Hope this helps.