下面是两个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);
            }
        }

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

python实现

def getPermutation(s, prefix=''):
        if len(s) == 0:
                print prefix
        for i in range(len(s)):
                getPermutation(s[0:i]+s[i+1:len(s)],prefix+s[i] )



getPermutation('abcd','')

我的实现基于Mark Byers上面的描述:

    static Set<String> permutations(String str){
        if (str.isEmpty()){
            return Collections.singleton(str);
        }else{
            Set <String> set = new HashSet<>();
            for (int i=0; i<str.length(); i++)
                for (String s : permutations(str.substring(0, i) + str.substring(i+1)))
                    set.add(str.charAt(i) + s);
            return set;
        }
    }

简单的递归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

使用位操作可以很容易地做到这一点。“我们都知道，任何给定的有N个元素的集合有2N个可能的子集。如果我们用一个位来表示子集中的每个元素呢?位可以是0或1，因此我们可以用它来表示对应的元素是否属于这个给定的子集。所以每个位模式代表一个子集。”(复制文本)

private void getPermutation(String str)
        {
            if(str==null)
                return;
            Set<String> StrList = new HashSet<String>();
            StringBuilder strB= new StringBuilder();
            for(int i = 0;i < (1 << str.length()); ++i)
            {
                strB.setLength(0); //clear the StringBuilder
                for(int j = 0;j < str.length() ;++j){
                    if((i & (1 << j))>0){  // to check whether jth bit is set
                        strB.append(str.charAt(j));
                    }
                }
                if(!strB.toString().isEmpty())
                    StrList.add(strB.toString());
            }
            System.out.println(Arrays.toString(StrList.toArray()));
        }