找出弦的所有排列的优雅方法是什么。例如,ba的排列,将是ba和ab,但更长的字符串,如abcdefgh?是否有Java实现示例?


当前回答

其中一个简单的解决方案是使用两个指针继续递归地交换字符。

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;
    }
}
}

其他回答

这对我很有效。

import java.util.Arrays;

public class StringPermutations{
    public static void main(String args[]) {
        String inputString = "ABC";
        permute(inputString.toCharArray(), 0, inputString.length()-1);
    }

    public static void permute(char[] ary, int startIndex, int endIndex) {
        if(startIndex == endIndex){
            System.out.println(String.valueOf(ary));
        }else{
            for(int i=startIndex;i<=endIndex;i++) {
                 swap(ary, startIndex, i );
                 permute(ary, startIndex+1, endIndex);
                 swap(ary, startIndex, i );
            }
        }
    }

    public static void swap(char[] ary, int x, int y) {
        char temp = ary[x];
        ary[x] = ary[y];
        ary[y] = temp;
    }
}
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编程入门)

简单的解决方案,利用swift语言的特点,数组是值类型。

func permutation(chrs: [String], arr: [String], result: inout [[String]]) {
   if arr.count == chrs.count {
       result.append(arr)
       return
   }

   for chr in chrs {
       var arr = arr
       if !arr.contains(chr) {
           arr.append(chr)
           permutation(chrs: chrs, arr: arr, result: &result)
       }
   }
}

func test() {
   var result = [[String]]()
   let chrs = ["a", "b", "c", "d"]
   permutation(chrs: chrs, arr: [], result: &result)
}

复杂度O(n * n!)

基于Mark Byers的回答,我想出了这个解决方案:

JAVA

public class Main {

    public static void main(String[] args) {
        myPerm("ABCD", 0);
    }

    private static void myPerm(String str, int index)
    {
        if (index == str.length()) System.out.println(str);

        for (int i = index; i < str.length(); i++)
        {
            char prefix = str.charAt(i);
            String suffix = str.substring(0,i) + str.substring(i+1);

            myPerm(prefix + suffix, index + 1);
        }
    }
}

C#

我还使用新的c# 8.0范围操作符在c#中编写了该函数

    class Program
    {
        static void Main(string[] args)
        {
            myPerm("ABCD", 0);
        }

        private static void myPerm(string str, int index)
        {
            if (index == str.Length) Console.WriteLine(str);

            for (int i = index; i < str.Length; i++)
            {
                char prefix = str[i];
                string suffix = str[0..i] + str[(i + 1)..];

                myPerm(prefix + suffix, index + 1);
            }
        }
    

我们只是把每个字母放在开头,然后排列。 第一次迭代是这样的:

/*
myPerm("ABCD",0)  
  prefix = "A"  
  suffix = "BCD"  
  myPerm("ABCD",1)  
    prefix = "B"  
    suffix = "ACD"  
    myPerm("BACD",2)  
      prefix = "C"  
      suffix = "BAD"  
      myPerm("CBAD",3)  
        prefix = "D"  
        suffix = "CBA"  
        myPerm("DCBA",4)  
          Console.WriteLine("DCBA")
*/

下面是一个简单的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;
}