Получить все параметры разделения на k кусков

У вас есть комбинаторная проблема: для заданного массива n элементов вы должны выбрать k подмассивы или, другими словами, k - 1 отделить от n - 1:

  [A, B, C, D, E]    n items, n - 1 possible splits 
     ^     ^ 
     |     |         k - 1 splits from n - 1 avaialable
     |     |
  [A] [B, C] [D, E]  k chunks   

Обратите внимание, что у нас есть стандартная комбинаторная задача

k - 1 из n - 1 неупорядоченно без повторов

Код для такой выборки может быть

private static IEnumerable<int[]> Samples(int take, int from) {
  if (take > from || take <= 0 || from <= 0)
    yield break;

  int[] array = Enumerable.Range(0, take).ToArray();

  for (bool agenda = true; agenda; ) {
    agenda = false;

    yield return array.ToArray();

    for (int i = array.Length - 1; i >= 0; --i) 
      if (array[i] < from - take + i) {
        agenda = true;

        array[i] += 1;

        for (int j = i + 1; j < array.Length; ++j)
          array[j] = array[i] + j - i;

        break;
      }
  }
}

Имея эту процедуру выборки, мы можем реализовать разбиение на куски:

private static IEnumerable<T[][]> MyChunks<T>(T[] array, int take) {
  if (take > array.Length)
    yield break;

  foreach (var sample in Samples(take - 1, array.Length - 1)) {
    T[][] result = new T[take][];

    for (int i = 0, from = 0, to; i <= sample.Length; ++i, from = to) {
      to = i < sample.Length ? sample[i] + 1 : array.Length;

      result[i] = array
        .Skip(from)
        .Take(to - from)
        .ToArray();
    }

    yield return result;
  }
}

Демо:

var arr = new int[] { 1, 2, 3, 4, 5};
int k = 3;

string report = string.Join(Environment.NewLine, MyChunks(arr, k)
  .Select(chunk => "[" + string.Join(", ", chunk
     .Select(item => $"[{string.Join(",", item)}]")) + "]"));

Console.Write(report);

Выход:

[[1], [2], [3,4,5]]
[[1], [2,3], [4,5]]
[[1], [2,3,4], [5]]
[[1,2], [3], [4,5]]
[[1,2], [3,4], [5]]
[[1,2,3], [4], [5]]

Один из способов решения такой проблемы – разделяй и властвуй. Мы могли бы сначала решить, как мы вычисляем возможные разбиения массива, если бы мы когда-либо хотели разбить только на два подмассива (k = 2).

т.е. наша функция, получив 1,2,3,4, должна возвращать 1|2,3,4, 1,2|3,4 и 1,2,3|4, где | отмечает границу между левым и правым подмассивами.

Обратите внимание, как | начинается с крайнего левого положения (которое по-прежнему создает непустое разделение слева) и постепенно перемещается вправо, пока для правого больше не может быть создано непустое разделение.

Функция C#, которая делает это, показана ниже:

IEnumerable<(Memory<int>, Memory<int>)> PossibleSplits(
    Memory<int> xs) {
    for (var i = 1; i < xs.Length; i++)
        yield return (xs[..i], xs[i..]);
}

var splits = PossibleSplits(new[] { 1, 2, 3, 4, 5 }.AsMemory());

Как видите, он возвращает последовательность левых/правых кортежей.

Я использую Memory, поэтому при разделении входных данных новые массивы не выделяются.

Одно приятное свойство этой функции заключается в том, что она возвращает пустую последовательность, когда длина входного массива меньше 2.

Так как же нам разделить на произвольное количество расщеплений, а не только на 2? Один из трюков состоит в том, чтобы снова рекурсивно разделить левую часть разделения, пока левая сторона не станет слишком маленькой для разделения.

С этой целью мы должны изменить вышеуказанную функцию несколькими способами:

• Возвращаемое значение должно измениться с последовательности Memory кортежей на последовательность Memory последовательностей.
• i не всегда может начинаться с позиции 1. При разбиении на произвольное количество k разбиений наша функция должна следить за тем, чтобы левая сторона всегда содержала достаточно элементов для повторного разбиения как минимум на k - 1 подмассивов. Поэтому i должно начинаться с k - 1.
• Очевидно, что функция должна вызывать себя, чтобы стать рекурсивной. И он должен сделать это с одним из двух подмассивов (мы выбираем левый) и предшественником k. Уменьшение k учитывает другой подмассив, который больше не будет разбиваться, но, конечно, будет возвращен как часть результата.
• Мы должны добавить условие выхода, чтобы прервать рекурсивный цикл. Когда k ниже 2, мы не можем осмысленно разделить массив (независимо от его размера) и просто вернуть входной массив, завернутый в виде одноэлементной последовательности.

Ниже приведена рекурсивная версия приведенной выше функции, которая делает именно это:

public static class Ext {
    public static IEnumerable<IEnumerable<Memory<int>>> PossibleSplits(
        this Memory<int> xs,
        int k) {
        if (k < 2) {
            yield return Enumerable.Repeat(xs, 1);
            yield break;
        }
        
        for (var i = k - 1; i < xs.Length; i++) {
            var (left, right) = (xs[..i], xs[i..]);
            foreach (var split in left.PossibleSplits(k - 1))
                yield return split.Append(right);
        }
    }
}

var splits = new[] { 1, 2, 3, 4, 5 }
    .AsMemory()
    .PossibleSplits(k: 3);

Это метод расширения, просто потому, что они мне нравятся.

Вы просили эффективное решение, но эффективность относительна. Это решение эффективно с точки зрения...

• ...память, потому что теперь выделяются новые массивы (тише, мы не говорим обо всех перечислителях, созданных этим кодом);
• ...лень, потому что будут вычисляться только запрошенные значения;
• ...размер кода.

Это не самый эффективный с точки зрения скорости выполнения из-за всех служебных перечислителей.