All possible combinations for any number of digits and characters

Hey, I have a lab assignment for school in which I have to write a recursive c or c++ function that will send every possible combination of a group of letters and any number of digits to a file.
For example: 5 Chars - 3 Digits would have to look like

Code:

A
B
C
D
E
AA
AB
AC
AD
AE
BA
BB
BC
BD
BE
CA
CB
CC
CD
CE
DA
DB
DC
DD
DE
EA
EB
EC
ED
EE
AAA
AAB
AAC
...
EEE

I've spent a long time thinking about it and don't know how I should do it, whether it be linked lists with recursion or objects oriented. Any thoughts would be great.

I assume you are able to make a flowchart--a general one, at least--for this task? If so, do it. It should be a good start.
It doesn't have to be in "computer language," but merely how you would logically do it in your head or on a piece of paper.

It doesn't look like a good candidate for recursion, but if you must you must. But can you do it non-recursively? That would be a good start.

Originally Posted by Elysia

I assume you are able to make a flowchart--a general one, at least--for this task? If so, do it. It should be a good start.
It doesn't have to be in "computer language," but merely how you would logically do it in your head or on a piece of paper.

Yea I did and the following code was what came from it lol.. It works but its definitely inefficient especially for something like this.

Originally Posted by oogabooga

It doesn't look like a good candidate for recursion, but if you must you must. But can you do it non-recursively? That would be a good start.

Yea it would have been a bunch of nested for loops but I was told unacceptable haha.

Heres the code I came up

Code:

//allPoss will calcualte all possible strings for string pass
//pWalker, curLength, curChar are local recursion variables
//starting from startChar to endChar with the numLength
int allPoss(char * pass, int pWalker, int curLength, int numLength, int startChar, int endChar, int curChar)
{
	if (pass[curLength] < endChar)
	{
		pass[curLength] = curChar;
		cout << pass << endl;
		return allPoss(pass,pWalker,curLength,numLength,startChar,endChar,curChar+1);
	}
	else if(pass[curLength] == endChar && pass[pWalker] == endChar)
	{
		if(curLength == 0)
		{
			pass[pWalker] = startChar;
			return allPoss(pass,curLength,curLength+1,numLength,startChar,endChar,startChar);
		}
		else if(pWalker == 0)
		{
			if(curLength<numLength-1)
			{
				int i;
				for(i=0;i<=curLength;i++)
				{
					pass[i] = startChar;
				}
				return allPoss(pass,curLength,curLength+1,numLength,startChar,endChar,startChar);
			}
		}
		else
		{
			return allPoss(pass,pWalker-1,curLength,numLength,startChar,endChar,pass[pWalker-1]+1);
		}
	}
	else if (pass[pWalker] < endChar)
	{
		pass[pWalker] +=1;
		int i;
		for(i=pWalker+1;i<=curLength;i++)
		{
			pass[i] = startChar;
		}
		return allPoss(pass,curLength-1,curLength,numLength,startChar,endChar,startChar);
	}
	else
		return -1;
}

This code is much more complicated that it needs to be, too. So how does your flowchart look like?

Yea it would have been a bunch of nested for loops but I was told unacceptable haha.

It's possible to do it without a bunch of nested for loops. E.g., you could count in base "number of symbols" + 1, skip any number with a non-leading zero in it, and translate digits to letters. But that's probably not the best way.

In fact, now that I think about it, a recursive implementation is actually a pretty good idea.

Originally Posted by Elysia

This code is much more complicated that it needs to be, too. So how does your flowchart look like?

This is just a rough rough flowchart, I hate them haha

Oh and sorry for the handwriting in advance lol

I think you have the right idea at first, but then it just goes into mumbo-jumbo.

So first we go through all combinations for length l (if l=1, this is very simple).
Then you mention that when we've done all possibilities, we go to the next step.

Clearly, here is where we could do some generalization.
The next step is just the first step with l=2, right? So that implies you probably should have sort of loop back to the beginning if l != final length.
That's a good start. Then you have to think about subdividing the first step into smaller steps with proper loops. It should be similar.

One approach to try is to see what it looks like for l=1, then for l=2, l=3, etc, until you find some general pattern, then try to merge that pattern into some sort of general loop.

Originally Posted by Elysia

I think you have the right idea at first, but then it just goes into mumbo-jumbo.

So first we go through all combinations for length l (if l=1, this is very simple).
Then you mention that when we've done all possibilities, we go to the next step.

Clearly, here is where we could do some generalization.
The next step is just the first step with l=2, right? So that implies you probably should have sort of loop back to the beginning if l != final length.
That's a good start. Then you have to think about subdividing the first step into smaller steps with proper loops. It should be similar.

One approach to try is to see what it looks like for l=1, then for l=2, l=3, etc, until you find some general pattern, then try to merge that pattern into some sort of general loop.

I tried generalizing it a bit more so heres my updated code let me know if you think I'm still missing some things to cut down on.

Code:

//allPoss will calcualte all possible strings for string pass
//pWalker, curLength, curChar are local recursion variables
//starting from startChar to endChar with the numLength
int allPoss(char * pass, int pWalker, int curLength, int numLength, int startChar, int endChar, int curChar)
{
	if(curLength < numLength)
	{
		if (pass[curLength] < endChar)
		{
			pass[curLength] = curChar;
			cout << pass << endl;
			return allPoss(pass,pWalker,curLength,numLength,startChar,endChar,curChar+1);
		}
		else if(pass[pWalker] < endChar)
		{
			pass[pWalker] +=1;
			int i;
			for(i=pWalker+1;i<=curLength;i++)
			{
				pass[i] = startChar;
			}
			return allPoss(pass,curLength,curLength,numLength,startChar,endChar,startChar);
		}
		else if(pWalker > 0)
		{
			return allPoss(pass,pWalker-1,curLength,numLength,startChar,endChar,startChar);
		}
		else
		{
			int j;
			for(j=0;j<=curLength;j++)
			{
				pass[j]=startChar;
			}
			return allPoss(pass,curLength,curLength+1,numLength,startChar,endChar,startChar);
		}
	}
	else
			return -1;
}

Though I cannot speak for the correctness of the code, it's better than before. Still, it's a lot. You realize this can be done iteratively too, right?
So what is your updated flowchart?

How do you call it?
Why is it returning a value? (Why not make it void?)

Originally Posted by oogabooga

How do you call it?
Why is it returning a value? (Why not make it void?)

Yea I made it void type, just forgot to change it.

Ughh the latest code posted here is actually giving me a stack overflow on chars A-D for 6 digits so I'm just going to leave this and come back to it tomorrow. Thanks both of you for help/comments I'll be sure to post some more tomorrow when I run into some problems haha.