找出弦的所有排列的优雅方法是什么。例如,ba的排列,将是ba和ab,但更长的字符串,如abcdefgh?是否有Java实现示例?
当前回答
我的实现基于Mark Byers上面的描述:
static Set<String> permutations(String str){
if (str.isEmpty()){
return Collections.singleton(str);
}else{
Set <String> set = new HashSet<>();
for (int i=0; i<str.length(); i++)
for (String s : permutations(str.substring(0, i) + str.substring(i+1)))
set.add(str.charAt(i) + s);
return set;
}
}
其他回答
下面是一个简单的Java递归解决方案:
public static ArrayList<String> permutations(String s) {
ArrayList<String> out = new ArrayList<String>();
if (s.length() == 1) {
out.add(s);
return out;
}
char first = s.charAt(0);
String rest = s.substring(1);
for (String permutation : permutations(rest)) {
out.addAll(insertAtAllPositions(first, permutation));
}
return out;
}
public static ArrayList<String> insertAtAllPositions(char ch, String s) {
ArrayList<String> out = new ArrayList<String>();
for (int i = 0; i <= s.length(); ++i) {
String inserted = s.substring(0, i) + ch + s.substring(i);
out.add(inserted);
}
return out;
}
/*
* eg: abc =>{a,bc},{b,ac},{c,ab}
* =>{ca,b},{cb,a}
* =>cba,cab
* =>{ba,c},{bc,a}
* =>bca,bac
* =>{ab,c},{ac,b}
* =>acb,abc
*/
public void nonRecpermute(String prefix, String word)
{
String[] currentstr ={prefix,word};
Stack<String[]> stack = new Stack<String[]>();
stack.add(currentstr);
while(!stack.isEmpty())
{
currentstr = stack.pop();
String currentPrefix = currentstr[0];
String currentWord = currentstr[1];
if(currentWord.equals(""))
{
System.out.println("Word ="+currentPrefix);
}
for(int i=0;i<currentWord.length();i++)
{
String[] newstr = new String[2];
newstr[0]=currentPrefix + String.valueOf(currentWord.charAt(i));
newstr[1] = currentWord.substring(0, i);
if(i<currentWord.length()-1)
{
newstr[1] = newstr[1]+currentWord.substring(i+1);
}
stack.push(newstr);
}
}
}
使用位操作可以很容易地做到这一点。“我们都知道,任何给定的有N个元素的集合有2N个可能的子集。如果我们用一个位来表示子集中的每个元素呢?位可以是0或1,因此我们可以用它来表示对应的元素是否属于这个给定的子集。所以每个位模式代表一个子集。”(复制文本)
private void getPermutation(String str)
{
if(str==null)
return;
Set<String> StrList = new HashSet<String>();
StringBuilder strB= new StringBuilder();
for(int i = 0;i < (1 << str.length()); ++i)
{
strB.setLength(0); //clear the StringBuilder
for(int j = 0;j < str.length() ;++j){
if((i & (1 << j))>0){ // to check whether jth bit is set
strB.append(str.charAt(j));
}
}
if(!strB.toString().isEmpty())
StrList.add(strB.toString());
}
System.out.println(Arrays.toString(StrList.toArray()));
}
使用递归。
依次尝试每个字母作为第一个字母,然后使用递归调用找到剩余字母的所有排列。 基本情况是,当输入是空字符串时,唯一的排列就是空字符串。
让我们以输入abc为例。
从集合(["c"])中的最后一个元素(c)开始,然后将最后第二个元素(b)添加到它的前面,末尾和中间的每个可能位置,使其["bc", "cb"],然后以同样的方式将后面的下一个元素(a)添加到集合中的每个字符串中,使其:
"a" + "bc" = ["abc", "bac", "bca"] and "a" + "cb" = ["acb" ,"cab", "cba"]
因此整个排列:
["abc", "bac", "bca","acb" ,"cab", "cba"]
代码:
public class Test
{
static Set<String> permutations;
static Set<String> result = new HashSet<String>();
public static Set<String> permutation(String string) {
permutations = new HashSet<String>();
int n = string.length();
for (int i = n - 1; i >= 0; i--)
{
shuffle(string.charAt(i));
}
return permutations;
}
private static void shuffle(char c) {
if (permutations.size() == 0) {
permutations.add(String.valueOf(c));
} else {
Iterator<String> it = permutations.iterator();
for (int i = 0; i < permutations.size(); i++) {
String temp1;
for (; it.hasNext();) {
temp1 = it.next();
for (int k = 0; k < temp1.length() + 1; k += 1) {
StringBuilder sb = new StringBuilder(temp1);
sb.insert(k, c);
result.add(sb.toString());
}
}
}
permutations = result;
//'result' has to be refreshed so that in next run it doesn't contain stale values.
result = new HashSet<String>();
}
}
public static void main(String[] args) {
Set<String> result = permutation("abc");
System.out.println("\nThere are total of " + result.size() + " permutations:");
Iterator<String> it = result.iterator();
while (it.hasNext()) {
System.out.println(it.next());
}
}
}
推荐文章
- 在流中使用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