Skip to content

Instantly share code, notes, and snippets.

@vaskoz
Created June 5, 2013 06:41
Show Gist options
  • Save vaskoz/5712028 to your computer and use it in GitHub Desktop.
Save vaskoz/5712028 to your computer and use it in GitHub Desktop.
Implementation of Lexicographic Permutation Generation. Algorithm L by Knuth. Usage: java AlgorithmL "122233344555"
import java.util.Arrays;
public class AlgorithmL {
public static void main(String[] args) {
if (args.length != 1) {
System.err.println("Usage: provide a string (quoted if multiword)");
System.exit(1);
}
char[] letters = args[0].toCharArray();
Arrays.sort(letters);
System.out.println(letters);
while (true) {
int j = letters.length - 2;
while (letters[j] >= letters[j+1]) {
if (j == 0) System.exit(0);
j--;
}
int l = letters.length - 1;
while (letters[j] >= letters[l]) {
l--;
}
swap(letters, j, l);
int k = j + 1;
l = letters.length - 1;
while (k < l) {
swap(letters, k, l);
k++;
l--;
}
System.out.println(letters);
}
}
private static void swap(char[] data, int i, int j) {
char temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment