Генерация подмножеств с использованием кода Грея - EcsFlash/DataTypes GitHub Wiki

В прошлой теме мы выяснили что основным свойством Кода Грея является то, что любые два соседние числа отличаются ровно на 1 бит. При этом последовательность кодов грея при заданной длине каждого кода(n) имеет ровно 2^n элементов - все варианты от 0000(n) до 1111(n). Соотвественно именно битовым представлением кода грея удобно пользоваться для генерации подмножеств: если на iом месте кода грея стоит 1 - элемент исходного множества входит в подмножество, 0 - не входит. Вот функция, которая перегоняет десятичную последовательность кодов грея в список двоичных представлений:

func binCode(nums []int, n int) [][]int {
	var result [][]int
	for j := 0; j < len(nums); j++ {
		temp := make([]int, n)
		i := n - 1
		for nums[j] > 0 {
			temp[i] = nums[j] % 2
			nums[j] = nums[j] / 2
			i--
		}
		result = append(result, temp)
	}
	return result
}

Соответственно, применять её можно так:

func main() {
	str := "Hello World!"
	codes := binCode(grayCode(len(str)), len(str))
	var result []string
	for i := 0; i < len(codes); i++ {
		temp := ""
		for j := 0; j < len(str); j++ {
			if codes[i][j] == 1 {
				temp += string(str[j])
			}
		}
		result = append(result, temp)
	}
	fmt.Println(len(result))
	for _, v := range result {
		fmt.Println(v)
	}
}

И получим 4096 подмножеств символов исходной строки:(тут только начало)

!
d!
d
ld
ld!
l!
l
rl
rl!
rld!
rld
rd
rd!
r!
r
or
or!
ord!
ord
orld
orld!
orl!
orl
ol
ol!
old!
old
od
od!
o!
o
Wo
Wo!
Wod!
Wod
Wold
Wold!
Wol!
Wol
Worl
Worl!
World!
World
Word
Word!
Wor!
Wor
Wr
Wr!
Wrd!
Wrd
Wrld
Wrld!
Wrl!
Wrl
Wl
Wl!
Wld!
Wld
Wd
Wd!
W!
W
 W
 W!
 Wd!
 Wd
 Wld
 Wld!