Get all split options to k chunks

Question

I need to split an array arr into k chunks where the union of all the chucks is arr and there in no same element in two chunks.

For example for

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

I need to return all the possible splits:

[[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]]

How can I do that efficiently in C#?

Answer 1

You have a combinatoric problem: given an array of n item you should sample k subarrays or, put it differently, k - 1 splits from 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   

Note that we have standard combinatoric problem

k - 1 from n - 1 unordered without repetitions

Code for such sampling can be

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;
      }
  }
}

Having this sampling routine, we can implement splitting into chunks:

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;
  }
}

Demo:

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);

Output:

[[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]]