Thread: All possible combinations for any number of digits and characters

  1. #1
    Registered User
    Join Date
    Sep 2010
    Location
    Boston, MA
    Posts
    97

    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.
    Last edited by omGeeK; 03-17-2012 at 01:33 PM.

  2. #2
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  3. #3
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    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.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  4. #4
    Registered User
    Join Date
    Sep 2010
    Location
    Boston, MA
    Posts
    97
    Quote Originally Posted by Elysia View Post
    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.

    Quote Originally Posted by oogabooga View Post
    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;
    }
    Last edited by omGeeK; 03-18-2012 at 12:23 PM.

  5. #5
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    This code is much more complicated that it needs to be, too. So how does your flowchart look like?
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  6. #6
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    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.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  7. #7
    Registered User
    Join Date
    Sep 2010
    Location
    Boston, MA
    Posts
    97
    Quote Originally Posted by Elysia View Post
    This code is much more complicated that it needs to be, too. So how does your flowchart look like?
    All possible combinations for any number of digits and characters-tn-jpg

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

    Oh and sorry for the handwriting in advance lol

  8. #8
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  9. #9
    Registered User
    Join Date
    Sep 2010
    Location
    Boston, MA
    Posts
    97
    Quote Originally Posted by Elysia View Post
    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;
    }

  10. #10
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    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?
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  11. #11
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    How do you call it?
    Why is it returning a value? (Why not make it void?)
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  12. #12
    Registered User
    Join Date
    Sep 2010
    Location
    Boston, MA
    Posts
    97
    Quote Originally Posted by oogabooga View Post
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. A3K4 << how many alpha characters and sum of digits?
    By scatterbrain in forum C Programming
    Replies: 3
    Last Post: 12-01-2011, 03:15 PM
  2. Generating number combinations
    By litzkrieg in forum C Programming
    Replies: 23
    Last Post: 03-01-2011, 11:25 AM
  3. Number of digits in a decimal number
    By maverix in forum C Programming
    Replies: 7
    Last Post: 11-04-2007, 12:12 PM
  4. computing the number of combinations
    By clover in forum C Programming
    Replies: 34
    Last Post: 06-06-2004, 01:12 PM
  5. Replies: 10
    Last Post: 01-07-2002, 04:03 PM