我们可以用阶乘来计算有多少字符串以某个字母开头。

示例:取输入abcd。(3!) == 6个字符串将以abcd中的每个字母开头。

static public int facts(int x){
    int sum = 1;
    for (int i = 1; i < x; i++) {
        sum *= (i+1);
    }
    return sum;
}

public static void permutation(String str) {
    char[] str2 = str.toCharArray();
    int n = str2.length;
    int permutation = 0;
    if (n == 1) {
        System.out.println(str2[0]);
    } else if (n == 2) {
        System.out.println(str2[0] + "" + str2[1]);
        System.out.println(str2[1] + "" + str2[0]);
    } else {
        for (int i = 0; i < n; i++) {
            if (true) {
                char[] str3 = str.toCharArray();
                char temp = str3[i];
                str3[i] = str3[0];
                str3[0] = temp;
                str2 = str3;
            }

            for (int j = 1, count = 0; count < facts(n-1); j++, count++) {
                if (j != n-1) {
                    char temp1 = str2[j+1];
                    str2[j+1] = str2[j];
                    str2[j] = temp1;
                } else {
                    char temp1 = str2[n-1];
                    str2[n-1] = str2[1];
                    str2[1] = temp1;
                    j = 1;
                } // end of else block
                permutation++;
                System.out.print("permutation " + permutation + " is   -> ");
                for (int k = 0; k < n; k++) {
                    System.out.print(str2[k]);
                } // end of loop k
                System.out.println();
            } // end of loop j
        } // end of loop i
    }
}

改进的代码相同

    static String permutationStr[];
    static int indexStr = 0;

    static int factorial (int i) {
        if (i == 1)
            return 1;
        else
            return i * factorial(i-1);
    }

    public static void permutation(String str) {
        char strArr[] = str.toLowerCase().toCharArray();
        java.util.Arrays.sort(strArr);

        int count = 1, dr = 1;
        for (int i = 0; i < strArr.length-1; i++){
            if ( strArr[i] == strArr[i+1]) {
                count++;
            } else {
                dr *= factorial(count);
                count = 1;
            }       
        }
        dr *= factorial(count);

        count = factorial(strArr.length) / dr;

        permutationStr = new String[count];

        permutation("", str);

        for (String oneStr : permutationStr){
            System.out.println(oneStr);
        }
    }

    private static void permutation(String prefix, String str) {
        int n = str.length();
        if (n == 0) {
            for (int i = 0; i < indexStr; i++){
                if(permutationStr[i].equals(prefix))
                    return;
            }        
            permutationStr[indexStr++] = prefix;
        } else {
            for (int i = 0; i < n; i++) {
                permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, 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")
*/

public class StringPermutation {

// Function to print all the permutations of str
static void printPermutn(String str, String ans) {

    // If string is empty
    if (str.length() == 0) {
        System.out.print(ans + " ");
        return;
    }

    for (int i = 0; i < str.length(); i++) {

        // ith character of str
        char ch = str.charAt(i);

        // Rest of the string after excluding
        // the ith character
        String ros = str.substring(0, i) + str.substring(i + 1);

        // Recurvise call
        printPermutn(ros, ans + ch);
    }
}


public static void main(String[] args) {
    String s = "ABC";
    printPermutn(s, "");
}

}

这是一个具有O(n!)时间复杂度的算法，具有纯递归和直观。

public class words {
static String combinations;
public static List<String> arrlist=new ArrayList<>();
public static void main(String[] args) {
    words obj = new words();

    String str="premandl";
    obj.getcombination(str, str.length()-1, "");
    System.out.println(arrlist);

}


public void getcombination(String str, int charIndex, String output) {

    if (str.length() == 0) {
        arrlist.add(output);
        return ;
    }

    if (charIndex == -1) {
        return ;
    }

    String character = str.toCharArray()[charIndex] + "";
    getcombination(str, --charIndex, output);

    String remaining = "";

    output = output + character;

    remaining = str.substring(0, charIndex + 1) + str.substring(charIndex + 2);

    getcombination(remaining, remaining.length() - 1, output);

}

}

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