找出弦的所有排列的优雅方法是什么。例如,ba的排列,将是ba和ab,但更长的字符串,如abcdefgh?是否有Java实现示例?
当前回答
这里有一个优雅的,非递归的O(n!)解:
public static StringBuilder[] permutations(String s) {
if (s.length() == 0)
return null;
int length = fact(s.length());
StringBuilder[] sb = new StringBuilder[length];
for (int i = 0; i < length; i++) {
sb[i] = new StringBuilder();
}
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
int times = length / (i + 1);
for (int j = 0; j < times; j++) {
for (int k = 0; k < length / times; k++) {
sb[j * length / times + k].insert(k, ch);
}
}
}
return sb;
}
其他回答
我定义了左右两个字符串。一开始,左边是输入字符串,右边是“”。我递归地从左边选择所有可能的字符,并将其添加到右边的末尾。然后,在left-charAt(I)和right+charAt(I)上调用递归函数。我定义了一个类来跟踪生成的排列。
import java.util.HashSet;
import java.util.Set;
public class FindPermutations {
static class Permutations {
Set<String> permutations = new HashSet<>();
}
/**
* Building all the permutations by adding chars of left to right one by one.
*
* @param left The left string
* @param right The right string
* @param permutations The permutations
*/
private void findPermutations(String left, String right, Permutations permutations) {
int n = left.length();
if (n == 0) {
permutations.permutations.add(right);
}
for (int i = 0; i < n; i++) {
findPermutations(left.substring(0, i) + left.substring(i + 1, n), right + left.charAt(i), permutations);
}
}
/**
* Gets all the permutations of a string s.
*
* @param s The input string
* @return all the permutations of a string s
*/
public Permutations getPermutations(String s) {
Permutations permutations = new Permutations();
findPermutations(s, "", permutations);
return permutations;
}
public static void main(String[] args) {
FindPermutations findPermutations = new FindPermutations();
String s = "ABC";
Permutations permutations = findPermutations.getPermutations(s);
printPermutations(permutations);
}
private static void printPermutations(Permutations permutations) {
for (String p : permutations.permutations) {
System.out.println(p);
}
}
}
我希望这能有所帮助。
下面是两个c#版本(仅供参考): 1. 打印所有排列 2. 返回所有排列
算法的基本要点是(可能下面的代码更直观-尽管如此,下面的代码是做什么的一些解释): -从当前索引到集合的其余部分,交换当前索引处的元素 -递归地获得下一个索引中剩余元素的排列 -恢复秩序,通过重新交换
注意:上述递归函数将从起始索引中调用。
private void PrintAllPermutations(int[] a, int index, ref int count)
{
if (index == (a.Length - 1))
{
count++;
var s = string.Format("{0}: {1}", count, string.Join(",", a));
Debug.WriteLine(s);
}
for (int i = index; i < a.Length; i++)
{
Utilities.swap(ref a[i], ref a[index]);
this.PrintAllPermutations(a, index + 1, ref count);
Utilities.swap(ref a[i], ref a[index]);
}
}
private int PrintAllPermutations(int[] a)
{
a.ThrowIfNull("a");
int count = 0;
this.PrintAllPermutations(a, index:0, count: ref count);
return count;
}
版本2(与上面相同-但返回排列而不是打印)
private int[][] GetAllPermutations(int[] a, int index)
{
List<int[]> permutations = new List<int[]>();
if (index == (a.Length - 1))
{
permutations.Add(a.ToArray());
}
for (int i = index; i < a.Length; i++)
{
Utilities.swap(ref a[i], ref a[index]);
var r = this.GetAllPermutations(a, index + 1);
permutations.AddRange(r);
Utilities.swap(ref a[i], ref a[index]);
}
return permutations.ToArray();
}
private int[][] GetAllPermutations(int[] p)
{
p.ThrowIfNull("p");
return this.GetAllPermutations(p, 0);
}
单元测试
[TestMethod]
public void PermutationsTests()
{
List<int> input = new List<int>();
int[] output = { 0, 1, 2, 6, 24, 120 };
for (int i = 0; i <= 5; i++)
{
if (i != 0)
{
input.Add(i);
}
Debug.WriteLine("================PrintAllPermutations===================");
int count = this.PrintAllPermutations(input.ToArray());
Assert.IsTrue(count == output[i]);
Debug.WriteLine("=====================GetAllPermutations=================");
var r = this.GetAllPermutations(input.ToArray());
Assert.IsTrue(count == r.Length);
for (int j = 1; j <= r.Length;j++ )
{
string s = string.Format("{0}: {1}", j,
string.Join(",", r[j - 1]));
Debug.WriteLine(s);
}
Debug.WriteLine("No.OfElements: {0}, TotalPerms: {1}", i, count);
}
}
使用递归。
当输入是空字符串时,唯一的排列就是空字符串。尝试将字符串中的每个字母作为第一个字母,然后使用递归调用找到其余字母的所有排列。
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);
}
}
}
//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--]);
}
}
}
使用递归。
依次尝试每个字母作为第一个字母,然后使用递归调用找到剩余字母的所有排列。 基本情况是,当输入是空字符串时,唯一的排列就是空字符串。
推荐文章
- 在流中使用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