求一个排列组合算法，高分！

有一个一字符串维数组，string[] F；F的长度为N；有M个不同的字符，每个字符都可以填充到F的任一一个位置，求把F填充完的不同组合的集合；

例如：string[] F的长度为4，有“A”，“B”，“C”三个字符元素，用来填充F，F可能的排列就有：AAAA，ABCA，AABC，CBAB等等。要得到所有可能的组合的集合。

同时考虑执行效率。

能给出具体代码最好。

百度，全排列算法

晕

穷举还要啥效率~~~~~~~~

递归实现：
C# code

    public class Program
    {
        static List<string> GetCombination(int length, char[] chars, List<string> strList) {
            if (strList.Count == 0) {
                strList.Add("");
            }
            if (strList[0].Length >= length) {
                return strList;
            }
            List<string> newList = new List<string>(chars.Length * strList.Count);
            foreach (var str in strList) {
                foreach (var c in chars) {
                    newList.Add(str+c);
                }
            }
            return GetCombination(length, chars, newList);
        }

        static void Main(string[] args) {
            List<string> result = GetCombination(4, "ABCD".ToCharArray(), new List<string>());
            foreach (var str in result) {
                Console.WriteLine(str);
            }
        }
    }

Assembly code

AAAA
AAAB
AAAC
AAAD
AABA
AABB
AABC
AABD
AACA
AACB
AACC
AACD
AADA
AADB
AADC
AADD
ABAA
ABAB
ABAC
ABAD
ABBA
ABBB
ABBC
ABBD
ABCA
ABCB
ABCC
ABCD
ABDA
ABDB
ABDC
ABDD
ACAA
ACAB
ACAC
ACAD
ACBA
ACBB
ACBC
ACBD
ACCA
ACCB
ACCC
ACCD
ACDA
ACDB
ACDC
ACDD
ADAA
ADAB
ADAC
ADAD
ADBA
ADBB
ADBC
ADBD
ADCA
ADCB
ADCC
ADCD
ADDA
ADDB
ADDC
ADDD
BAAA
BAAB
BAAC
BAAD
BABA
BABB
BABC
BABD
BACA
BACB
BACC
BACD
BADA
BADB
BADC
BADD
BBAA
BBAB
BBAC
BBAD
BBBA
BBBB
BBBC
BBBD
BBCA
BBCB
BBCC
BBCD
BBDA
BBDB
BBDC
BBDD
BCAA
BCAB
BCAC
BCAD
BCBA
BCBB
BCBC
BCBD
BCCA
BCCB
BCCC
BCCD
BCDA
BCDB
BCDC
BCDD
BDAA
BDAB
BDAC
BDAD
BDBA
BDBB
BDBC
BDBD
BDCA
BDCB
BDCC
BDCD
BDDA
BDDB
BDDC
BDDD
CAAA
CAAB
CAAC
CAAD
CABA
CABB
CABC
CABD
CACA
CACB
CACC
CACD
CADA
CADB
CADC
CADD
CBAA
CBAB
CBAC
CBAD
CBBA
CBBB
CBBC
CBBD
CBCA
CBCB
CBCC
CBCD
CBDA
CBDB
CBDC
CBDD
CCAA
CCAB
CCAC
CCAD
CCBA
CCBB
CCBC
CCBD
CCCA
CCCB
CCCC
CCCD
CCDA
CCDB
CCDC
CCDD
CDAA
CDAB
CDAC
CDAD
CDBA
CDBB
CDBC
CDBD
CDCA
CDCB
CDCC
CDCD
CDDA
CDDB
CDDC
CDDD
DAAA
DAAB
DAAC
DAAD
DABA
DABB
DABC
DABD
DACA
DACB
DACC
DACD
DADA
DADB
DADC
DADD
DBAA
DBAB
DBAC
DBAD
DBBA
DBBB
DBBC
DBBD
DBCA
DBCB
DBCC
DBCD
DBDA
DBDB
DBDC
DBDD
DCAA
DCAB
DCAC
DCAD
DCBA
DCBB
DCBC
DCBD
DCCA
DCCB
DCCC
DCCD
DCDA
DCDB
DCDC
DCDD
DDAA
DDAB
DDAC
DDAD
DDBA
DDBB
DDBC
DDBD
DDCA
DDCB
DDCC
DDCD
DDDA
DDDB
DDDC
DDDD
Press any key to continue . . .

