找出弦的所有排列的优雅方法是什么。例如,ba的排列,将是ba和ab,但更长的字符串,如abcdefgh?是否有Java实现示例?
当前回答
以下是我在《破解编程面试》(P54)一书中提出的解决方案:
/**
* List permutations of a string.
*
* @param s the input string
* @return the list of permutations
*/
public static ArrayList<String> permutation(String s) {
// The result
ArrayList<String> res = new ArrayList<String>();
// If input string's length is 1, return {s}
if (s.length() == 1) {
res.add(s);
} else if (s.length() > 1) {
int lastIndex = s.length() - 1;
// Find out the last character
String last = s.substring(lastIndex);
// Rest of the string
String rest = s.substring(0, lastIndex);
// Perform permutation on the rest string and
// merge with the last character
res = merge(permutation(rest), last);
}
return res;
}
/**
* @param list a result of permutation, e.g. {"ab", "ba"}
* @param c the last character
* @return a merged new list, e.g. {"cab", "acb" ... }
*/
public static ArrayList<String> merge(ArrayList<String> list, String c) {
ArrayList<String> res = new ArrayList<>();
// Loop through all the string in the list
for (String s : list) {
// For each string, insert the last character to all possible positions
// and add them to the new list
for (int i = 0; i <= s.length(); ++i) {
String ps = new StringBuffer(s).insert(i, c).toString();
res.add(ps);
}
}
return res;
}
字符串"abcd"的运行输出:
第一步:合并[a]和b: [ba, ab] 步骤2:Merge [ba, ab]和c: [cba, bca, bac, cab, acb, abc] 第三步:Merge [cba, bca, bac, cab, acb, abc]和d: [dcba, cdba, cbad, cbca, bdcad
其他回答
作为Python生成器,带有现代类型提示:
from typing import Iterator
def permutations(string: str, prefix: str = '') -> Iterator[str]:
if len(string) == 0:
yield prefix
for i, character in enumerate(string):
yield from permutations(string[:i] + string[i + 1:], prefix + character)
for p in permutations('abcd'):
print(p)
基于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)为空间复杂度。
其中一个简单的解决方案是使用两个指针继续递归地交换字符。
public static void main(String[] args)
{
String str="abcdefgh";
perm(str);
}
public static void perm(String str)
{ char[] char_arr=str.toCharArray();
helper(char_arr,0);
}
public static void helper(char[] char_arr, int i)
{
if(i==char_arr.length-1)
{
// print the shuffled string
String str="";
for(int j=0; j<char_arr.length; j++)
{
str=str+char_arr[j];
}
System.out.println(str);
}
else
{
for(int j=i; j<char_arr.length; j++)
{
char tmp = char_arr[i];
char_arr[i] = char_arr[j];
char_arr[j] = tmp;
helper(char_arr,i+1);
char tmp1 = char_arr[i];
char_arr[i] = char_arr[j];
char_arr[j] = tmp1;
}
}
}
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编程入门)
如果有人想要生成排列来做一些事情,而不是通过void方法打印它们:
static List<int[]> permutations(int n) {
class Perm {
private final List<int[]> permutations = new ArrayList<>();
private void perm(int[] array, int step) {
if (step == 1) permutations.add(array.clone());
else for (int i = 0; i < step; i++) {
perm(array, step - 1);
int j = (step % 2 == 0) ? i : 0;
swap(array, step - 1, j);
}
}
private void swap(int[] array, int i, int j) {
int buffer = array[i];
array[i] = array[j];
array[j] = buffer;
}
}
int[] nVector = new int[n];
for (int i = 0; i < n; i++) nVector [i] = i;
Perm perm = new Perm();
perm.perm(nVector, n);
return perm.permutations;
}
推荐文章
- 在流中使用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