package main

import (
	"fmt"
)

func main() {
    Combination(6, 3)
}

/*
列举出所有C(m,a)的情况, 从m个不同小球中取a个的所有情况
*/
func Combination(m, a int) {
	if m <= 0 || a < 0 || a > m {
		fmt.Printf("参数错误. m必须大于0，n必须大于等于0，并且m>=a")
		return
	}

	arr := make([]bool, m)
	// 将a个true放在最左边
	for i := 0; i < a; i += 1 {
		arr[i] = true
	}
	printArr(arr)

	count := 1

	if a != 0 {
		for {
			trueIndex, trueLen := findList(arr)

			// 如果所有的true都在最右边，则退出
			if trueIndex+a == m && trueLen == a {
				break
			}
			// 将最右边的true往右移一位
			arr[trueIndex+trueLen-1] = false
			arr[trueIndex+trueLen] = true

			//剩下的true全部放最左边
			for i := 0; i < trueLen-1; i += 1 {
				arr[i+trueIndex] = false
				arr[i] = true
			}
			printArr(arr)

			count += 1
		}
	}

	fmt.Printf("C(%v,%v)=%v\n", m, a, count)
}

/*
从arr中找到最左边连续的true
@return (连续true左端的index，连续true的长度)。 如果没有true,则返回 (-1, 0)
eg:
11010 返回 (0,2)
01010 返回 (1,1)
01110 返回 (1,3)
00011 返回 (3,2)
*/
func findList(arr []bool) (int, int) {

	trueIndex := -1

	for i, item := range arr {
		if item {
			// 找到第一个true
			trueIndex = i
			break
		}
	}
	if trueIndex == -1 {
		return -1, 0
	}

	falseIndex := -1
	for i := trueIndex + 1; i < len(arr); i += 1 {
		if !arr[i] {
			// 找true后面的false
			falseIndex = i
			break
		}
	}
	// 右边没有false了
	if falseIndex == -1 {
		return trueIndex, len(arr) - trueIndex
	}
	return trueIndex, falseIndex - trueIndex
}

/*
将bool数组用 0 1的方式打印出来，而不是默认的 true false，以方便查看
*/
func printArr(arr []bool) {
	for _, item := range arr {
		if item {
			fmt.Printf("1 ")
		} else {
			fmt.Printf("0 ")
		}
	}
	fmt.Printf("\n")
}