By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
455,806 Members | 1,380 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 455,806 IT Pros & Developers. It's quick & easy.

Finding all possible combinations - Simplifying many for loops into one

P: 1
Hello Everyone, this is my first post on these forums, mostly because I never thought I would get this stumped ever and never had to really post on a Java forum before. So, to try and push myself harder in the Java world, I wanted to make a program that found all possible combinations of characters. I thought it would be kind of cool. I got it mostly, but it turned out to be a lot harder than I suspected ever. I commented it out to help anyone that might be reading this. Basically, what it does so far, is for each for loop added, it goes up a character in what it generates. Not how I intended it to work at all. What I want it to do is change the length based on a variable called Length. I've been working more then 2 hours trying to solve this issue, to no avail
Here's my current code that I'm using:
What it does is it actively writes the results to a file on my Desktop called test.txt.
I current have 3 for loops set on it, which by the dumb principles on my programming, means a 3 char limit.
Expand|Select|Wrap|Line Numbers
  1. import java.io.FileOutputStream;
  2. import java.io.IOException;
  3. import java.io.OutputStreamWriter;
  4.  
  5. public class Generate {
  6.     public static void Gen() throws IOException
  7.     {
  8.         //opens a file writing stream
  9.         FileOutputStream fos = new FileOutputStream("C:\\Users\\Ryan\\Desktop\\test.txt"); 
  10.         OutputStreamWriter out = new OutputStreamWriter(fos, "UTF-8");
  11.         //the character list I'm using
  12.         String CharList = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
  13.         //gets a list of characters
  14.         String[] CharSplit = CharList.split("");
  15.         String Str = "";
  16.         //generates text document on my desktop of possible combinations
  17.         //only currently a max length of 3 since I have no idea how to simulate more for loops or what not
  18.         //notice that 3 for loops = char length of 3
  19.         for(int I = 1;I<CharSplit.length;I++)
  20.         {
  21.             //takes up first character
  22.             Str += CharSplit[i];
  23.             //writes it to a file, along with a separation to the next line
  24.             out.write(Str + System.getProperty("line.separator"));
  25.             //clears Str for further use
  26.             Str = "";
  27.             for(int O = 1;O<CharSplit.length;O++)
  28.             {
  29.                 //writes 2 pieces into Str for a 2 char length
  30.                 Str += CharSplit[i] + CharSplit[O];
  31.                 //writes to file along with a new line
  32.                 out.write(Str + System.getProperty("line.separator"));
  33.                 //clears Str
  34.                 Str = "";
  35.                 for(int P = 1;P<CharSplit.length;P++)
  36.                 {
  37.                     //writes 3 pieces into Str for a 3 char length
  38.                     Str += CharSplit[i] + CharSplit[O] + CharSplit[P];
  39.                     //writes to file along with new line
  40.                     out.write(Str + System.getProperty("line.separator"));
  41.                     //clears Str
  42.                     Str = "";
  43.                 }
  44.             }
  45.         }
  46.         //closes the file writing stream
  47.         out.close(); 
  48.     }
  49. }
  50. /*
  51. How can I simplify the for loops so that they are more customizable?
  52. Ex:
  53. A variable called Length controls the maximum length, no need to paste in new for loops
  54. */
  55.  
As you can see, it's rediculasly long and hard to change the length. Does anyone have any idea how to simplify this into say, one for loop able to be changed on a variable? What would I have to do? I'm very completely stumped.
Apr 7 '12 #1
Share this Question
Share on Google+
4 Replies


Rabbit
Expert Mod 10K+
P: 12,422
You can't do it in only one loop but you can make it more dynamic.

Something along the lines of this
Expand|Select|Wrap|Line Numbers
  1. pw = initial pw
  2. output pw
  3.  
  4. loop until length of pw exceeds max length
  5.    increment first character of pw
  6.  
  7.    loop through each character in pw
  8.       if character is beyond last allowable character
  9.          reset to first character
  10.          increment next character
  11.       else 
  12.          exit loop
  13.       end if
  14.    end loop
  15.  
  16.    ouput pw
  17. end loop
Apr 7 '12 #2

P: 62
Just a correction to the above post, when you "loop through each character in pw", and reach the last character, and this last "character is beyond last allowable character", you need to add a new character, the first allowable character, to the back of pw, instead of "incrementing next character".

I probably would not do it the above way though. I would implement a simple recursive solution - create a new function that (1) prints the current string (2) (if string is not at maximum length) goes through all possible characters to add to the end of the string and calls itself recursively. This is the pseudo-code in javascript:
Expand|Select|Wrap|Line Numbers
  1. var str="",acceptable_chars="abcd",max_length=4,allstr=[];
  2. function printLn(str)
  3. {
  4.     allstr.push(str);
  5. }
  6. function makestr()
  7. {
  8.     printLn(str); // generic print function
  9.     if( str.length==max_length ) return;
  10.     for(var a=0;a<acceptable_chars.length;a++)
  11.     {
  12.         str+=acceptable_chars.charAt(a); // add a possible last character
  13.         makestr();
  14.         str=str.slice(0,-1); // pluck off the last character added two lines above
  15.     }
  16. }
  17. makestr();
  18. alert(allstr);
  19.  
Edit: Changed function name from "do" to "makestr" as "do" is a keyword... :P.

Edit: Earlier code crashed because "str.slice(-1)" did NOT truncate the last character of the string. It should be "str.slice(0,-1)". Interestingly, it crashed Firefox completely when I ran it in Scratchpad.
Apr 7 '12 #3

Rabbit
Expert Mod 10K+
P: 12,422
A recursive solution will spiral out of control. If his goal is to get all possible combinations of characters, and from his post, he wants at least 4 characters, probably more, then even if we limit to the character set available on a standard keyboard, that's 88.5 million combinations at 4 characters. Add a bunch more if you want to use the full ASCII character set. Add a ton more if you want more than 4 characters.
Apr 7 '12 #4

P: 62
Your solution also will. It's similarly exponential. If you're talking about stack space, in the recursive solution, stack space used is linear in number of characters.
Apr 7 '12 #5

Post your reply

Sign in to post your reply or Sign up for a free account.