Last active
March 26, 2023 18:49
-
-
Save guneyizol/d106633a782bd257741c49fe0af6a1a1 to your computer and use it in GitHub Desktop.
Generating lexicographically ordered permutations
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class Permutation { | |
private char[] chars; | |
public ArrayList<String> permutation(String s) { | |
chars = s.toCharArray(); | |
Arrays.sort(chars); | |
ArrayList<String> perms = new ArrayList<String>(factorial(s.length())); | |
perms.add(String.valueOf(chars)); | |
while (next()) | |
perms.add(String.valueOf(chars)); | |
return perms; | |
} | |
private boolean next() { | |
int m = chars.length - 1; | |
// find the index | |
while (m > 0 && chars[m - 1] > chars[m]) | |
m--; | |
// largest permutation is in chars, stop generating | |
if (m == 0) return false; | |
assert chars[m - 1] < chars[m]; | |
int k = chars.length - 1; | |
while (chars[k] < chars[m - 1]) | |
k--; | |
assert chars[k] > chars[m - 1]; | |
swap(k, m - 1); | |
// reverse the chars in the range [m, chars.length - 1] | |
// so that they are in increasing order | |
int s = m; | |
int e = chars.length - 1; | |
while (s < e) { | |
swap(s, e); | |
s++; | |
e--; | |
} | |
return true; | |
} | |
private void swap(int i, int j) { | |
char t = chars[i]; | |
chars[i] = chars[j]; | |
chars[j] = t; | |
} | |
private int factorial(int n) { | |
int fact = 1; | |
for (int i = 2; i <= n; i++) { | |
fact *= i; | |
} | |
return fact; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This algorithm is an implementation of the Fischer-Krause Algorithm adapted from an article on mathsanew.com. The method
permutation
returns a list of lexicographically ordered permutations of an input string s. It passes the tests for the relevant Geeks for Geeks practice problem.