Permutations in Go

permutations.go

// By: Robert Wallis - [email protected]
// Returns a channel of all the possible permutations of a string containing
// r length in characters.
// adopted from http://docs.python.org/library/itertools.html
func StringPermutationsSub(s string, r int) chan string {
	out := make(chan string)
	go func() {
		defer close(out)
		pool := []int(s) // get unicode
		n := len(pool)
		if r > n {
			return
		}
		indices := make([]int, n)
		for i := 0; i < n; i++ {
			indices[i] = i
		}
		cycles := []int{}
		for i := n; i > n-r; i-- {
			cycles = append(cycles, i)
		}
		endOfCycles := make([]int, len(cycles))
		copy(endOfCycles, cycles)
		// send the first iteration
		sout := make([]int, r)
		for i, v := range indices[:r] {
			sout[i] = pool[v]
		}
		out <- string(sout)
		for n > 0 {
			reversedRangeR := []int{}
			for i := r - 1; i >= 0; i-- {
				reversedRangeR = append(reversedRangeR, i)
			}
			for _, i := range reversedRangeR {
				cycles[i] = cycles[i] - 1
				if cycles[i] == 0 {
					// time for a new cycle
					newindices := make([]int, i)
					for k := 0; k < i; k++ {
						newindices[k] = indices[k]
					}
					for k := i + 1; k < len(indices); k++ {
						newindices = append(newindices, indices[k])
					}
					newindices = append(newindices, indices[i])
					indices = newindices
					cycles[i] = n - i
				} else {
					j := cycles[i]
					indices[i], indices[len(indices)-j] = indices[len(indices)-j], indices[i]
					// send iteration
					sout := make([]int, r)
					for k, v := range indices[:r] {
						sout[k] = pool[v]
					}
					out <- string(sout)
					break
				}
			}
			// have we come all the way around to the first permutation?
			same := true
			for i, v := range cycles {
				if endOfCycles[i] != v {
					same = false
					break
				}
			}
			if same {
				// yes this is the same as the first
				return
			}
		}
		// end
		return
	}()
	return out
}