求.NET的一个排列组合

f(1) = 1
之后直接for都可以写出来了

从后第一个往前拼接，循环n-1遍，把结果保存到result。
再从后第二个往前拼接，循环n-2遍，把结果合并到result。
依次。。
最后得到所有result。

参考http://www.cnblogs.com/rogerwei/archive/2010/11/18/1880336.html//-----------------------------------------------------------------------------
//
// 算法：排列组合类
//
// 版权所有(C) Snowdust
// 个人博客    http://blog.csdn.net/snowdust & http://snowdust.cnblogs.com
// MSN & Email [email protected]
//
// 此源代码可免费用于各类软件（含商业软件）
// 允许对此代码的进一步修改与开发
// 但必须完整保留此版权信息
//
//-----------------------------------------------------------------------------/// <summary>
/// 递归算法求数组的组合(私有成员)
/// </summary>
/// <param name="list">返回的范型</param>
/// <param name="t">所求数组</param>
/// <param name="n">辅助变量</param>
/// <param name="m">辅助变量</param>
/// <param name="b">辅助数组</param>
/// <param name="M">辅助变量M</param>
private static void GetCombination<T>(ref List<T[]> list, T[] t, int n, int m, int[] b, int M)
{
    for (int i = n; i >= m; i--)
    {
        b[m - 1] = i - 1;
        if (m > 1)
        {
            GetCombination(ref list, t, i - 1, m - 1, b, M);
        }
        else
        {
            if (list == null)
            {
                list = new List<T[]>();
            }
            T[] temp = new T[M];
            for (int j = 0; j < b.Length; j++)
            {
                temp[j] = t[b[j]];
            }
            list.Add(temp);
        }
    }
}/// <summary>
/// 求数组中n个元素的组合
/// </summary>
/// <param name="t">所求数组</param>
/// <param name="n">元素个数</param>
/// <returns>数组中n个元素的组合的范型</returns>
public static List<T[]> GetCombination<T>(T[] t, int n)
{
    if (t.Length < n)
    {
        return null;
    }
    int[] temp = new int[n];
    List<T[]> list = new List<T[]>();
    GetCombination(ref list, t, t.Length, n, temp, n);
    return list;
}应用int[] arr = {1,2,3};
List<int[]> result = new List<int[]>();
for(int i = 0; i < arr.Length; i++)
{
result.AddRange(GetCombination(arr, i+1));
}
// 输出
foreach(int[] varr in result)
{
foreach(int vnum in varr)
{
Console.Write(vnum.ToString() + " ");
}
Console.WriteLine("");
}
/*
3
2
1
2 3
1 3
1 2
1 2 3
*/

      static void Main(string[] args)
        {
            ShowResult();
        }      public static void ShowResult()
      {
          string str = "1,2,3";
          string[] temp1 = str.Split(',');
          List<string> list = new List<string>();
          foreach (string s in temp1)
          {
              if (list.Count == 0)
                  list.AddRange(temp1);
              else
                  list.AddRange(JoinPart(list, s));
          }
          foreach (string s in list)
              Console.WriteLine(s);
      }
      public static List<string> JoinPart(List<string> part1, string s)
      {
          List<string> result = new List<string>();
          foreach (string str1 in part1)
          {
              result.Add(str1 + s);
          }

          return result;
      }
/*
1
2
3
12
22
32
13
23
33
123
223
323
*/

其实1楼给的公式也没错，非常正确。这里的f(n)就是组合数，但要将内容显示则是通过循环+二进制位运算，其效率是最高的算法，因为没有比位运算的效率更高的算法，其中只用到循环而没有用到递归。另外他这个f(n)的求解比较麻烦，永远是依赖上个值，意味着要递归求解，因此我改下算法，变为这样:f(n) = 2^n - 1，这样计算就方便多了。
下面给出最佳算法，速度非常快。public static List<List<T>> GetCombination<T>(T[] t)
{
    List<List<T>> result = new List<List<T>>();
    int length = t.Length;
    int num = (int)Math.Pow(2, length) - 1;
    for (int i = 1; i <= num; i++)
    {
        List<T> tmp = new List<T>();
        for (int j = 0; j < length; j++)
        {
            if ((i >> j) % 2 == 1)
                tmp.Add(t[j]);
        }
        result.Add(tmp);
    }
    return result;
}
static void Main(string[] args)
{
    int[] arr = { 1, 2, 3 };
    List<List<int>> result = GetCombination(arr);
    foreach (List<int> varr in result)
    {
        foreach (int vnum in varr)
        {
            Console.Write(vnum.ToString() + " ");
        }
    }
}
/*
输出
1
2
1 2
3
1 3
2 3
1 2 3
*/

   System.Collections.Generic.List<string> sum;
    protected void Page_Load(object sender, EventArgs e)
    {
        sum = new System.Collections.Generic.List<string>();
        System.Collections.Generic.List<int> list = new System.Collections.Generic.List<int>() { 1,2,3};
        bind(list, new System.Collections.Generic.List<int>(), 0, 1);
        foreach (string s in sum.OrderBy(t => t.Length))
            Response.Write(s);
    }
    private void bind(System.Collections.Generic.List<int> list, System.Collections.Generic.List<int> source, int index, int count)
    {
        if (source.Count <= count)
        {
            printf(source);
        }
        for (int i = index; i < list.Count; i++)
        {
            if (source.Contains(list[i]))
                continue;
            source.Add(list[i]);
            bind(list, source, i, count + 1);
            source.Remove(list[i]);
        }
    }
    private void printf(System.Collections.Generic.List<int> List)
    {
        for (int i = 0; i < List.Count - 1; i++)
            if (List[i] >= List[i + 1])
                return;
        string str = "";
        for (int i = 0; i < List.Count; i++)
        {
            str += List[i];
            if (i < List.Count - 1)
            {
                str += ",";
            }
        }
        str += "<br/>";
        sum.Add(str);
    }

调试易

求.NET的一个排列组合

解决方案 »