[分享+散分]：高效率的全组合算法

Question

最近发现论坛上问全组合的问题挺多的，自己之前也在这里问过类似的问题，一直没有找到特别高效的算法。
这两天看到了下面这个帖子，
http://topic.csdn.net/u/20090216/18/9104bda7-6ea3-4899-973c-cb7aae6612d8.html
特意又考虑了一下。终于写出了自己认为效率比较高的算法，拿出来给大家评评看，欢迎大家批评指正：        static string[] m_Data = { "A", "B", "C", "D", "E" };         static void Main(string[] args)
        {
            Dictionary<string, int> dic = new Dictionary<string, int>();
            for (int i = 0; i < m_Data.Length; i++)
            {
                Console.WriteLine(m_Data[i]);//如果不需要打印单元素的组合，将此句注释掉
                dic.Add(m_Data[i], i);
            }
            GetString(dic);
            Console.ReadLine();
        }        static void GetString(Dictionary<string,int> dd)
        {
            Dictionary<string, int> dic = new Dictionary<string, int>();
            foreach (KeyValuePair<string, int> kv in dd)
            {
                for (int i = kv.Value + 1; i < m_Data.Length; i++)
                {
                    Console.WriteLine(kv.Key + m_Data[i]);
                    dic.Add(kv.Key + m_Data[i], i);
                }
            }
            if(dic.Count>0) GetString(dic);
        }运行结果：
A
B
C
D
E
AB
AC
AD
AE
BC
BD
BE
CD
CE
DE
ABC
ABD
ABE
ACD
ACE
ADE
BCD
BCE
BDE
CDE
ABCD
ABCE
ABDE
ACDE
BCDE
ABCDE

Answer 1

蛮好的
像这种String为Key的可以使用System.Collections.Specialized.StringDictionary

Answer 2

我也来一个，不过输出顺序比较乱:        static void Main(string[] args)
        {
            string[] arr = new[] { "A", "B", "C", "D", "E" };
            GetCombination(arr);
        }        static void GetCombination(string[] nums)
        {
            double count = Math.Pow(2, nums.Length);
            for (int i = 1; i <= count - 1; i++)
            {
                string str = Convert.ToString(i, 2).PadLeft(nums.Length, '0');
                for (int j = 0; j < str.Length; j++)
                {
                    if (str[j] == '1')
                    {
                        Console.Write(nums[j]);
                    }
                }
                Console.WriteLine();
            }
        }
/*
输出:
E
D
DE
C
CE
CD
CDE
B
BE
BD
BDE
BC
BCE
BCD
BCDE
A
AE
AD
ADE
AC
ACE
ACD
ACDE
AB
ABE
ABD
ABDE
ABC
ABCE
ABCD
ABCDE
*/

Answer 3

注释还真不好加，我举个例子：
假如当kv的值为<"BC",2>，那么执行下面的for循环,                for (int i = kv.Value + 1; i < m_Data.Length; i++)
                {
                    Console.WriteLine(kv.Key + m_Data[i]);
                    dic.Add(kv.Key + m_Data[i], i);
                }
就可以得到：
<"BCD",3>和<"BCE",4>，将这两个值添加到dic中
然后再执行递归。
不知道这样说明白了没有？

Answer 4

写了个非递归的，望高手指点
using System;
using System.Collections.Generic;
namespace Test
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] m_Data = { "A", "B", "C", "D", "E" };
            List<string> list = new List<string>();
            List<string> temp = new List<string>();
            List<string> result = new List<string>();
            int n = m_Data.Length;
            string t;
            string sEnd = m_Data[n-1];
            int i = 0;
            while (i<5)
            {
                t = m_Data[i];
                temp.Add(t);
                foreach (string s in list)
                {
                    result.Add(t + s);
                    temp.Add(t + s);
                }
                list.AddRange(temp);
                temp.Clear();
                i++;
            }
            foreach (string s in result)
            {
                Console.WriteLine(s);
            }
        }
    }
}
输出:
BA
CA
CB
CBA
DA
DB
DBA
DC
DCA
DCB
DCBA
EA
EB
EBA
EC
ECA
ECB
ECBA
ED
EDA
EDB
EDBA
EDC
EDCA
EDCB
EDCBA

Answer 5

C++实现，敢问还有更高效的么？可以用计时器测试一下，比一比！
// 算法说明：当n大于2时，n个数的全组合一共有(2^n)-1种。
// 当对n个元素进行全组合的时候，可以用一个n位的二进制数表示取法。
// 1表示在该位取，0表示不取。例如，对ABC三个元素进行全组合，
// 100表示取A，010表示取B，001表示取C，101表示取AC
// 110表示取AB，011表示取BC，111表示取ABC
// 注意到表示取法的二进制数其实就是从1到7的十进制数
// 推广到对n个元素进行全排列，取法就是从1到2^n-1的所有二进制形式
// 要取得2^n，只需将0xFFFFFFFF左移32-n位，再右移回来就可以了。#include <iostream>
using namespace std;
void main()
{
string str[] = { "A", "B", "C", "D", "E" };
unsigned int nCnt = sizeof( str ) / sizeof( str[0] );
int nBit = ( ( 0xFFFFFFFFU << ( 32 - nCnt ) ) >> ( 32 - nCnt ) );
for ( int i = 1; i <= nBit; ++i ) {
for ( unsigned int j = 0; j < nCnt; ++j )
if ( ( i << ( 31 - j ) ) >> 31 ) cout << str[j];
cout << '\n';
}
return;
}

Answer 6

有点瑕疵，8行有效代码以最高效率搞定！
#include <iostream>
void main( void )
{
string str[] = { "A", "B", "C", "D", "E" };
unsigned int nCnt = sizeof( str ) / sizeof( str[0] );
int nBit = ( ( 0xFFFFFFFFU << ( 32 - nCnt ) ) >> ( 32 - nCnt ) );
for ( int i = 1; i <= nBit; ++i ) {
for ( unsigned int j = 0; j < nCnt; ++j )
if ( ( i << ( 31 - j ) ) >> 31 ) std::cout << str[j];
std::cout << '\n';
}
}

Answer 7

good thing and thank you