On-demand algorithm returns a contiguous combination of k elements from n

original wording

(skip to update below )

1. Suppose nthe elements are integers 1..n.
2. kRepresents each -combination in increasing order (this representation gets rid of the permutation inside the -combination k).
3. Now consider the lexicographic order between k combinations (of nelements) . In other words, {i_1..i_k} < {j_1..j_k}if there is an index tsuch that
   • i_s = j_sall s < tand
   • i_t < j_t。
4. If -combination, define it {i_1..i_k}as the next element in lexicographical order.knext{i_1..i_k}

Here's how it is calculated next{i_1..i_k}:

• Find the largest exponent rsuch thati_r + 1 < i_{r+1}
• If no index satisfies this condition i_k < n, setr := k
• If none of the above conditions are met, there is no next (and k-combination equals {n-k+1, n-k+2,... ,n})
• If rthe first condition is met, set nextto{i_1, ..., i_{r-1}, i_r + 1, i_{r+1}, ..., i_k}
• if r = k(second condition), setnext := {i_1, ..., i_{k-1}, i_k + 1}.

Update (many thanks to @rici for improving the solution)

1. Suppose nthe elements are integers 1..n.
2. kRepresents each -combination in increasing order (this representation gets rid of the permutation inside the -combination k).
3. Now consider the lexicographic order between k combinations (of nelements) . In other words, {i_1..i_k} < {j_1..j_k}if there is an index tsuch that
   • i_s = j_sall s < tand
   • i_t < j_t。
4. If -combination, define it {i_1..i_k}as the next element in lexicographical order.knext{i_1..i_k}
5. Note that in this order, the smallest kcombination is {1..k}the largest {n-k+1, n-k+2,... ,n}.

Here's how to calculatenext{i_1..i_k}

• Find the largest index rso that it i_rcan be increased 1.
• Increments the value at index rand resets the following elements from consecutive values ​​starting at i_r + 2.
• Repeat until there are no more places to add.

more specifically:

• If i_k < n, increment i_kby 1(ie, replace i_kwith i_k + 1)
• If i_k = n, find the largest exponent rsuch that i_r + 1 < i_{r+1}. Then increase i_rthe pass 1and reset the following positions{i_r + 2, i_r + 3, ..., i_r + k + 1 - r}
• repeat until reach{n-k+1, n-k+2,... ,n}

Note the recursive nature of this algorithm : every time the least significant position is incremented, the tail is reset to the lexicographically smallest sequence that starts with the value just incremented.

Smalltalk code

SequenceableCollection >> #nextChoiceFrom: n
    | next k r ar |
    k := self size.
    (self at: 1) = (n - k + 1) ifTrue: [^nil].
    next := self shallowCopy.
    r := (self at: k) = n
      ifTrue: [(1 to: k-1) findLast: [:i | (self at: i) + 1 < (self at: i+1)]]
      ifFalse: [k].
    ar := self at: r.
    r to: k do: [:i | 
      ar := ar + 1.
      next at: i put: ar].
    ^next