How to return all array permutations iteratively into a two-dimensional array?

I am trying to write a program that will iterate through all possible permutations of a String array, and return a two dimensional array with all the permutations. Specifically, I am trying to use a String array of length 4 to return a 2D array with 24 rows and 4 columns.

I have only found ways to print the Strings iteratively but not use them in an array. I have also found recursive ways of doing it, but they do not work, as I am using this code with others, and the recursive function is much more difficult.

For what I want the code to do, I know the header should be:

public class Permutation
{
     public String[][] arrayPermutation(String[] str)
     {
          //code to return 2D array
     }
}

//I tried using a recursive method with heap’s algorithm, but it is very //complex with its parameters.

I am very new to programming and any help would be greatly appreciated.

Answer

Your permutation-problem is basically just an index-permutation problem. If you can order the numbers from 0 to n – 1 in all possible variations, you can use them as indexes of your input array, and simply copy the Strings. The following algorithm is not optimal, but it is graphic enough to explain and implement iteratively.

public static String[][] getAllPermutations(String[] str) {
    LinkedList<Integer> current = new LinkedList<>();
    LinkedList<Integer[]> permutations = new LinkedList<>();

    int length = str.length;
    current.add(-1);

    while (!current.isEmpty()) {
        // increment from the last position.
        int position = Integer.MAX_VALUE;
        position = getNextUnused(current, current.pop() + 1);
        while (position >= length && !current.isEmpty()) {
            position = getNextUnused(current, current.pop() + 1);
        }
        if (position < length) {
            current.push(position);
        } else {
            break;
        }

        // fill with all available indexes.
        while (current.size() < length) {
            // find first unused index.
            int unused = getNextUnused(current, 0);

            current.push(unused);
        }
        // record result row.
        permutations.add(current.toArray(new Integer[0]));
    }

    // select the right String, based on the index-permutation done before.
    int numPermutations = permutations.size();
    String[][] result = new String[numPermutations][length];
    for (int i = 0; i < numPermutations; ++i) {
        Integer[] indexes = permutations.get(i);
        String[] row = new String[length];
        for (int d = 0; d < length; ++d) {
            row[d] = str[indexes[d]];
        }
        result[i] = row;
    }

    return result;
}

public static int getNextUnused(LinkedList<Integer> used, Integer current) {
    int unused = current != null ? current : 0;
    while (used.contains(unused)) {
        ++unused;
    }
    return unused;
}

The getAllPermutations-method is organized in an initialization part, a loop collecting all permutations (numeric), and finally a convertion of the found index-permutation into the String-permutations.

As the convertion from int to String is trivial, I’ll just explain the collection part. The loop iterates as long, as the representation is not completely depleted, or terminated from within.

First, we increment the representation (current). For that, we take the last ‘digit’ and increment it to the next free value. Then we pop, if we are above length, and look at the next digit (and increment it). We continue this, until we hit a legal value (one below length).

After that, we fill the remainder of the digits with all still remaining digits. That done, we store the current representation to the list of arrays.

This algorithm is not optimal in terms of runtime! Heap is faster. But implementing Heap’s iteratively requires a non-trivial stack which is tiresome to implement/explain.