Java 中的字符串排列（非递归）
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/12189698/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
String permutations in Java (non-recursive)
提问by Sumit Shyamsukha
I'm a high school student of grade 10 trying to work through some problems in a Data Structures and Algorithms book on Java.
我是一名 10 年级的高中生，正在尝试解决有关 Java 的数据结构和算法书中的一些问题。
One of the questions is to print all permutations of a string.
问题之一是打印字符串的所有排列。
class C14
{
public static void main(char a[])
{
// char[] a = {'c','a','r','b','o','n'};
int c=0,w=0;
for(int q = 0;q<a.length;q++)
{
for(int i=0;i<a.length;i++)
{
for(int j=1;j<a.length;j++)
{
for(int k=1;k<a.length-1;k++)
{
for(int z=0;z<a.length;z++)
{
System.out.print(a[z]);
c++;
}
w++;
System.out.println();
char p=a[k+1];
a[k+1]=a[k];
a[k]=p;
}
System.out.println();
}
System.out.println();
char x=a[0];
a[0]=a[1];
a[1]=x;
}
}
System.out.println(" Character count = " + c);
System.out.println(" Word count = " + w);
}
}
This is my attempt. The book asks me to do it for the characters 'c','a','r','b','o','n'. My solution does just that, but when I try to use 3 or 4 letter words, it gives me repetitions. If I remove the outermost loop and try to print it, it works for 3 and 4 letter words but not for 5+ letter words.
这是我的尝试。这本书要求我为字符 'c'、'a'、'r'、'b'、'o'、'n' 做这件事。我的解决方案就是这样做的，但是当我尝试使用 3 或 4 个字母的单词时，它会给我重复。如果我删除最外层的循环并尝试打印它，它适用于 3 和 4 个字母的单词，但不适用于 5 个以上字母的单词。
I'll be glad to clarify my reasoning for it, I know it's not the most efficient, but do bear in mind the fact that I'm only in grade 10 and this is what came to my mind first.
我很乐意澄清我的理由，我知道这不是最有效的，但请记住，我只有 10 年级，这是我首先想到的。
Can someone please help me out, or at least hint at what's wrong? Please don't advise a recursive solution, because I want to work through it iteratively first. Thanks, Sumit.
有人可以帮助我，或者至少提示一下出了什么问题吗？请不要建议递归解决方案，因为我想先迭代地解决它。谢谢，苏米特。
采纳答案by John
Permutation with repetitions
重复排列
When you have n things to choose from ... you have n choices each time!
当你有n种东西可供选择时……你每次都有n种选择！
When choosing r of them, the permutations are:
在选择其中 r 个时，排列为：
n × n × ... (r times) = n^r
n × n × ... (r 次) = n^r
I'm presenting 2 cases. First case is when the we know the size of n and r already, and its the easy one. The second when n and r are dynamic.
我介绍了 2 个案例。第一种情况是当我们已经知道 n 和 r 的大小时，这很容易。当 n 和 r 是动态的时的第二个。
//when n and r are known statically
class Permutation
{
public static void main(String[] args)
{
char[] values = {'a', 'b', 'c', 'd'};
int n = values.length;
int r = 2;
int i = 0, j = 0;
for(i=0; i<n; i++)
{
for(j=0; j<n; j++)
{
System.out.println(values[j] + " " + values[i]);
}
}
}
}
//when n and r are known only dynamically
class Permutation
{
public static void main(String[] args)
{
char[] values = {'a', 'b', 'c', 'd'};
int n = values.length;
int r = 2;
int i[] = new int[r];
int rc = 0;
for(int j=0; j<Math.pow(n,r); j++)
{
rc=0;
while(rc<r)
{
System.out.print(values[i[rc]] + " ");
rc++;
}
System.out.println();
rc = 0;
while(rc<r)
{
if(i[rc]<n-1)
{
i[rc]++;
break;
}
else
{
i[rc]=0;
}
rc++;
}
}
}
}
