-
-
Save anil477/a41c0d7d63059480b8718eb35e60afde to your computer and use it in GitHub Desktop.
Generate all permutation of a string in lexicographically sorted order with repetition of characters possible.
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
import java.util.Map; | |
import java.util.TreeMap; | |
/** | |
* Date 01/29/2016 | |
* @author Tushar Roy | |
* | |
* Generate all permutations of string in lexicographically sorted order where repetitions of | |
* character is possible in string. | |
*/ | |
public class StringPermutation { | |
public void permute(char input[]) { | |
Map<Character, Integer> countMap = new TreeMap<>(); | |
for (char ch : input) { | |
countMap.compute(ch, (key, val) -> { | |
if (val == null) { | |
return 1; | |
} else { | |
return val + 1; | |
} | |
}); | |
} | |
char str[] = new char[countMap.size()]; | |
int count[] = new int[countMap.size()]; | |
int index = 0; | |
for (Map.Entry<Character, Integer> entry : countMap.entrySet()) { | |
str[index] = entry.getKey(); | |
count[index] = entry.getValue(); | |
index++; | |
} | |
char result[] = new char[input.length]; | |
permuteUtil(str, count, result, 0); | |
} | |
public void permuteUtil(char str[], int count[], char result[], int level) { | |
if (level == result.length) { | |
printArray(result); | |
return; | |
} | |
for(int i = 0; i < str.length; i++) { | |
if(count[i] == 0) { | |
continue; | |
} | |
result[level] = str[i]; | |
count[i]--; | |
permuteUtil(str, count, result, level + 1); | |
count[i]++; | |
} | |
} | |
private void printArray(char input[]) { | |
for(char ch : input) { | |
System.out.print(ch); | |
} | |
System.out.println(); | |
} | |
public static void main(String args[]) { | |
StringPermutation sp = new StringPermutation(); | |
sp.permute("AABC".toCharArray()); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment