Get all combinations of Strings

Question

I have requirement that need to get all combinations of given Strings. For example I have a String of digits and some special charcters

String chars="0123456789@#$%&";
String guessedPw="authentic";

So I want to get combinations like this

1. $authentic%4
2. authentic#@
3. 5&authentic
4. authentic8

How should I improve my method to get all combinations?

This is the code that I have written.

but it doesn't give me all combinations.

private static String combination(String prefix, String s, String pw, String md5Pw) {
    String pwFound = "";
    if (s.length() > 0) {
        // System.out.println(prefix + s.charAt(0) + pw);

        String tempPw1 = prefix + s.charAt(0) + pw;
        System.out.println("pw1 : " + tempPw1);
        if (md5(tempPw1).equals(md5Pw)) {
            // String tempPw1;
            pwFound = tempPw1;

            return pwFound;

        }

        String tempPw2 = pw + prefix + s.charAt(0);


        if (md5(tempPw2).equals(md5Pw)) {
            // String tempPw1;
            pwFound = tempPw2;
            return pwFound;

        }

        pwFound = combination(prefix + s.charAt(0), s.substring(1), pw, md5Pw);
        pwFound = combination(prefix, s.substring(1), pw, md5Pw);
    }
    return pwFound;
}

Answer 1

Just if you don't want write own algo, you can use google.

Try to search for: "Generate Permutations".

For example, on this link: Generate all combinations from multiple lists there is a algo which you can use it (but with list).

void GeneratePermutations(List<List<Character>> Lists, List<String> result, int depth, String current)
{
    if(depth == Lists.size())
    {
       result.add(current);
       return;
     }

    for(int i = 0; i < Lists.get(depth).size(); ++i)
    {
        GeneratePermutations(Lists, result, depth + 1, current + Lists.get(depth).get(i));
    }
}

But sure, there are a lot of other ways.

Answer 2

If you want to code everything by your own then this is how you should approach your problem =>
Have a special character say ~ to denote guessedPw, and create another string say str = chars + "~".
Now first you need to look for all possible combinations of str, finding which will take exponential time , and then for each found combination, you should generate all it's permutation , which is again factorial time complex.
And then in the final string , you should replace all the occurrence of '~' with guessedPw, and get the answer string. Here you go for the link for generating permutations and combinations :
Link : http://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/
To find out combinations , you can use bit-masking if you have at max. 64 characters in the string , combinations from which you want to extract.

Answer 3

To make new combination, you can add one char as prefix or add one char as suffix. To avoid repeats, stop adding prefix when suffix exists

Pseudocode:

GenPass(CurrentString, boolAllowPrefix)

    check CurrentString, return it if good result

    check length limit, exit if too long

    for c in Chars 
        if (boolAllowPrefix)
             GenPass(Chars[i] + CurrentString, True)
        GenPass(s + Chars[i], False)

Delphi implementation to check

procedure GenPass(s: string; bPrefix: Boolean);
var
  i: integer;
begin
  List.Add(s);
  if Length(s) = MaxLen then
    Exit;
  if bPrefix then
     for i := 1 to Length(Chars) do
        GenPass(Chars[i] + s, True);
   for i := 1 to Length(Chars) do
       GenPass(s + Chars[i], False);

end;