找出弦的所有排列的优雅方法是什么。例如,ba的排列,将是ba和ab,但更长的字符串,如abcdefgh?是否有Java实现示例?
当前回答
递归Python解决方案
def permute(input_str):
_permute("", input_str)
def _permute(prefix, str_to_permute):
if str_to_permute == '':
print(prefix)
else:
for i in range(len(str_to_permute)):
_permute(prefix+str_to_permute[i], str_to_permute[0:i] + str_to_permute[i+1:])
if __name__ == '__main__':
permute('foobar')
其他回答
使用递归。
依次尝试每个字母作为第一个字母,然后使用递归调用找到剩余字母的所有排列。 基本情况是,当输入是空字符串时,唯一的排列就是空字符串。
让我试着用Kotlin来解决这个问题:
fun <T> List<T>.permutations(): List<List<T>> {
//escape case
if (this.isEmpty()) return emptyList()
if (this.size == 1) return listOf(this)
if (this.size == 2) return listOf(listOf(this.first(), this.last()), listOf(this.last(), this.first()))
//recursive case
return this.flatMap { lastItem ->
this.minus(lastItem).permutations().map { it.plus(lastItem) }
}
}
核心概念:将长链表分解成小链表+递归
长答案与示例列表[1,2,3,4]:
即使是一个4种组合的列表,在脑海中列出所有可能的排列已经有点令人困惑了,我们需要做的就是避免这种情况。我们很容易理解如何对大小为0、1和2的列表进行排列,因此我们所需要做的就是将它们分解为这些大小中的任何一个,并将它们正确地组合起来。想象一台头奖机器:这个算法将从右向左旋转,然后写下
当列表大小为0或1时,返回空/列表为1 当列表大小为2时处理(例如[3,4]),并生成2个排列([3,4]& [4,3]) 对于每一项,将其标记为最后一项中的最后一项,并找到列表中其余项目的所有排列。(例如,把[4]放在桌子上,把[1,2,3]重新排列) 现在对它的子元素进行所有的排列,把它自己放回列表的末尾(例如:[1,2,3][,4],[1,3,2][,4],[2,3,1][,4],…)
下面是一个java实现:
/* All Permutations of a String */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Complexity O(n*n!) */
class Ideone
{
public static ArrayList<String> strPerm(String str, ArrayList<String> list)
{
int len = str.length();
if(len==1){
list.add(str);
return list;
}
list = strPerm(str.substring(0,len-1),list);
int ls = list.size();
char ap = str.charAt(len-1);
for(int i=0;i<ls;i++){
String temp = list.get(i);
int tl = temp.length();
for(int j=0;j<=tl;j++){
list.add(temp.substring(0,j)+ap+temp.substring(j,tl));
}
}
while(true){
String temp = list.get(0);
if(temp.length()<len)
list.remove(temp);
else
break;
}
return list;
}
public static void main (String[] args) throws java.lang.Exception
{
String str = "abc";
ArrayList<String> list = new ArrayList<>();
list = strPerm(str,list);
System.out.println("Total Permutations : "+list.size());
for(int i=0;i<list.size();i++)
System.out.println(list.get(i));
}
}
http://ideone.com/nWPb3k
在python中
def perms(in_str, prefix=""):
if not len(in_str) :
print(prefix)
else:
for i in range(0, len(in_str)):
perms(in_str[:i] + in_str[i + 1:], prefix + in_str[i])
perms('ASD')
没有递归的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;
}
推荐文章
- 在流中使用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