Mathematical method to produce an integer containing array (permutation)

Question

I need a mathematical function that produces arrays containing all variants of some integers, so called permutation, e.g.:

private static final int[][] a = {{1}};
private static final int[][] b = {{1,2},{2,1}};
private static final int[][] c = {{1,2,3},{3,2,1},{2,1,3},{3,1,2},{1,3,2},{2,3,1}};
private static final int[][] d = {{1,2,3,4},{1,2,4,3},...};

It should be possible to produce arrays up to hundred {{1,2,3,....100},{...}} or more if manageable.

Do you know any formula or algorithm that can produce such arrays?

Answer 1

http://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order

You could follow the algorithm given there for an array containing {1..k}, (copying each permutation to a new array as you go), and doing the same with {1..k+1}, and so on.

However, there might be a more efficient method since the possibilities for {1..k} will be the results for {1..k-1} with k inserted at each possible position.

Consider what you plan on doing with them, however. If you only want some of the permutations, you don't need to be storing them all in memory, so you could modify your function to only return the nth permutation, or implement an iterator which doesn't do any copying of the array and then let the calling code decide when to copy. You certainly aren't going to be able to store 100! arrays of size 100. If my math is right, for N=12 you are already talking about over 20 GB of space to store all of them (and that's not even including the ones up to N-1).