java - Transposition Cipher Enumeration

Question

Note: I deleted this post earlier because I found the following post but I'm not sure how to apply it to my problem.

I'm working on a transposition cipher decoder. I have already solved the problem of static columns (1,2,3,4 kept in order), but I'm not sure how to create an array of each possible permutation of a length(Given as a parameter), I understand the easiest way is some kind of recursive method, but whilst attempting this I keep getting lost in the endeavour. (I've been coding all day and am quite tired)

Example array would contain:

1,2,3,4,5,6
2,1,3,4,5,6
2,3,1,4,5,6
...

Answer 1

After being very confused for awhile, and trying a few different things, a friend of mine (Not a user here) gave me the following java solution:

public static void main(String[] args) {
        Nibba nib = new Nibba();
        List<Character> characterSet = new ArrayList<>();
        characterSet.add('1');
        characterSet.add('2');
        characterSet.add('3');
        characterSet.add('4');
        characterSet.add('5');
        characterSet.add('6');

        List<String> perms = nib.generatePermutations(characterSet);
        // filter only the permutations of length 6
        perms = perms.stream().filter(p -> p.length() == characterSet
                .size()).collect(Collectors.toList());
        for (String s : perms) {
            System.out.println(s);
        }
        System.out.println("Total permutations = " + perms.size());
    }

    private List<String> generatePermutations(List<Character> characterSet) {
        List<String> permutations = new ArrayList<>();

        for (int idx = 0; idx < characterSet.size(); idx++) {
            char character = characterSet.get(idx);

            // Initialise first "permutation"
            if (idx == 0) {
                permutations.add(String.valueOf(character));
                continue;
            }

            ArrayList<String> oldPerms = new ArrayList<>(permutations);
            for (String subPermutation : oldPerms) {
                insertPermutations(permutations, subPermutation, character);
            }
        }

        return permutations;
    }

    /**
     * Insert permutations into the given list
     *
     * @param list the list
     * @param str  the string
     * @param c    the character to insert at each point in the string
     */
    private void insertPermutations(List<String> list, String str, char c) {
        for (int i = 0; i <= str.length(); i++) {
            String newStr = str.substring(0, i) + c + str.substring(i);
            list.add(newStr);
        }
    }

Answer 2

Recall that there are n! permutations of n items. The n! can be easily understood in the following way:

1.   There are `n` options for choosing the first item.
2.   There are `n-1` items remaining from which to choose the second item
...
n-1. There are `2` options left for the `n-1`-th item.
n.   There is only 1 item left for the `n`-th position.

Thus there are (n) * (n-1) * (n-2) * ... (2) * (1) = n! total choices for how to order the items.

This directly reveals a method for enumerating the permutations using a mixed-radix numbering scheme. In this scheme, the most-significant digit will be base n, the next-most-significant digit will be base n-1..etc.

You use such a mixed-radix number to select a permutation in the following way:

1. Use the most significant digit to select an element from the array (note that the first digit ranges from [0, n-1], and there are n elements to select from, so you can use it as the index of the item to select.)
2. Remove the selected element from the array, record that it's the first element of the permuted array, and compact the remaining elements to the front of the array.
3. Use the second-most significant digit to select an element from the remaining items (note that the value of this digit ranges from [0, n-2], and there are n-1 digits remaining)
4. Remove the selected element recording it as the second element in the permuted array
5. Repeat until all items have been selected.

If we use an array to represent the mixed-radix number in little-endian digit order, then we would have the following:

int mixed_radix[n] = {0};

You increment this mixed-radix number in the following way:

//Increment the least-significant digit
mixed_radix[0]++;

//Ripple overflow toward the most-significant digit
for(i=0; i<n; i++) {
  if(mixed_radix[i] > i) {
    mixed_radix[i] = 0;
    if(i < n-1)mixed_radix[i+1]++;
  }
  else {
    break;
  }
}

So we have a way to initialize the mixed-radix number to zero, and then increment it through every possible value, stopping once it wraps back around to zero. (or after n!-1 increments...)

All that said, there's a lovely numerical trick that can make this even simpler: You can unpack that ugly mixed-radix number from an integer in the following way:

We know that there are n! permutations of n items; for any integer val in the range [0, n!-1] the following provides a bijective mapping between the integer value and a mixed-radix number:

int working = val;  //val in the range [0, n!-1]
for(j=0 j<n; j++) {
  mixed_radix[j] = working % (j+1);
  working /= (j+1);
}

So embedding this "unpacking" loop within an outer loop that runs val over the range 0 to n!-1 is a much denser method to enumerate the mixed-radix numbers (which enumerates the possible permutations). It also assigns an integer to each permutation, effectively naming them. :)