找出弦的所有排列的优雅方法是什么。例如,ba的排列,将是ba和ab,但更长的字符串,如abcdefgh?是否有Java实现示例?
当前回答
/** Returns an array list containing all
* permutations of the characters in s. */
public static ArrayList<String> permute(String s) {
ArrayList<String> perms = new ArrayList<>();
int slen = s.length();
if (slen > 0) {
// Add the first character from s to the perms array list.
perms.add(Character.toString(s.charAt(0)));
// Repeat for all additional characters in s.
for (int i = 1; i < slen; ++i) {
// Get the next character from s.
char c = s.charAt(i);
// For each of the strings currently in perms do the following:
int size = perms.size();
for (int j = 0; j < size; ++j) {
// 1. remove the string
String p = perms.remove(0);
int plen = p.length();
// 2. Add plen + 1 new strings to perms. Each new string
// consists of the removed string with the character c
// inserted into it at a unique location.
for (int k = 0; k <= plen; ++k) {
perms.add(p.substring(0, k) + c + p.substring(k));
}
}
}
}
return perms;
}
其他回答
这个没有递归
public static void permute(String s) {
if(null==s || s.isEmpty()) {
return;
}
// List containing words formed in each iteration
List<String> strings = new LinkedList<String>();
strings.add(String.valueOf(s.charAt(0))); // add the first element to the list
// Temp list that holds the set of strings for
// appending the current character to all position in each word in the original list
List<String> tempList = new LinkedList<String>();
for(int i=1; i< s.length(); i++) {
for(int j=0; j<strings.size(); j++) {
tempList.addAll(merge(s.charAt(i), strings.get(j)));
}
strings.removeAll(strings);
strings.addAll(tempList);
tempList.removeAll(tempList);
}
for(int i=0; i<strings.size(); i++) {
System.out.println(strings.get(i));
}
}
/**
* helper method that appends the given character at each position in the given string
* and returns a set of such modified strings
* - set removes duplicates if any(in case a character is repeated)
*/
private static Set<String> merge(Character c, String s) {
if(s==null || s.isEmpty()) {
return null;
}
int len = s.length();
StringBuilder sb = new StringBuilder();
Set<String> list = new HashSet<String>();
for(int i=0; i<= len; i++) {
sb = new StringBuilder();
sb.append(s.substring(0, i) + c + s.substring(i, len));
list.add(sb.toString());
}
return list;
}
public static void permutation(String str) {
permutation("", str);
}
private static void permutation(String prefix, String str) {
int n = str.length();
if (n == 0) System.out.println(prefix);
else {
for (int i = 0; i < n; i++)
permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
}
}
(通过Java编程入门)
python实现
def getPermutation(s, prefix=''):
if len(s) == 0:
print prefix
for i in range(len(s)):
getPermutation(s[0:i]+s[i+1:len(s)],prefix+s[i] )
getPermutation('abcd','')
没有递归的Java实现
public Set<String> permutate(String s){
Queue<String> permutations = new LinkedList<String>();
Set<String> v = new HashSet<String>();
permutations.add(s);
while(permutations.size()!=0){
String str = permutations.poll();
if(!v.contains(str)){
v.add(str);
for(int i = 0;i<str.length();i++){
String c = String.valueOf(str.charAt(i));
permutations.add(str.substring(i+1) + c + str.substring(0,i));
}
}
}
return v;
}
这里有一个优雅的,非递归的O(n!)解:
public static StringBuilder[] permutations(String s) {
if (s.length() == 0)
return null;
int length = fact(s.length());
StringBuilder[] sb = new StringBuilder[length];
for (int i = 0; i < length; i++) {
sb[i] = new StringBuilder();
}
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
int times = length / (i + 1);
for (int j = 0; j < times; j++) {
for (int k = 0; k < length / times; k++) {
sb[j * length / times + k].insert(k, ch);
}
}
}
return sb;
}
推荐文章
- 在流中使用Java 8 foreach循环移动到下一项
- 访问限制:'Application'类型不是API(必需库rt.jar的限制)
- 用Java计算两个日期之间的天数
- 如何配置slf4j-simple
- 在Jar文件中运行类
- 带参数的可运行?
- 我如何得到一个字符串的前n个字符而不检查大小或出界?
- 我可以在Java中设置enum起始值吗?
- Java中的回调函数
- c#和Java中的泛型有什么不同?和模板在c++ ?
- 在Java中,流相对于循环的优势是什么?
- Jersey在未找到InjectionManagerFactory时停止工作
- 在Java流是peek真的只是调试?
- Recyclerview不调用onCreateViewHolder
- 将JSON字符串转换为HashMap