找出弦的所有排列的优雅方法是什么。例如,ba的排列,将是ba和ab,但更长的字符串,如abcdefgh?是否有Java实现示例?
当前回答
使用递归。
依次尝试每个字母作为第一个字母,然后使用递归调用找到剩余字母的所有排列。 基本情况是,当输入是空字符串时,唯一的排列就是空字符串。
其他回答
使用递归。
依次尝试每个字母作为第一个字母,然后使用递归调用找到剩余字母的所有排列。 基本情况是,当输入是空字符串时,唯一的排列就是空字符串。
使用位操作可以很容易地做到这一点。“我们都知道,任何给定的有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()));
}
这是一个更快的解决方案,因为它不受字符串连接计算复杂度O(n^2)的影响。另一方面它是无循环的,完全递归的
public static void main(String[] args) {
permutation("ABCDEFGHIJKLMNOPQRSTUVWXYZ");
}
private static void permutation(String str) {
char[] stringArray = str.toCharArray();
printPermutation(stringArray, 0, stringArray.length, 0, 1);
}
private static void printPermutation(char[] string, int loopCounter, int length, int indexFrom, int indexTo) {
// Stop condition
if (loopCounter == length)
return;
/*
When reaching the end of the array:
1- Reset loop indices.
2- Increase length counter.
*/
if (indexTo == length) {
indexFrom = 0;
indexTo = 1;
++loopCounter;
}
// Print.
System.out.println(string);
// Swap from / to indices.
char temp = string[indexFrom];
string[indexFrom] = string[indexTo];
string[indexTo] = temp;
// Go for next iteration.
printPermutation(string, loopCounter, length, ++indexFrom, ++indexTo);
}
下面是一个简单的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;
}
public class Permutation
{
public static void main(String[] args)
{
String str = "ABC";
int n = str.length();
Permutation permutation = new Permutation();
permutation.permute(str, 0, n-1);
}
/**
* permutation function
* @param str string to calculate permutation for
* @param l starting index
* @param r end index
*/
private void permute(String str, int l, int r)
{
if (l == r)
System.out.println(str);
else
{
for (int i = l; i <= r; i++)
{
str = swap(str,l,i);
permute(str, l+1, r);
str = swap(str,l,i);
}
}
}
/**
* Swap Characters at position
* @param a string value
* @param i position 1
* @param j position 2
* @return swapped string
*/
public String swap(String a, int i, int j)
{
char temp;
char[] charArray = a.toCharArray();
temp = charArray[i] ;
charArray[i] = charArray[j];
charArray[j] = temp;
return String.valueOf(charArray);
}
}
推荐文章
- 在流中使用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