bit_string_iterator.go

package bitstring

//GistID: c9e651c9b075fc96e966

// An asynchronous permutation Iterator for bitstrings
// So you want all the permuations of 3 bits choose 2 at a time? Well just
// create this async iterator which produces these bitstrings as there integer
// equivlent.
//
// bspIterator(3,2)
// 011 = 3
// 101 = 5
func BSPIterator(n, k int) chan int64 {

	// Create buffer to pass integer of bitstring
	ch := make(chan int64, 0)

	// Recursive defintion
	switch {
	case n < 0 || k < 0:
		// Invalid parameters should close the channel to indicate the the
		// permutations of n < 0 or k < 0 is the empty set. Consumers of the
		// iterator would not make any loops which is considered "safe" normal
		// behavior.
		go func() {
			close(ch)
		}()
	case k == 0:
		// Choosing 0 bits of any length is the bit string 00000...
		go func() {
			ch <- 0
			close(ch)
		}()
	case n == k:
		go func() {
			// Asking for n bits from n bits returns 111111...n which is equal
			// to 10 ... (n) ... 0 bits minus 1
			ch <- (1 << uint(k)) - 1
			close(ch)
		}()
	case k == 1:
		// This is the base case when asking for n choose one bit
		go func() {

			for i := 0; i < n; i++ {
				ch <- 1 << uint(i)
			}

			// Signal the consumer that the end is nigh
			close(ch)
		}()

	case k > 1:
		// The is the recursive step in which a logical or of every bit with
		// every permutation of n choose k-1 bits
		go func() {

			for i := range BSPIterator(n, k-1) {

				// To remove duplicates (i,j) = (j,i) we start j from i
				for j := i; j < int64(n); j++ {

					// We test for equivlent permutations and throw it out
					if 1<<uint(j) != uint(i) {

						// A logical or with a lesser n choose k call will produce
						// all n choose k permutations
						ch <- 1<<uint(j) | i
					}
				}
			}

			// Signal the consumer that the end is nigh
			close(ch)
		}()
	}

	return ch
}

bit_string_iterator_test.go

package bitstring

import "testing"

func TestBitStringPermutations(t *testing.T) {

	cases := []struct {
		n, k int
		want []int64
	}{
		{-3, 1, []int64{}},
		{3, -1, []int64{}},
		{3, 0, []int64{0}},
		{3, 1, []int64{1, 2, 4}},
		{3, 2, []int64{3, 5, 6}},
		{3, 3, []int64{7}},
	}

	for _, c := range cases {

		got := make([]int64, 0)

		for i := range BSPIterator(c.n, c.k) {
			got = append(got, i)
		}

		if len(got) != len(c.want) {
			t.Errorf("Expected %d permutations, got %d %+v %+v", len(c.want), len(got), c.want, got)
		} else {
			for i := range got {
				if got[i] != c.want[i] {
					t.Errorf("Differnt permutatation: want=%+v, got=%+v", c.want, got)
				}
			}
		}
	}
}