Wolfram alpha will tell you that you need ⌈log2(1024!)⌉=8,770 bits in an optimal representation. Not that much better than naively storing the elements themselves. The conceptually easiest way to achieve such a slightly more concise representation is to imagine all those permutations ordered lexicographically. Then you can simply store the index of the permutation in that list. To make this practical, you can iterate over the elements of the permutation, and at each position ask yourself how many permutations there are which have all the preceeding positions in common, but a lesser value at the current position. Summing these numbers will result in the zero-based index for the permutation.
Since you asked about Java code for this, here is a piece of code which will determine the number of bits required, and which will also compute the concise representation for a given permutation.
import java.math.BigInteger;
class SO18757672 {
int n;
BigInteger[] fac;
SO18757672(int n) {
this.n = n;
fac = new BigInteger[n + 1];
fac[0] = BigInteger.ONE;
for (int i = 1; i <= n; ++i)
fac[i] = fac[i - 1].multiply(BigInteger.valueOf(i));
}
int bitsRequired() {
return fac[n].subtract(BigInteger.ONE).bitLength();
}
BigInteger codeFor(int[] permutation) {
if (permutation.length != n)
throw new IllegalArgumentException("wrong length");
BigInteger res = BigInteger.ZERO;
for (int i = 0; i != n; ++i) {
int pi = permutation[i];
if (pi < 0 || pi > n - i)
throw new IllegalArgumentException("invalid value");
res = res.add(fac[n - 1 - i].multiply(BigInteger.valueOf(pi)));
for (int j = i + 1; j != n; ++j) {
if (permutation[j] == pi)
throw new IllegalArgumentException("duplicate value");
if (permutation[j] > pi)
--permutation[j]; // We modify out input!
}
}
return res;
}
boolean sanityChecks() {
int[] p = new int[n];
// smallest code is zero, for all elements in order
for (int i = 0; i != n; ++i)
p[i] = i;
assert BigInteger.ZERO.equals(codeFor(p));
// largest code is n!-1, for all elements in reverse order
for (int i = 0; i != n; ++i)
p[i] = n - 1 - i;
assert fac[n].subtract(BigInteger.ONE).equals(codeFor(p));
return true; // so we can use this in an assert call
}
public static void main(String[] args) {
SO18757672 instance = new SO18757672(1024);
System.out.println(instance.bitsRequired() + " bits required");
assert instance.sanityChecks();
}
}