[分享+散分]：高效率的全组合算法
最近发现论坛上问全组合的问题挺多的，自己之前也在这里问过类似的问题，一直没有找到特别高效的算法。
这两天看到了下面这个帖子，
http://topic.csdn.net/u/20090216/18/9104bda7-6ea3-4899-973c-cb7aae6612d8.html
特意又考虑了一下。终于写出了自己认为效率比较高的算法，拿出来给大家评评看，欢迎大家批评指正：
- C# code
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
[解决办法]
up
[解决办法]
蛮好的
像这种String为Key的可以使用System.Collections.Specialized.StringDictionary
[解决办法]
向楼主学习啊。。高手！！！！！！！！！！！！
[解决办法]
学习~
[解决办法]
我也来一个，不过输出顺序比较乱:
- C# code
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(); } }/*输出:EDDECCECDCDEBBEBDBDEBCBCEBCDBCDEAAEADADEACACEACDACDEABABEABDABDEABCABCEABCDABCDE*/
[解决办法]
学习！！！
[解决办法]
楼主写的不错，就是没有诚心与网友们分享。
试问没有注释的代码怎么分享？
[解决办法]
[解决办法]
学习！
[解决办法]
厉害
[解决办法]
刚好对我有用，谢了
[解决办法]
up
[解决办法]
[解决办法]
写了个非递归的，望高手指点
- C# code
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); } } }}
[解决办法]
这种组合，使用下标发是最好的。
下标还能进行有序筛选。
例如可重复使用和不可重复使用等情况。
[解决办法]
ding
[解决办法]
看起来不错的
[解决办法]
UP
[解决办法]
向楼主学习啊。。高手！！！！！！！！！！！！
[解决办法]
学习:)
[解决办法]
向楼主学习 要是能写点注释就更好了
[解决办法]
嗯,确实挺不错的.
[解决办法]
的确是高手
[解决办法]
good
[解决办法]
up
[解决办法]
mark
[解决办法]
up
[解决办法]
收藏，学习！~
[解决办法]
up
[解决办法]
学习了。
[解决办法]
mark
[解决办法]
学习uP
[解决办法]
插入
[解决办法]
学习学习
[解决办法]
up！
学习了！
[解决办法]
这已经有理论表明, 时间复杂度就是O(2^n), 分别在于用简洁的递归还是自己搞栈消除递归而已.
[解决办法]
好呀，想法不错
------解决方案--------------------
jf
[解决办法]
学习中！
[解决办法]
up
[解决办法]
mark 不过我觉的循环是不是比递归好点
递归不过很简洁
当只有A ，B两个时 递归好像还要多判断一次 不知道我的理解对不
呵呵 希望大家指点
[解决办法]
谢谢楼主分享！！！
[解决办法]
支持
[解决办法]
up
[解决办法]
up...
[解决办法]
mark
[解决办法]
学习中
有谁能在vc6.0中写一个呢？
[解决办法]
UP...
[解决办法]
这个算法我收藏了，呵呵，谢谢分享
[解决办法]
up。
很好很强大
[解决办法]
好东西，不顶不行
[解决办法]
支持
[解决办法]
不错，收藏
[解决办法]
谢谢楼主分享！！！
[解决办法]
jf
[解决办法]
ding
[解决办法]
很好！学习中
[解决办法]
看不懂的人写了注释也照样不懂。
[解决办法]
mark
[解决办法]
学习。。谢谢分享
[解决办法]
谢谢
[解决办法]
顶一个，学习
[解决办法]
收藏了~
[解决办法]
学习 了
[解决办法]
mark up!
[解决办法]
高人 厉害 学习 鼎鼎
[解决办法]
好！！！好东西！
[解决办法]
收藏
[解决办法]
学习~~~~~~~
[解决办法]
要是再注释下就更好了，但是还是很喜欢楼主的精神。。顶~~~~~~~~~~~
[解决办法]
mark
[解决办法]
帮顶了，顺便接分。
最重要的还是学习了。
[解决办法]
学习！
[解决办法]
GOOG
[解决办法]
学习
[解决办法]
一共才几行代码。。还得要个注释。。
有点像去公交车上刷卡还要管乘务员要发票的感觉。。
[解决办法]
学习了
[解决办法]
学习了
[解决办法]
学习
[解决办法]
学习了
[解决办法]
学习学习！
[解决办法]
学习
[解决办法]
C++实现，敢问还有更高效的么？可以用计时器测试一下，比一比！
- C/C++ code
// 算法说明：当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;}
[解决办法]
学习了
[解决办法]
有点瑕疵，8行有效代码以最高效率搞定！
- C/C++ code
#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'; }}
[解决办法]
学习...
[解决办法]
支持支持。给分
[解决办法]
不错，学习~
[解决办法]
学习
[解决办法]
good thing and thank you
[解决办法]
学习
[解决办法]
up
[解决办法]
噢，晓习
[解决办法]
路过！！
[解决办法]
mark 学习