combinations.go

func combinations(n, m int, f func([]int)) {
	// For each combination of m elements out of n
	// call the function f passing a list of m integers in 0-n
	// without repetitions
	
	// TODO: switch to iterative algo
	s := make([]int, m)
	last := m - 1
	var rc func(int, int)
	rc = func(i, next int) {
		for j := next; j < n; j++ {
			s[i] = j
			if i == last {
				f(s)
			} else {
				rc(i+1, j+1)
			}
		}
		return
	}
	rc(0, 0)
}

combinations_with_replacement.go

func combinations_with_replacement(n, m int, f func([]int)) {
	// For each combination of m elements out of n
	// call the function f passing a list of m integers in 0-n
	// with repetitions
	indices := make([]int, m)
	f(indices)

	for {
		var i int
		for i = m - 1; i >= 0; i-- {
			if indices[i] != n-1 {
				break
			}
		}
		if i < 0 {
			break
		}

		indices_i := indices[i]
		for k := i; k < m; k++ {
			indices[k] = indices_i + 1
		}
		f(indices)
	}
}