Generate all strings of a set, given a range of characters?

Question

I need help with a program for my computer security course; in the program I need to generate all possible combinations of a string given a default set of characters (letters, numbers and a few special characters). I just can't figure out how to get a method that cycles through them all correctly, given a possible length of 1 to 10 characters. I was able to create a simple nested loop that works for 2 digits but figured there must be a better way to scale it to 10 characters that doesn't require just copy pasting the loops over again lol. The first block of code below is my attempt at the 10 digits and the one below is my attempt at 2 digits. Any help, even in understanding how to tackle the problem would be greatly appreciated, Thank you.

String SALTCHARS = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890_$#-~";
    for(int i =1;i<11;i++) {
        String initialPW = StringUtils.repeat("a", i);
        StringBuilder potentialPW = new StringBuilder(initialPW);
        System.out.println("initial ps is "+initialPW);
        for (int j=0;j<67;j++) {

            String letterSwap = Character.toString(SALTCHARS.charAt(j));
            System.out.println("The swap letter is "+letterSwap);
            potentialPW.setCharAt(i-1, SALTCHARS.charAt(j));
            String saltStr = potentialPW.toString();
            System.out.println("The final pw guess is "+ saltStr); 
            for (int k = 0;k<i;k++) {
                potentialPW.setCharAt(k, SALTCHARS.charAt(j));
                saltStr = potentialPW.toString();
                System.out.println("The final pw guess is "+ saltStr); 
            }
        } 
    } 

And here is my attempt at the concept but with 2 characters

String[] possiblePasswords = new String[676];
    int position = 0;
    for (int i = 97;i<123;i++) {
        for (int j = 97;j<123;j++) {
            String firstLetter = Character.toString((char) i);
            String secondLetter = Character.toString((char) j);
            //System.out.println("Test for: "+ firstLetter+secondLetter);
            possiblePasswords[position] = firstLetter + secondLetter;
            position++;
        }
    }

Answer 1

Hmm... interesting?

I think I may have a horrible idea.

To make it simple, I'm just going to use two valid characters A and B. And then, say that we want to generate all possible sequences of those two characters for a string of length 2:

We could represent all possible 2 length strings using a two dimensional array... Then,say we wanted to find all possible 3 length strings...

And then we can get every possible combination of A and B for a string of length 3 by iterating through every element of the 3D array. We know that there are 8 possible outcomes (2^3), and indeed there are 8 'cubes' That will be AAA, AAB, ABA, ABB, BAA, BAB, BBA, BBB.

And so forth... For a string of length 4, create a 4 dimensional array... See, told you it's a horrible idea.

Now you just need to figure out how to populate the array, then you can use something like Array.deepToString to print it all out... It's horrible, but I like the idea of having to go into other dimensions to answer this question.

---

Another Method of Modeling

Another possible method of modeling this question would be to see it as a set of linked wheels (like a flip clock):

(ignore the one frame where the third wheel has 2 B's, that's a mistake :P)

The arrows point to what combination the 'wheels' are set to.

When the first 'wheel' completes it's rotation, it increments the next 'wheel' by 1. This would allow you to cycle through all possible combinations.

This behavior could be achieved by creating a wheel class with a 'value' property and a 'rotation' method. Each time the rotation is called, it'll cycle through it's values. Create a set of these wheel classes, and make it so that when the first wheel completes a full rotation/cycle, it'll increment the second wheel. Then once the second wheel completes a rotation, the third wheel will be called and so on...

Concatenate and print the value of the wheels for every step of the program, and that should work.

Answer 2

You need to use backtracking to generate all combinations of characters over a given length . You need to use recursion if the length of the generated string is not fixed , otherwise you will need to write that many nested loops . I coded up a simple C++ program that does the same . However , there will be a lot of possible combinations for length [1,10] and creating all of them is resulting in a stack overflow on my system ( since I am using recursion ) . But you can go through the code and understand the basic idea of doing this . If you want to execute this code to check it, I suggest you change the value of hi to something low (2-3 maybe) or shrink the domain size to a smaller number of characters , otherwise it will cause stack overflow. (hi denotes the desired upper length of the generated string ).

    #include<bits/stdc++.h>
using namespace std;
void create(int i,string domain,vector<bool>& included,string str,int len)
{
    if(i==(len))
    {
        cout<<str<<endl;
        return;
    }
    for(int j=0;j<domain.length();j++)
    {
        if(included[j]==1)
        continue;
        else
        {
            included[j]=1;
            str+=domain[j];
            create(i+1,domain,included,str,len);
            included[j]=0;
            str.pop_back();
        }
    }
}
int main()
{
    string domain = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890_$#-~";
    int lo=1;
    int hi=10;
    for(int i=lo;i<=hi;i++)
    {
        int len=i;
        string str;
        vector<bool> included(domain.length(),0);
        create(0,domain,included,str,len);
    }
   return 0;
}