找出弦的所有排列的优雅方法是什么。例如,ba的排列,将是ba和ab,但更长的字符串,如abcdefgh?是否有Java实现示例?
当前回答
使用递归的简单python解决方案。
def get_permutations(string):
# base case
if len(string) <= 1:
return set([string])
all_chars_except_last = string[:-1]
last_char = string[-1]
# recursive call: get all possible permutations for all chars except last
permutations_of_all_chars_except_last = get_permutations(all_chars_except_last)
# put the last char in all possible positions for each of the above permutations
permutations = set()
for permutation_of_all_chars_except_last in permutations_of_all_chars_except_last:
for position in range(len(all_chars_except_last) + 1):
permutation = permutation_of_all_chars_except_last[:position] + last_char + permutation_of_all_chars_except_last[position:]
permutations.add(permutation)
return permutations
其他回答
使用递归。
依次尝试每个字母作为第一个字母,然后使用递归调用找到剩余字母的所有排列。 基本情况是,当输入是空字符串时,唯一的排列就是空字符串。
public class StringPermutation {
// Function to print all the permutations of str
static void printPermutn(String str, String ans) {
// If string is empty
if (str.length() == 0) {
System.out.print(ans + " ");
return;
}
for (int i = 0; i < str.length(); i++) {
// ith character of str
char ch = str.charAt(i);
// Rest of the string after excluding
// the ith character
String ros = str.substring(0, i) + str.substring(i + 1);
// Recurvise call
printPermutn(ros, ans + ch);
}
}
public static void main(String[] args) {
String s = "ABC";
printPermutn(s, "");
}
}
下面是一个简单的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);
}
}
}
基于Heap算法的我的实现:
import java.util.ArrayList;
import java.util.List;
public class PermutationString {
public static List<String> permute(char[] str, int n) {
List<String> permutations = new ArrayList<>();
if (n == 1) {
permutations.add(new String(str));
}
else {
for (int i = 0; i < n; i++) {
permutations.addAll(permute(str, n-1));
if (n % 2 == 0) {
swap(str, i, n-1);
}
else {
swap(str, 0, n-1);
}
}
}
return permutations;
}
public static void swap(char[] str, int i, int j) {
char temp = str[i];
str[i] = str[j];
str[j] = temp;
}
public static void main(String[] args) {
List<String> permutations = permute("abcdefgh".toCharArray(), 8);
System.out.println(permutations);
}
}
时间复杂度为O(n!* n), O(n)为空间复杂度。
推荐文章
- 在流中使用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