找出弦的所有排列的优雅方法是什么。例如,ba的排列,将是ba和ab,但更长的字符串,如abcdefgh?是否有Java实现示例?
当前回答
没有递归的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;
}
其他回答
我们可以用阶乘来计算有多少字符串以某个字母开头。
示例:取输入abcd。(3!) == 6个字符串将以abcd中的每个字母开头。
static public int facts(int x){
int sum = 1;
for (int i = 1; i < x; i++) {
sum *= (i+1);
}
return sum;
}
public static void permutation(String str) {
char[] str2 = str.toCharArray();
int n = str2.length;
int permutation = 0;
if (n == 1) {
System.out.println(str2[0]);
} else if (n == 2) {
System.out.println(str2[0] + "" + str2[1]);
System.out.println(str2[1] + "" + str2[0]);
} else {
for (int i = 0; i < n; i++) {
if (true) {
char[] str3 = str.toCharArray();
char temp = str3[i];
str3[i] = str3[0];
str3[0] = temp;
str2 = str3;
}
for (int j = 1, count = 0; count < facts(n-1); j++, count++) {
if (j != n-1) {
char temp1 = str2[j+1];
str2[j+1] = str2[j];
str2[j] = temp1;
} else {
char temp1 = str2[n-1];
str2[n-1] = str2[1];
str2[1] = temp1;
j = 1;
} // end of else block
permutation++;
System.out.print("permutation " + permutation + " is -> ");
for (int k = 0; k < n; k++) {
System.out.print(str2[k]);
} // end of loop k
System.out.println();
} // end of loop j
} // end of loop i
}
}
使用递归。
当输入是空字符串时,唯一的排列就是空字符串。尝试将字符串中的每个字母作为第一个字母,然后使用递归调用找到其余字母的所有排列。
import java.util.ArrayList;
import java.util.List;
class Permutation {
private static List<String> permutation(String prefix, String str) {
List<String> permutations = new ArrayList<>();
int n = str.length();
if (n == 0) {
permutations.add(prefix);
} else {
for (int i = 0; i < n; i++) {
permutations.addAll(permutation(prefix + str.charAt(i), str.substring(i + 1, n) + str.substring(0, i)));
}
}
return permutations;
}
public static void main(String[] args) {
List<String> perms = permutation("", "abcd");
String[] array = new String[perms.size()];
for (int i = 0; i < perms.size(); i++) {
array[i] = perms.get(i);
}
int x = array.length;
for (final String anArray : array) {
System.out.println(anArray);
}
}
}
在这里和其他论坛给出的所有解决方案中,我最喜欢Mark Byers。这个描述实际上让我自己思考并编写了代码。 可惜我不能投票支持他的解决方案,因为我是新手。 无论如何,这是我对他的描述的实现
public class PermTest {
public static void main(String[] args) throws Exception {
String str = "abcdef";
StringBuffer strBuf = new StringBuffer(str);
doPerm(strBuf,0);
}
private static void doPerm(StringBuffer str, int index){
if(index == str.length())
System.out.println(str);
else { //recursively solve this by placing all other chars at current first pos
doPerm(str, index+1);
for (int i = index+1; i < str.length(); i++) {//start swapping all other chars with current first char
swap(str,index, i);
doPerm(str, index+1);
swap(str,i, index);//restore back my string buffer
}
}
}
private static void swap(StringBuffer str, int pos1, int pos2){
char t1 = str.charAt(pos1);
str.setCharAt(pos1, str.charAt(pos2));
str.setCharAt(pos2, t1);
}
}
我更喜欢这个解决方案,而不是第一个解决方案,因为这个解决方案使用StringBuffer。我不会说我的解决方案没有创建任何临时字符串(它实际上在system.out.println中创建,其中调用StringBuffer的toString())。但我只是觉得这比第一个解决方案好太多的字符串字面值被创建。可能有些性能人员可以根据“内存”来评估这一点(对于“时间”来说,由于额外的“交换”,它已经滞后了)
改进的代码相同
static String permutationStr[];
static int indexStr = 0;
static int factorial (int i) {
if (i == 1)
return 1;
else
return i * factorial(i-1);
}
public static void permutation(String str) {
char strArr[] = str.toLowerCase().toCharArray();
java.util.Arrays.sort(strArr);
int count = 1, dr = 1;
for (int i = 0; i < strArr.length-1; i++){
if ( strArr[i] == strArr[i+1]) {
count++;
} else {
dr *= factorial(count);
count = 1;
}
}
dr *= factorial(count);
count = factorial(strArr.length) / dr;
permutationStr = new String[count];
permutation("", str);
for (String oneStr : permutationStr){
System.out.println(oneStr);
}
}
private static void permutation(String prefix, String str) {
int n = str.length();
if (n == 0) {
for (int i = 0; i < indexStr; i++){
if(permutationStr[i].equals(prefix))
return;
}
permutationStr[indexStr++] = prefix;
} else {
for (int i = 0; i < n; i++) {
permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n));
}
}
}
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编程入门)
推荐文章
- 在流中使用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