Loops

[Chris Pocock]

I was just wondering, how would you write a for loop to decode a String by trying every possible combination of numbers/letters?
eg.

final int min = 3;
final int max = 15;
String thing = "Hello123";
String test;
for( \* What to put here? *\ )
{
   if (test == thing)
   {
       // return success
   }
}

Something like that I guess. I'm still trying to figure out this problem. Can anybody help me or give me any hints? Am I doing this totally wrong?
Thanks
-Chris
[ April 03, 2002: Message edited by: Chris Pocock ]

[James Swan]

There were a couple of cool algorithms posted yesterday by Brent Worden for performing combinations and permutations (implemented in C++ too).
They could be well worth a look.
http://www.javaranch.com/cgi-bin/ubb/ultimatebb.cgi?ubb=get_topic&f=33&t=005058
James.

[Chris Pocock]

The algorithm from that link that was in that guys post didn't look like it would help me out... I edited my original post to make the code better (I was in a rush before).
I'm still (very) open to any help .
Thanks heaps
-Chris

[James Swan]

I thought those algorithms were almost spot on for what you're trying to do (brute force approach).
If you look at a definition of what a permutation is (it's been 10 or so years so I did Mathematics so I had to look it up):
http://mathforum.org/dr.math/faq/faq.comb.perm.html
Those algorithm's will return you the possible values in a permutation (given the right input).
Ok, as I said my math is a little out but Ill give it a shot anyway.
Lets say you have a "password" of length 5, that can be any combination of "lowercase letters" and numbers (ie. a..z 0..9)
So the number of possible permutations of that password is:
36_P_5 = 36! / (36 - 5)! = 45,239,040
My understanding that those algorithms posted would actually return in each iteration a particular set of values.
In the above case there would be ~45 Million iterations.
Please feel free to flame if my Math is incorrect.

[James Swan]

Ok I had to try it for myself:

public class GuessPassword {
    private static final char[] possibleValues = {'a','b','c','d','e','f','g','h',
                                                    'i','j','k','l','m','n','o','p',
                                                    'q','r','s','t','u','v','w','x',
                                                    'y','z','0','1','2','3','4','5',
                                                    '6','7','8','9'};
    
    private static final int MAX_PASSWORD_LENGTH = 3;
    public static void main(String[] args) {
        // to make it easy, and quick password is of length 3
        String password = "js1";
        int[] perm = new int[possibleValues.length];
        perm[0] = -1;
        int guessNumber = 0;
        while (enumeratePermutations(possibleValues.length,MAX_PASSWORD_LENGTH,perm)) {
            guessNumber++;
            // do something with perm[0..4]
            StringBuffer guess = new StringBuffer();
            guess.append(possibleValues[perm[0]]).append(possibleValues[perm[1]]).append(possibleValues[perm[2]]);
            //System.out.println(guess.toString());
            if (guess.toString().equals(password)) {
                System.out.println("Your password was " + guess.toString() + ", guessed after " + guessNumber + " tries");
                break;
            }
        }
    }
    public static boolean enumeratePermutations(int n, int k, int j[])
    /*-------------------------------------------------------------------
     Description:
       Enumerates all possible permutations of choosing k objects from n
       distint objects.  Initialize the enumeration by setting j[0] to a
       negative value.  Then, each call to enumeratePermutations will
       generate the next permutation and place it in j[0..k-1].  A return
       value of false indicates there are no more permutations to
       generate.  j needs to be allocated with a size for at least n
       elements.
    
     Author:
       Brent Worden
    
     Language:
       C++
    
     Usage:
       int perm[10] = {-1};
       while(enumeratePermutations(10, 5, perm)){
           // do something with perm[0..4]
       }
    
     Reference:
       Tucker, Allen.  Applied Combinatorics.  3rd Ed.  1994.
    -------------------------------------------------------------------*/
    {
        int i;
        if(j[0] < 0){
            for(i = 0; i < n; ++i){
                j[i] = i;
            }
            int start = k;
            int end = n - 1;
            int t;
            while(start < end){
                t = j[start];
                j[start++] = j[end];
                j[end--] = t;
            }
            return true;
        } else {
            for(i = n - 2; i >= 0 && j[i] >= j[i+1]; --i){}
            if(i < 0){
                return false;
            } else {
                int least = i + 1;
                for(int m = i + 2; m < n; ++m){
                    if(j[m] < j[least] && j[m] > j[i]){
                        least = m;
                    }
                }
                int t = j[i];
                j[i] = j[least];
                j[least] = t;
                if(k - 1 > i){
                    int start = i + 1;
                    int end = n - 1;
                    while(start < end){
                        t = j[start];
                        j[start++] = j[end];
                        j[end--] = t;
                    }
                    start = k;
                    end = n - 1;
                    while(start < end){
                        t = j[start];
                        j[start++] = j[end];
                        j[end--] = t;
                    }
                }
                return true;
            }
        }
    }
}

You should get output:
Your password was js1, guessed after 11314 tries
[ April 04, 2002: Message edited by: james swan ]