Generating permutations can be quite tedious, especially when the number is large. The traditional way is to instantiate all at once, then retrieve each when needed. This, however, requires vast quantities of memory for very large sets, thus making them impractical in most research settings. For example, let the character set be the English alphabet and size of each permutation \(k=8\). This results in \(26^{8}*sizeof(char)=388.97\) GB of memory (not factoring in Java Object overhead). This example is essentially the cost of storing all of the lowercase passwords of size 8 for a brute force attack. Obviously, this is not feasible using traditional methods. In this posting, I will demonstrate how to generate each permutation without memory. For completeness, I will begin with the code for generating all permutations first.
Generate all
The following Java class generates all possible permutations at once, then returns the list of permutations to the calling method. The use of this class is quite simple. First, instantiate the class by passing the character set \(chars\) and length of permutation \(k\) to the constructor. Then, call getPermutations() to create and retrieve the permutations.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* Generates all permutations given a character set and length of permutation.
* This class works well for a small number of permutations. However, as the
* size increases, it becomes prohibitively expensive or even impossible to
* create due to memory consumption. For large sets, see
* {@link PermutationsIndividual} and {@link PermutationsIndividualPreComputed}.
* @author Ray Hylock
*/
public class PermutationsAll {
private String chars;
private int k;
/**
* Creates a new instance of {@link PermutationsAll } given the character set
* and length of permutation.
* @param chars the character set
* @param k the length of each permutation
*/
public PermutationsAll(final String chars, final int k) {
this.chars = chars;
this.k = k;
}
/**
* Generates all permutations and returns a {@link List} of permutations,
* each as a {@code char[]}.
* @return a {@link List} of permutations, each as a {@code char[]}
*/
public List<char[]> getPermutations() {
int l = chars.length();
int permutations = (int) Math.pow(l, k);
char[][] p = new char[permutations][k];
// generate permutations
for (int w = 0; w < k; w++) {
int s = (int) Math.pow(l, w);
for (int x = 0; x < permutations;) {
for (int y = 0; y < l; y++) {
for (int z = 0; z < s; z++) {
p[x][w] = chars.charAt(y);
x++;
}
}
}
}
// create output
List<char[]> result = new ArrayList<char[]>();
result.addAll(Arrays.asList(p));
return result;
}
}Test class.
import java.util.List;
public class PermutationsAllTest {
public static void main(String[] args) {
String chars = "ABCDEFGHIJ";
int k = 7;
PermutationsAll perm = new PermutationsAll (chars, k);
List<char[]> v = perm.getPermutations();
for (char[] s : v) {
System.out.println(String.valueOf(s));
}
}
}Generate direct/iterator
The following Java class generates each permutation independently of all others. It will allow iteration or random generation via a direct approach. The use of this class is quite simple as well. First, instantiate the class by passing the character set \(chars\) and length of permutation \(k\) to the constructor. If you wish to use direct index access, then call the get(index) function. For iteration, check if the i+1 value exists via hasNext(). If true, then getNext() will retrieve the next permutation in the set. You may also reset the iterator for subsequent searches (resetIterator). As both the direct and iterator approach have zero memory footprint, this class may serve multiple inputs via set(chars, k).
Computing permutation \(i\) given \(chars\) and \(k\) is accomplished as follows:
\[permutation(i)=\biguplus_{j=0…k-1}chars\left[\left\lfloor{\frac{i}{n^{j}}}\right\rfloor\%n\right]\]
where \(n\) is the size of the character set (i.e., \(|chars|\)) and \(\uplus\) represents a character appending function.
/**
* Generates permutations one at a time given a character set and length of
* permutation. This class is a first attempt at on-demand permutation
* computing. It is slower than {@link PermutationsAll}, but has a minimal
* footprint. The optimized version of this attempt is
* {@link PermutationsIndividualPreComputed}.
* @author Ray Hylock
*/
public class PermutationsIndividual {
private char[] chars;
private int k;
private int n;
private long MAX;
private long iteratorIndex;
/**
* Creates a new instance of {@link PermutationsIndividual} given the
* character set and length of permutation.
* @param chars the character set
* @param k the length of each permutation
*/
public PermutationsIndividual(final String chars, final int k){
set(chars, k);
}
/**
* Gets the permutations for the index {@code i}.
* @param i index position of the permutation to generate
* @return the permutation
*/
private char[] getPermutation(final long i){
if(i >= MAX) {
throw new IndexOutOfBoundsException("Permutation " + i + " is "
+ " greater than the maximum number of permutations " + MAX
+ "(0..." + (MAX-1) + ").");
} else {
char[] p = new char[k];
for(int j=0; j<k; j++){
p[j] = chars[(int)(Math.floor(i/Math.pow(n,j))%n)];
}
return p;
}
}
/**
* Returns {@code true} if the permutation matches the comparison value,
* {@code false} otherwise.
* @param i index position of the permutation to generate
* @param compare the comparison value
* @return {@code true} if the permutation matches the comparison value,
* {@code false} otherwise.
*/
private boolean getPermutation(final long i, final char[] compare){
if(i >= MAX) {
throw new IndexOutOfBoundsException("Permutation " + i + " is "
+ " greater than the maximum number of permutations " + MAX
+ "(0..." + (MAX-1) + ").");
} else {
if(k != compare.length) return false;
for(int j=0; j<k; j++){
if(compare[j] != chars[(int)(Math.floor(i/Math.pow(n,j))%n)])
return false;
}
return true;
}
}
/**************************************************************
* ITERATOR METHODS *
**************************************************************/
/**
* Returns {@code true} if there is another permutation available based on
* previous {@link #getNext()} calls, {@code false} otherwise.
* @return {@code true} if there is another permutation available,
* {@code false} otherwise.
*/
public boolean hasNext(){
return (iteratorIndex + 1 < MAX);
}
/**
* Returns the next permutation in the iterator.
* @return the next permutation in the iterator.
*/
public char[] getNext(){
return getPermutation(++iteratorIndex);
}
/**
* Resets the iterator.
*/
public void resetIterator(){
iteratorIndex = -1L;
}
/**************************************************************
* DIRECT METHODS *
**************************************************************/
/**
* Returns the {@code i}th permutation.
* @param i index position of the permutation to generate
* @return the {@code i}th permutation
*/
public char[] get(final long i){
return getPermutation(i);
}
/**
* Returns {@code true} if the {@code i}th permutation matches the
* comparison value, {@code false} otherwise.
* @param i index position of the permutation to generate
* @param compare the comparison value
* @return {@code true} if the permutation matches the comparison value,
* {@code false} otherwise.
*/
public boolean get(final long i, final char[] compare){
return getPermutation(i, compare);
}
/**************************************************************
* UTILITY METHODS *
**************************************************************/
/**
* Sets the character set and permutation length.
* @param chars the character set
* @param k the length of each permutation
*/
public void set(final String chars, final int k){
this.iteratorIndex = -1L;
this.chars = chars.toCharArray();
this.k = k;
this.n = chars.length();
this.MAX = (long) Math.pow(n, k);
}
/**
* Returns the maximum number of permutations possible given the input.
* @return the maximum number of permutations possible given the input
*/
public long getMax(){
return this.MAX;
}
}Test class using direct index calls.
import java.util.List;
public class PermutationsIndividualTest {
public static void main(String[] args) {
String chars = "ABCDEFGHIJ";
int k = 7;
PermutationsIndividual perm =
new PermutationsIndividual(chars, k);
long max = perm.getMax();
for(long i=0; i<max; i++) {
System.out.println(String.valueOf(perm.get(i)));
}
}
}Test class using iterator calls.
import java.util.List;
public class PermutationsIndividualIteratorTest {
public static void main(String[] args) {
String chars = "ABCDEFGHIJ";
int k = 7;
PermutationsIndividual perm =
new PermutationsIndividual(chars, k);
while(perm.hasNext()) {
System.out.println(String.valueOf(perm.getNext()));
}
}
}Generate direct/iterator optimized
Generate direct/iterator can be optimized by pre-computing and storing \(n^{j}\) \(\forall j=0,…,k-1\). This vector is only of size \(k\) longs, which is measured in bytes. The gain, however, is significant over the base version.
/**
* Generates permutations one at a time given a character set and length of
* permutation. This class is at least as fast as {@link PermutationsAll} with
* a memory footprint equivalent to {@link PermutationsIndividual}. Thus, this
* is the fastest and smallest implementation, and should be used by default.
* @author Ray Hylock
*/
public class PermutationsIndividualPreComputed {
private char[] chars;
private int k;
private int n;
private long MAX;
private long iteratorIndex;
private double[] preComp;
/**
* Creates a new instance of {@link PermutationsIndividualPreComputed}
* given the character set and length of permutation.
* @param chars the character set
* @param k the length of each permutation
*/
public PermutationsIndividualPreComputed(final String chars, final int k){
set(chars, k);
}
/**
* Gets the permutations for the index {@code i}.
* @param i index position of the permutation to generate
* @return the permutation
*/
private char[] getPermutation(final long i){
if(i >= MAX) {
throw new IndexOutOfBoundsException("Permutation " + i + " is "
+ " greater than the maximum number of permutations " + MAX
+ "(0..." + (MAX-1) + ").");
} else {
char[] p = new char[k];
for(int j=0; j<k; j++){
p[j] = chars[(int)(Math.floor(i/preComp[j])%n)];
}
return p;
}
}
/**
* Returns {@code true} if the permutation matches the comparison value,
* {@code false} otherwise.
* @param i index position of the permutation to generate
* @param compare the comparison value
* @return {@code true} if the permutation matches the comparison value,
* {@code false} otherwise.
*/
private boolean getPermutation(final long i, final char[] compare){
if(i >= MAX) {
throw new IndexOutOfBoundsException("Permutation " + i + " is "
+ " greater than the maximum number of permutations " + MAX
+ "(0..." + (MAX-1) + ").");
} else {
if(k != compare.length) return false;
for(int j=0; j<k; j++){
if(compare[j] != chars[(int)(Math.floor(i/preComp[j])%n)])
return false;
}
return true;
}
}
/**************************************************************
* ITERATOR METHODS *
**************************************************************/
/**
* Returns {@code true} if there is another permutation available based on
* previous {@link #getNext()} calls, {@code false} otherwise.
* @return {@code true} if there is another permutation available,
* {@code false} otherwise.
*/
public boolean hasNext(){
return (iteratorIndex + 1 < MAX);
}
/**
* Returns the next permutation in the iterator.
* @return the next permutation in the iterator.
*/
public char[] getNext(){
return getPermutation(++iteratorIndex);
}
/**
* Resets the iterator.
*/
public void resetIterator(){
iteratorIndex = -1L;
}
/**************************************************************
* DIRECT METHODS *
**************************************************************/
/**
* Returns the {@code i}th permutation.
* @param i index position of the permutation to generate
* @return the {@code i}th permutation
*/
public char[] get(final long i){
return getPermutation(i);
}
/**
* Returns {@code true} if the {@code i}th permutation matches the
* comparison value, {@code false} otherwise.
* @param i index position of the permutation to generate
* @param compare the comparison value
* @return {@code true} if the permutation matches the comparison value,
* {@code false} otherwise.
*/
public boolean get(final long i, final char[] compare){
return getPermutation(i, compare);
}
/**************************************************************
* UTILITY METHODS *
**************************************************************/
/**
* Sets the character set and permutation length.
* @param chars the character set
* @param k the length of each permutation
*/
public void set(final String chars, final int k){
this.iteratorIndex = -1L;
this.chars = chars.toCharArray();
this.k = k;
this.n = chars.length();
this.MAX = (long) Math.pow(n, k);
preComp = new double[k];
for(int i=0; i<k; i++) preComp[i] = Math.pow(n,i);
}
/**
* Returns the maximum number of permutations possible given the input.
* @return the maximum number of permutations possible given the input
*/
public long getMax(){
return this.MAX;
}
}Test class using direct index calls.
import java.util.List;
public class PermutationsIndividualPreComputedTest {
public static void main(String[] args) {
String chars = "ABCDEFGHIJ";
int k = 7;
PermutationsIndividualPreComputed perm =
new PermutationsIndividualPreComputed(chars, k);
long max = perm.getMax();
for(long i=0; i<max; i++) {
System.out.println(String.valueOf(perm.get(i)));
}
}
}A very basic comparison
Using a character set of size 10 and permutation length of 7, a basic comparison between All, Direct, and Optimized Direct in terms of milliseconds (MS) and megabytes (MB) was performed. Each result in the table corresponds to the average and standard deviation of 10 iterations. In this one instance, Optimized Direct is 42.45/65.95% faster and 87.04/0.02% smaller than All and Direct respectively. Thus, Optimized Direct is the quickest of the three, with the same minimal memory footprint as Direct.
| Metric | All MS | All MB | Direct MS | Direct MB | Optimized Direct MS | Optimized Direct MB |
|---|---|---|---|---|---|---|
| Average | 3,853.80 | 421.38 | 6,513.40 | 54.61 | 2,217.80 | 54.60 |
| Stdev | 45.74 | 0.01 | 6.77 | 0.02 | 4.53 | 0.03 |