一道算法题,自己想出来的,求答案!

Question

将m个数字随机分成n份,问有多少种分法?并输出所有的分法!
如:5个数字分成3份,分别是2,2,1个数字,问有多少种分法,当然不能重复!我们用数学公式可以算出上面一共15种分法,如何用C#程序输出所有的分法呢?也就是实现这样一个函数List<List<int[]>> GetAllCom(int m,int[] nf)
{
    ...
}输入:m=5,
nf=new int[]{2,2,1}输出:
List:{
{ [0,1],[2,3],[4]},
{ [0,2],[1,3],[4]},
...
}

Answer 1

本帖最后由 caozhy 于 2011-08-22 20:27:55 编辑

  

Answer 2

有人嫌分数少，只好又发了一个贴。解决了一并给分
http://topic.csdn.net/u/20110824/08/0b86dcdc-04aa-4848-874e-6f20de40eb55.html

Answer 3

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;namespace ConsoleApplication1
{
    class CustomComparer : IEqualityComparer<List<List<int>>>
    {
        public bool Equals(List<List<int>> x, List<List<int>> y)
        {
            return GetHashCode(x) == GetHashCode(y);
        }        public int GetHashCode(List<List<int>> obj)
        {
            return string.Join("; ", obj.Select(y => string.Join(", ", y.OrderBy(x => x))).OrderBy(x => x)).GetHashCode();
        }
    }    class Program
    {
        static void Main(string[] args)
        {
            var result = solve(5, new int[] { 2, 2, 1 }).Distinct(new CustomComparer()).ToList();
            result.ForEach(x =>
                Console.WriteLine(string.Join("; ", x.Select(y => string.Join(", ", y)))));
        }        static IEnumerable<List<List<int>>> solve(int n, int[] split)
        {
            foreach (var item in Arrange(Enumerable.Range(0, n).ToList(), new List<int>()))
            {
                List<List<int>> result = new List<List<int>>();
                for (int i = 0; i < split.GetLength(0); i++)
                {
                    result.Add(item.Skip(split.Take(i).Sum()).Take(split[i]).ToList());
                }
                yield return result;
            }
        }        static IEnumerable<List<T>> Arrange<T>(List<T> source, List<T> current)
        {
            if (current.Count == source.Count)
                yield return current;
            else
                foreach (var item in source)
                    if (!current.Any(x => x.Equals(item)))
                        foreach (var item1 in Arrange(source, current.Union(new List<T>() { item }).ToList()))
                            yield return item1;
        }    }
}
0, 1; 2, 3; 4
0, 1; 2, 4; 3
0, 1; 3, 4; 2
0, 2; 1, 3; 4
0, 2; 1, 4; 3
0, 2; 3, 4; 1
0, 3; 1, 2; 4
0, 3; 1, 4; 2
0, 3; 2, 4; 1
0, 4; 1, 2; 3
0, 4; 1, 3; 2
0, 4; 2, 3; 1
1, 2; 3, 4; 0
1, 3; 2, 4; 0
1, 4; 2, 3; 0
Press any key to continue . . .

Answer 4

5取3排列组合？ 这个在math上不是有现成的方法么？