问题描述

用递归能实现一个数组划分的算法么？

用递归能实现一个数组划分的算法么？

给一个数组，长度为m，划分成n个子数组（每个数组起码有一个元素），比如
{1 2 3 4 5}划分成2个：
1, 2345 12,345 123,45 1234,5一共5个分法
{1234}分成3个
1,2,34 1,23,4 12,3,4，一共3个分法
求代码怎么写

解决方案

 IEnumerable<IEnumerable<IEnumerable<int>>> Split(IEnumerable<int> source, int n)
{
  int[] splitter = Enumerable.Range(1, n - 1).ToArray();
  splitter[n - 2]--;
  int[] lastsp = Enumerable.Range(source.Count() - n, n -1).ToArray();
  while (splitter.Zip(lastsp, (x, y) => x != y).Any(x => x == true))
  {
    for (int i = n - 2; i >= 0; i--)
    {
      if (splitter[i] < lastsp[i])
      {
        splitter[i]++;
        for (int j = i + 1; j < n - 1; j++)
        {
          splitter[j] = splitter[i] + j - i;
        }
        break;
      }
    }
    IEnumerable<int>[] result = new IEnumerable<int>[n];
    int acc = 0;
    for (int i = 0; i < n; i++)
    {
      if (i == n - 1)
      {
        result[i] = source.Skip(acc);
      }
      else
      {
        result[i] = source.Skip(acc).Take(splitter[i] - acc);
        acc = splitter[i];
      }
    }
    yield return result;
  }
}