Soft Coding.

[Cruncher]

import java.util.Random;
public class StringPossibilities
{
    static char[] letters = new char [4];
    static Random gen = new Random ();
    public static void main (String[] args)
    {
        for (int i = 0 ; i < 4 ; i++)
            letters [i] = ((char) ((gen.nextInt (26) + 97)));
        for (int i = 0 ; i < 4 ; i++)
        {
            for (int j = 0 ; j < 4 ; j++)
            {
                for (int k = 0 ; k < 4 ; k++)
                {
                    for (int l = 0 ; l < 4 ; l++)
                    {
                        if (!duplicates (new int[] {i, j, k, l}))
                        {
                            System.out.println (stringOrder (letters, new int[]{i, j, k, l}));
                        }
                    }
                }
            }
        }
    }

    static public String stringOrder (char[] chars, int[] order)
    {
        if (chars.length == order.length)
        {
            char[] newChars = new char [chars.length];
            for (int i = 0 ; i < newChars.length ; i++)
            {
                newChars [i] = chars [order [i]];
            }
            return new String (newChars);
        }
        else
        {
            return "unacceptable parameters";
        }
    }

    static public boolean duplicates (int[] array)
    {
        for (int i = 0 ; i < array.length ; i++)
        {
            for (int j = i+1 ; j < array.length ; j++)
            {
                if (array [i] == array [j])
                {
                    return true;
                }
            }
        }
        return false;
    }
}

Okay, this code makes a random char array of length 4, and prints all 24(4!) possible strings with those 4 characters.

This is good for my assignment, this is all that is asked, however I have never been satisfied with just completeing enough for this class.

So how could i softcode this to work with any length of char array?

Thanks.

[Cruncher]

I was thinking recursion, but my head has been spinning trying to come with an exact implementation.

[gcalvin]

OK, you want to generate a list of permutations, so let's start with a method signature that returns a list:

[B]        public List<String> listPermutations(String input) {
        }
[/B]

Recursion is not a bad idea here. The idea of recursion is
1. Identify a base case from which we know that no more recursion is needed, and return a simple result.
2. For all other cases, do the simple part, and let the next recursive call do the hard part.
3. Make sure that the modifications we make to our parameters will tend toward the base case, so that we'll reach termination at some point.

When generating permutations of a String, the base case is a one-character (or zero-character) String, that has only one permutation.

        public List<String> listPermutations(String input) {
[B]                List<String> results = new ArrayList<String>();
                if (input.length() <= 1) {
                        results.add(input);
                }
                return results;
[/B]        }

Now let's think about a concrete example to make the next part more understandable. Let's say we start with the String "ABCD". Our list of permutations will have some Strings that start with "A", followed by each permutation of "BCD", then Strings that start with "B", followed by each permutation of "ACD", then Strings that start with "C", followed by each permutation of "ABD", then finally Strings that start with "D", followed by each permutation of "ABC". So that means we want to loop through our original String, and for each character, get the permutations of the remaining String and prepend our character to each of them. (We're removing one character from our String, so we know eventually the input String will have a length of 1.)

        public List<String> listPermutations(String input) {
                List<String> results = new ArrayList<String>();
                if (input.length() <= 1) {
                        results.add(input);
[B]                } else {
                        for (int i = 0; i < input.length(); i++) {
                                char c = input.charAt(i);
                                String remainder = input.substring(0, i) + input.substring(i + 1);
                                for (String s : listPermutations(remainder)) {
                                        results.add(c + s);
                                }
                        }
[/B]                }
                return results;
        }

That's it. The funny thing about writing recursive methods is that you're usually done before you think you're done. :)

-Gary-

[JosAH]

If you want to generate permutations in lexicographical order you don't need recursion at all. There is a simple iterative algorithm that also works if there are duplicates in your 'set'; here's how it works:

given a set p_1, p_2, p_3 ... p_n that is marked as the 'current' permutation;

1) find the rightmost i such that p_i < p_(i+1);
2) if no such i can be found there is no 'next' permutation given the 'current' one;
3) find the rightmost j > i such that p_j > p_i; note that such j always exists;
4) swap the elements p_i and p_j;
5) reverse the elements p_(i+1) ... p_n.

after these five steps have completed succesfully you have found a next permutation; repeat those steps until step 2) fails.

Here's a small example: given the permutation ACDEB; step 1) says that p_i == D (D < E); and step 3) says that p_j == E (E > D); step 4) results in: ACEDB and step 5) results in ACEBD which is the next permutation for ACDEB in lexicographical order. If you start with ABCDE, apply the above algorithm ad nauseam you'll find all the permutations of ABCDE.

kind regards,

Jos

[Cruncher]

Thanks guys,

too tired to really try/understand it at the moment, but i will later lol.

[gcalvin]

My version will generate duplicates. To eliminate them, you could use a HashSet<String> instead of an ArrayList<String>.

The big advantage of JosAH's approach is that there is no need to keep a list of existing permutations in memory, which the recursive approach requires. You can do everything with the one char array, printing out the permutations (or writing them to a file, if you prefer) as you go. This means you can permute much longer Strings.

-Gary-