Smalltalk implemenation of Algorithm 7.2.1.3T TAOCP by Donald Knuth: Lexicographic Combinations

knuth-combinations.st

" Algorithm 7.2.1.3T TAOCP by Donald Knuth: Lexicographic Combinations
  This algorithm is like Algorithm L, but faster. It assumes, for convenience, t < n

  Return a list of digits from 1 to n taken t at a time, in lexicographic order"

"T1. Initialize"
initializeStep := [
	c := Array new: t + 2.
	(1 to: t) do: [:j1 | c at: j1 put: (j1-1)].
	c at: t + 1 put: n.
	c at: t + 2 put: 0.
	j := t.
	visitStep value
].

"T2. Visit"
visitStep := [
	results add: ((t to: 1 by: -1) collect: [:j1 | c at: j1]).
	(j > 0) ifTrue: [
		x := j.
		increaseCjStep value]
	ifFalse: [
		easyCaseStep value ]
].

"T3. Easy case?"
easyCaseStep := [
	((c at: 1) + 1 < (c at: 2))
		ifTrue: [
			c at: 1 put: (c at: 1) + 1.
			visitStep value ]
		ifFalse: [
			j := 2.
			findjStep value ]
].

"T4. Find j"
findjStep := [
	c at: (j - 1) put: j - 2.
	x := (c at: j) + 1.
	(x = (c at: (j + 1))) ifTrue: [
		j := j + 1.
		findjStep value].
	terminateCheckStep value
].

"T5. Terminate the algorithm if j > t"
terminateCheckStep := [
	(j > t) ifTrue: [^results].
	increaseCjStep value
].

"T6. Increase cj"
increaseCjStep := [
	c at: j put: x.
	j := j - 1.
	visitStep value
].

"Test"
n := 6.
t := 3.
results := OrderedCollection new.
initializeStep value.
^results