这可以通过简单地在前面部分结果的所有位置依次插入字符串的每个字母来迭代完成。

我们以[A]开头，与B连成[BA, AB]，与C连成[CBA, BCA, BAC, CAB等]。

运行时间将是O(n!)，对于测试用例ABCD，它是1 x 2 x 3 x 4。

在上面的乘积中，1是A, 2是B，以此类推。

飞镖示例:

void main() {

  String insertAt(String a, String b, int index)
  {
    return a.substring(0, index) + b + a.substring(index);
  }

  List<String> Permute(String word) {

    var letters = word.split('');

    var p_list = [ letters.first ];

    for (var c in letters.sublist(1)) {

      var new_list = [ ];

      for (var p in p_list)
        for (int i = 0; i <= p.length; i++)
          new_list.add(insertAt(p, c, i));

      p_list = new_list;
    }

    return p_list;
  }

  print(Permute("ABCD"));

}

这对我很有效。

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

在这里和其他论坛给出的所有解决方案中，我最喜欢Mark Byers。这个描述实际上让我自己思考并编写了代码。 可惜我不能投票支持他的解决方案，因为我是新手。 无论如何，这是我对他的描述的实现

public class PermTest {

    public static void main(String[] args) throws Exception {
        String str = "abcdef";
        StringBuffer strBuf = new StringBuffer(str);
        doPerm(strBuf,0);
    }

    private static void doPerm(StringBuffer str, int index){

        if(index == str.length())
            System.out.println(str);            
        else { //recursively solve this by placing all other chars at current first pos
            doPerm(str, index+1);
            for (int i = index+1; i < str.length(); i++) {//start swapping all other chars with current first char
                swap(str,index, i);
                doPerm(str, index+1);
                swap(str,i, index);//restore back my string buffer
            }
        }
    }

    private  static void swap(StringBuffer str, int pos1, int pos2){
        char t1 = str.charAt(pos1);
        str.setCharAt(pos1, str.charAt(pos2));
        str.setCharAt(pos2, t1);
    }
}   

我更喜欢这个解决方案，而不是第一个解决方案，因为这个解决方案使用StringBuffer。我不会说我的解决方案没有创建任何临时字符串(它实际上在system.out.println中创建，其中调用StringBuffer的toString())。但我只是觉得这比第一个解决方案好太多的字符串字面值被创建。可能有些性能人员可以根据“内存”来评估这一点(对于“时间”来说，由于额外的“交换”，它已经滞后了)

//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--]);
        }
    }
}

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, "");
}

}

简单的递归c++实现如下所示:

#include <iostream>

void generatePermutations(std::string &sequence, int index){
    if(index == sequence.size()){
        std::cout << sequence << "\n";
    } else{
        generatePermutations(sequence, index + 1);
        for(int i = index + 1 ; i < sequence.size() ; ++i){
            std::swap(sequence[index], sequence[i]);
            generatePermutations(sequence, index + 1);
            std::swap(sequence[index], sequence[i]);            
        }
    }
}

int main(int argc, char const *argv[])
{
    std::string str = "abc";
    generatePermutations(str, 0);
    return 0;
}

输出:

abc
acb
bac
bca
cba
cab

更新

如果想要存储结果，可以将vector作为函数调用的第三个参数传递。此外，如果您只想要唯一的排列，您可以使用集合。

#include <iostream>
#include <vector>
#include <set>

void generatePermutations(std::string &sequence, int index, std::vector <std::string> &v){
    if(index == sequence.size()){
        //std::cout << sequence << "\n";
        v.push_back(sequence);
    } else{
        generatePermutations(sequence, index + 1, v);
        for(int i = index + 1 ; i < sequence.size() ; ++i){
            std::swap(sequence[index], sequence[i]);
            generatePermutations(sequence, index + 1, v);
            std::swap(sequence[index], sequence[i]);            
        }
    }
}

int main(int argc, char const *argv[])
{
    std::string str = "112";
    std::vector <std::string> permutations;
    generatePermutations(str, 0, permutations);
    std::cout << "Number of permutations " << permutations.size() << "\n";
    for(const std::string &s : permutations){
        std::cout << s << "\n";
    }
    std::set <std::string> uniquePermutations(permutations.begin(), permutations.end());
    std::cout << "Number of unique permutations " << uniquePermutations.size() << "\n";
    for(const std::string &s : uniquePermutations){
        std::cout << s << "\n";
    }
    return 0;
}

输出:

Number of permutations 6
112
121
112
121
211
211
Number of unique permutations 3
112
121
211