Partition list overlapping into N sub-lists as evenly as possible

Question

There are similar questions here I haven't seen one where the there is an overlap.

The requirements:

• The result should be N sub lists with the overlap specified.
• There should be no dropped elements
• The sub-lists should have lengths that are as even as possible, i.e. there should be a minimum number of different sub-list lengths and the difference between sub-list lengths should be minimized.

For example, given Range[10] and overlap of 1 this would be the output for different numbers of sub-lists:

N   Output
1   {{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}}
2   {{1, 2, 3, 4, 5, 6}, {6, 7, 8, 9, 10}}
3   {{1, 2, 3, 4}, {4, 5, 6, 7}, {7, 8, 9, 10}}
4   {{1, 2, 3, 4}, {4, 5, 6}, {6, 7, 8}, {8, 9, 10}}
5   {{1, 2, 3}, {3, 4, 5}, {5, 6, 7}, {7, 8, 9}, {9, 10}}
6   {{1, 2, 3}, {3, 4, 5}, {5, 6, 7}, {7, 8}, {8, 9}, {9, 10}}
7   {{1, 2, 3}, {3, 4, 5}, {5, 6}, {6, 7}, {7, 8}, {8, 9}, {9, 10}}
8   {{1, 2, 3}, {3, 4}, {4, 5}, {5, 6}, {6, 7}, {7, 8}, {8, 9}, {9, 10}}
9   {{1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 6}, {6, 7}, {7, 8}, {8, 9}, {9, 10}}

Note: Above is an example done by hand and it is not a requirement that the splitting be done as in the example above. So for example for N = 4 either of the following would be valid:

{{1, 2, 3, 4}, {4, 5, 6}, {6, 7, 8}, {8, 9, 10}}
{{1, 2, 3}, {3, 4, 5}, {5, 6, 7}, {7, 8, 9, 10}}

Answer 1

The following takes subsequences of the average length required, with end points rounded to the nearest integer, so that the lengths of subsequences will differ by at most 1.

partitionRagged[list_, n_, k_: 0] := (* n sublists, overlapping k elements *)
  With[{dl = (Length[list] - k)/n},
   Table[
    Take[list,
     {Round[1 + (j - 1)*dl], 
      Min[Round[k + (j)*dl], Length[list]]}],
    {j, n}
    ] /; dl > 0]; (* fails if k > Length[list] *)

Examples:

partitionRagged[Range@10, 5, 2]
Length /@ % (* consistency check *)
(*
{{1, 2, 3, 4}, {3, 4, 5}, {4, 5, 6, 7}, {6, 7, 8}, {7, 8, 9, 10}}

{4, 3, 4, 3, 4}
*)

partitionRagged[Range@17, 6, 3]
Length /@ % (* consistency check *)
(*  
{{1, 2, 3, 4, 5}, {3, 4, 5, 6, 7, 8}, {6, 7, 8, 9, 10},
 {8, 9, 10, 11, 12}, {10, 11, 12, 13, 14, 15}, {13, 14, 15, 16, 17}}

{5, 6, 5, 5, 6, 5}
*)

(* second consistency check: compute the overlaps *)
FoldPairList[
 {Intersection[##], #2} &,
 partitionRagged[Range@17, 6, 3]
 ]
(*  {{3, 4, 5}, {6, 7, 8}, {8, 9, 10}, {10, 11, 12}, {13, 14, 15}}  *)

Answer 2

list = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

n = 5

overlap = 2

list[[#]]& /@ Span@@@(Join[{{0,0}}, ConstantArray[{-overlap + 1, 0}, n - 1]] + Partition[Ceiling[Subdivide[Length[list] - 1, n]] + 1, 2, 1])