100分求一道算法题答案，注意不是简单的组合问题

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

前几天发过一个帖子，有人嫌分数少，就又发了该贴，解决了一并给分。
http://topic.csdn.net/u/20110822/15/ed388ce7-d2f0-49e2-978f-1ba813dad187.html?seed=181980749&r=75124581#r_75124581

Answer 2

数学公式我会：
如：01234分成3份[2，2，1]
公式是：c52*c32/p22=15;
数学公式可以计算出有15个，但不知道是哪15个？

Answer 3

3个嵌套循环，每个循环都是这个位置所有可能的值，然后建立1个结果表，每次得到的临时结果都与结果表比较是否重复，不重复则加入结果表。这样循环完就可以得到正确答案。如
  准备空结果表
  for i=1 to 5
    for j=1 to 5
      for k=1 to 5
         判断i,j,k是否在结果表中，不重复再加入结果表
        结束
如果是m分n份，对照代入。

Answer 4

没仔细看题，少了个判断:
  判断i,j,k是否在结果表中，不重复再加入结果表
要改成
  先判断i<>j and j<>k and k<>i,然后再 判断i,j,k是否在结果表中，不重复再加入结果表

Answer 5

[url=http://bbs.9ria.com/thread-11466-1-1.html]这个也许对你有用LZurl]

Answer 6

[url=http://bbs.9ria.com/thread-11466-1-1.html]这个也许对你有用LZ[url]

Answer 7

我的算法代码有问题，但是思路是这样的，就是循环所有的可能，然后判断每个可能是否与结果表重复，再存入结果表。
如果是5个数分3份，2，2，1，还是要循环5次
for i1=1 to 5
for i2=1 to 5
  for j1=1 to 5
  for j2=1 to 5
     for k1=1 to 5
       先判断i1<>i2<>j1<>j2<>k1,然后再 判断i,j,k是否在结果表中，不重复再加入结果表
循环结束

Answer 8

将N个数分成M份，取K=（k1,k2,……,km)，其中K中元素代表每一份中数字的个数，由题意，可对数组K中的元素进行排序，规定；k1<=k2<=……<=km，并有k1+k2+……km=N，因此，N（10）个数分成M（3）份，其分法代码如下：static void Main(string[] args)
        {
            for (int k1 = 1; k1 <=10; k1++)
            {
                for (int k2 = k1; k2 <= 10; k2++)
                {
                    for (int k3 = k2; k3 <= 10; k3++)
                    {
                        if (k1 + k2 + k3 == 10)
                        {
                            Console.WriteLine("{0}+{1}+{2}={3}", k1, k2, k3, k1 + k2 + k3);
                            break;
                        }
                    }
                }
            }
            Console.Read();
        }//结果
//1+1+8=10
//1+2+7=10
//1+3+6=10
//1+4+5=10
//2+2+6=10
//2+3+5=10
//2+4+4=10
//3+3+4=10
再往下的还没想好

Answer 9

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 10

16楼老兄的程序测试过没？虽然猜测你的思路是用暴力算法，但粘贴以后编译不了哈。
(在下还没接触过Linq，是从代码里的单词猜测的，猜错了还请多包涵)

Answer 11

LZ的问题好像提得不是太清楚，没说清楚什么情况为重复的。按照LZ给的计算公式暂且推出以下条件：
1.每个分组视为一个组合，即相同数据但不同顺序的为同一分组；
2.分组的排列形式也按组合的标准，即两个分组数据相同，但位置调换后视为重复分组。我也来用暴力算法解下吧，下班再去想想有没有什么优化的方案：using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;namespace ConTest4
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] source = { 3, 5, 2, 7, 4 };
            int[] splits = { 2, 3 };            IList<IList<int>> list = GetAllPermutations(new List<int>(source));            Proc(list, splits);
        }        static IList<IList<int>> GetAllPermutations(IList<int> source)
        {
            IList<IList<int>> result = new List<IList<int>>();            if (source != null)
                if (source.Count > 1)
                {
                    int num = source[0];                    source.RemoveAt(0);                    IList<IList<int>> temp = GetAllPermutations(source);                    foreach (IList<int> list in temp)
                        for (int i = 0; i < list.Count + 1; i++)
                        {
                            IList<int> tempList = new List<int>(list);                            tempList.Insert(i, num);                            result.Add(tempList);                            
                        }
                }
                else
                    result.Add(new List<int>(source));            return (result);
        }        static void Proc(IList<IList<int>> source, int[] splits)
        {
            IList<IList<int[]>> temp = new List<IList<int[]>>();
            int sum = 0;            foreach (int split in splits)
                sum += Math.Max(0, split);            foreach (IList<int> list in source)
            {
                if (list.Count < sum)
                    continue;                StringBuilder sb = new StringBuilder();
                IList<int[]> tempList = new List<int[]>();
                int i = 0;                foreach (int split in splits)
                    if (split > 0)
                    {
                        int[] arr = new int[split];                        for (int j = 0; j < split; j++, i++)
                            arr[j] = list[i];                        Array.Sort(arr);                        for (int j = 0; j < split; j++)
                            sb.Append(j > 0 ? "," + arr[j] : "" + arr[j]);
                        sb.Append(";");
                        tempList.Add(arr);
                    }                if (!ContainsListEx(temp, tempList))
                {
                    Console.WriteLine(sb);                    temp.Add(tempList);
                }
            }
        }        static bool EqualsArrayEx(int[] a, int[] b)
        {
            if (a.Length == b.Length)
            {
                for (int i = 0; i < a.Length; i++)
                    if (a[i] != b[i])
                        return (false);                return (true);
            }            return (false);
        }        static bool ContainsListEx(IList<IList<int[]>> source, IList<int[]> targets)
        {
            int count;            foreach (IList<int[]> list in source)
            {
                count = 0;                foreach (int[] target in targets)
                    foreach (int[] arr in list)
                        if (EqualsArrayEx(target, arr))
                        {
                            count++;                            break;
                        }                if (count == targets.Count)
                    return (true);
            }            return (false);
        }
             
    }
}

Answer 12

貌似挺简单的；就是一个算法中的一个递归算法而已吧.
a[1][1]=1;a[2][1]=1;a[2][2]=1;
a[m][n]=a[m-1][n-1]+a[m-2][n-1]+....+a[n-1][n-1]
可以无限往上递归  就可以求得m分n份的总数(n<=m,每份中必须>1)

Answer 13

我也编译没过 。VS2008，不知道是不是2010没这个错误。Error 7 The best overloaded method match for 'string.Join(string, string[])' has some invalid arguments D:\Project\Wireless Plug-In\WIRELESSPLUGIN\TestConsoleApplication1\CustomComparer.cs 18 54 TestConsoleApplication1Error 8 Argument '2': cannot convert from 'System.Linq.IOrderedEnumerable<int>' to 'string[]' D:\Project\Wireless Plug-In\WIRELESSPLUGIN\TestConsoleApplication1\CustomComparer.cs 18 72 TestConsoleApplication1

Answer 14

本帖最后由 caozhy 于 2011-08-24 18:11:50 编辑

  

Answer 15

22楼的暴力解法简单明了，不失为一种方法，但是我觉得应该还有更好的方法！
如果：int[] source = { 0, 1, 2, 3, 4,5,6,7,8,9 };
      int[] splits = { 2, 2,2,2,2 };
用暴力解法速度相当的慢，因为大部分结果是重复的，时间都花在了比较数组相等上了！谁还有更妙的解法？