那啥...严格来说这不是排列

不需要递归。
C# code

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            string Element = "ABC";
            int NeedLength = 4;
            Arrange(Element, NeedLength).ToList().ForEach(x => Console.WriteLine(x));
        }

        static IEnumerable<string> Arrange(string Element, int NeedLength)
        {
            IEnumerable<string> e = Element.Select(x => new string(new char[] { x }));
            var r = e;
            for (int i = 0; i < NeedLength - 1; i++)
                r = from x in r join y in e on 1 equals 1 select x + y; 
            return r;
        }
    }
}

另外这个题可以当作数字转字符串来解,效率更高.
就lz的例子来说.

可以当做"4位3进制数转字符串问题"

AAAA
AAAB
AAAC
AABA
AABB
AABC
AACA
AACB
AACC
ABAA
ABAB
ABAC
ABBA
ABBB
ABBC
ABCA
ABCB
ABCC
ACAA
ACAB
ACAC
ACBA
ACBB
ACBC
ACCA
ACCB
ACCC
BAAA
BAAB
BAAC
BABA
BABB
BABC
BACA
BACB
BACC
BBAA
BBAB
BBAC
BBBA
BBBB
BBBC
BBCA
BBCB
BBCC
BCAA
BCAB
BCAC
BCBA
BCBB
BCBC
BCCA
BCCB
BCCC
CAAA
CAAB
CAAC
CABA
CABB
CABC
CACA
CACB
CACC
CBAA
CBAB
CBAC
CBBA
CBBB
CBBC
CBCA
CBCB
CBCC
CCAA
CCAB
CCAC
CCBA
CCBB
CCBC
CCCA
CCCB
CCCC
Press any key to continue . . .

C# code

using System;
using System.Text;


public class IntConvert
{
    public static string Itos(string charset, int value, int n = 1)
    {
        StringBuilder ret = new StringBuilder(10);
        if (value == 0)
        {
            ret.Append(charset[0], n);
            return ret.ToString();
        }
        
        while (value > 0)
        {
            ret.Append(charset[value % charset.Length]);
            value /= charset.Length;
        }
        //补位
        var c = n - ret.Length;
        ret.Append(charset[0], c);

        //如果是用作进制转换,则需要加上最后的反转
        //int lastChIdx = ret.Length - 1;
        ////反转字符串
        //for (var i = 0; i < ret.Length / 2; ++i)
        //{
        //    var tmp = ret[i];
        //    ret[i] = ret[lastChIdx - i];
        //    ret[lastChIdx - i] = tmp;
        //}
        
        return ret.ToString();
    }
    static void Main()
    {
        string charset = "ABC";
        int n = 4;
        int max = (int)Math.Pow(charset.Length, n);
        for (int i=0;i< max;++i)
            Console.WriteLine(Itos(charset, i, 4));
    }
}

C# code

using System;
using System.Text;


public class IntConvert
{
    public static string Itos(string charset, int value, int n = 1)
    {
        StringBuilder ret = new StringBuilder(10);

        while (value > 0)
        {
            ret.Append(charset[value % charset.Length]);
            value /= charset.Length;
        }
        //补位
        var c = n - ret.Length;
        ret.Append(charset[0], c);

        //如果是用作进制转换,则需要加上最后的反转
        //int lastChIdx = ret.Length - 1;
        ////反转字符串
        //for (var i = 0; i < ret.Length / 2; ++i)
        //{
        //    var tmp = ret[i];
        //    ret[i] = ret[lastChIdx - i];
        //    ret[lastChIdx - i] = tmp;
        //}
        
        return ret.ToString();
    }
    static void Main()
    {
        string charset = "ABC";
        int n = 4;
        int max = (int)Math.Pow(charset.Length, n);
        for (int i=0;i< max;++i)
            Console.WriteLine(Itos(charset, i, 4));
    }
}

稍微改了下,删掉了冗余的判断..

楼上，你这个代码是做什么的哦？

递归容易理解

递归容易理解的前提是问题本身不容易理解

编译运行一下就知道了.
和caozhy原理不同功能等价.

想想从前，自己也为优化这类指数级算法投入过不少精力，包括自己写栈来模拟递归，或者像兔子同志一样搞3进制甚至混合进制，还为此学习了格雷码。只是后来不知道为什么，写着写着最后都写成递归了。大概也是对Linq和Lambda表达式不熟造成的。