找出弦的所有排列的优雅方法是什么。例如,ba的排列,将是ba和ab,但更长的字符串,如abcdefgh?是否有Java实现示例?
当前回答
这是一个更快的解决方案,因为它不受字符串连接计算复杂度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);
}
其他回答
使用递归。
依次尝试每个字母作为第一个字母,然后使用递归调用找到剩余字母的所有排列。 基本情况是,当输入是空字符串时,唯一的排列就是空字符串。
/*
* 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);
}
}
}
另一种简单的方法是遍历字符串,选择尚未使用的字符并将其放入缓冲区,继续循环,直到缓冲区大小等于字符串长度。我更喜欢这个回溯跟踪解决方案,因为:
容易理解 容易避免重复 输出是排序的
下面是java代码:
List<String> permute(String str) {
if (str == null) {
return null;
}
char[] chars = str.toCharArray();
boolean[] used = new boolean[chars.length];
List<String> res = new ArrayList<String>();
StringBuilder sb = new StringBuilder();
Arrays.sort(chars);
helper(chars, used, sb, res);
return res;
}
void helper(char[] chars, boolean[] used, StringBuilder sb, List<String> res) {
if (sb.length() == chars.length) {
res.add(sb.toString());
return;
}
for (int i = 0; i < chars.length; i++) {
// avoid duplicates
if (i > 0 && chars[i] == chars[i - 1] && !used[i - 1]) {
continue;
}
// pick the character that has not used yet
if (!used[i]) {
used[i] = true;
sb.append(chars[i]);
helper(chars, used, sb, res);
// back tracking
sb.deleteCharAt(sb.length() - 1);
used[i] = false;
}
}
}
str输入:1231
输出列表:{1123,1132,1213,1231,1312,1321,2113,2131,2311,3112,3121,3211}
注意,输出是排序的,没有重复的结果。
//Rotate and create words beginning with all letter possible and push to stack 1
//Read from stack1 and for each word create words with other letters at the next location by rotation and so on
/* eg : man
1. push1 - man, anm, nma
2. pop1 - nma , push2 - nam,nma
pop1 - anm , push2 - amn,anm
pop1 - man , push2 - mna,man
*/
public class StringPermute {
static String str;
static String word;
static int top1 = -1;
static int top2 = -1;
static String[] stringArray1;
static String[] stringArray2;
static int strlength = 0;
public static void main(String[] args) throws IOException {
System.out.println("Enter String : ");
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader bfr = new BufferedReader(isr);
str = bfr.readLine();
word = str;
strlength = str.length();
int n = 1;
for (int i = 1; i <= strlength; i++) {
n = n * i;
}
stringArray1 = new String[n];
stringArray2 = new String[n];
push(word, 1);
doPermute();
display();
}
public static void push(String word, int x) {
if (x == 1)
stringArray1[++top1] = word;
else
stringArray2[++top2] = word;
}
public static String pop(int x) {
if (x == 1)
return stringArray1[top1--];
else
return stringArray2[top2--];
}
public static void doPermute() {
for (int j = strlength; j >= 2; j--)
popper(j);
}
public static void popper(int length) {
// pop from stack1 , rotate each word n times and push to stack 2
if (top1 > -1) {
while (top1 > -1) {
word = pop(1);
for (int j = 0; j < length; j++) {
rotate(length);
push(word, 2);
}
}
}
// pop from stack2 , rotate each word n times w.r.t position and push to
// stack 1
else {
while (top2 > -1) {
word = pop(2);
for (int j = 0; j < length; j++) {
rotate(length);
push(word, 1);
}
}
}
}
public static void rotate(int position) {
char[] charstring = new char[100];
for (int j = 0; j < word.length(); j++)
charstring[j] = word.charAt(j);
int startpos = strlength - position;
char temp = charstring[startpos];
for (int i = startpos; i < strlength - 1; i++) {
charstring[i] = charstring[i + 1];
}
charstring[strlength - 1] = temp;
word = new String(charstring).trim();
}
public static void display() {
int top;
if (top1 > -1) {
while (top1 > -1)
System.out.println(stringArray1[top1--]);
} else {
while (top2 > -1)
System.out.println(stringArray2[top2--]);
}
}
}
基于Mark Byers的回答,我的python实现:
def permutations(string):
if len(string) == 1:
return [string]
permutations=[]
for i in range(len(string)):
for perm in permutations(string[:i]+string[i+1:]):
permutations.append(string[i] + perm)
return 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