小鸟测姓的一个实现方案

周末在广场上，看到有人摆摊用小鸟测姓，每次收费10元。

流程如下：

1. 路人从A区选出一张含有自己姓的卡片，覆盖到B区含有自己姓的卡片上
2. 摆摊的拿起选中的卡片，让小鸟C在灯下看一遍
3. 小鸟C从盒子D里叼出一张纸片，摆摊的便道出了路人的姓

围观了几个人付钱后，看起来不像都是托。

本着实用主义的理念，我觉得小鸟在这场以它自己为主角的演出中没有什么作用，排除掉鸟发挥的作用。

一个可能的方案浮现在脑海中：路人从A和B中，各选出了一张卡片，这些卡片上的姓，做交集，若结果不唯一，那么排除掉罕见的姓，剩下的便是路人的姓。

于是，我编程实现了这个方案，以小姓“王”为例，运行结果如下：

A、B两区域与测姓现场相对应，每一行为一张卡片。从A、B区域中各选出一行，做交集，可以得出两个姓，一为常用姓，一为罕见姓，选择常用姓作为结果输出。

附上代码如下(Golang实现，共三个文件)：

1. 实现逻辑 main.go

// main.go
package main

import (
	"fmt"
	"math/rand"
	"time"
)

var (
	commonList = []rune("王李张刘陈杨黄赵吴周徐孙马朱胡郭何高林郑谢罗梁宋唐许韩冯邓曹彭曾肖田董袁潘于蒋蔡余杜叶程苏魏吕丁任沈姚卢姜崔钟谭陆汪范金石廖贾夏韦付方白邹孟熊秦邱江尹薛闫段雷侯龙史陶黎贺顾毛郝龚邵万钱严覃武戴莫孔向汤草发放受改卿取印即变文盛笔又盖第新目荣南古华十题颜可升都艺抒如部要术特未臆朴和阳至屈最阅有合属后难名朝展期版自同各宪撇家胸狂能官需被稿体作得但律态怀缘佼使约开式思连进还这应流楷运羲庄过迄迅楚意追浮迹感")
	rareList = []rune("块前骨战出起成处或夺毕准大止义们之正畅此泛令以法代仿指元也先略仍今介具其习关仅书挥汉他全八公商尖雕行权小将雅品就然表来尤而者导肥韵音端章竖状皆的密肃寄呵瘦富词识诞话四率现语询因国读粗说常长柳点规素见间染始写横由甲模画节再用贯醒祖奔生欲没种上欧演与不欢七一主为丰据情称捷中捺壮真历族字等省整原日无早故化北时学到源篆确造刷制承功力别划顺动那列创则初分切所速才通溯手认已己记论工年并广唯易键喜明果显黑是系构")
)


func convSlice(fromSlice []rune) (toSlice []interface{}) {
	toSlice = make([]interface{}, len(fromSlice))
	for index, value := range fromSlice {
		toSlice[index] = string(value)
	}
	return
}

// 打乱元素次序
func shuffleSlice(rawSlice []interface{}) (s []interface{}) {
	s = make([]interface{}, len(rawSlice))
	rand.Seed(int64(time.Now().Nanosecond()))
	for rawIndex, index := range rand.Perm(len(rawSlice)) {
		s[index] = rawSlice[rawIndex]
	}
	return
}


func main() {

	commonSlice := shuffleSlice(convSlice(commonList))
	rareSlice := shuffleSlice(convSlice(rareList))

	 //用于确定是否为常用姓
	commonSet := NewSetFromList(commonSlice)

	// 新建 PokerGroup 20 个 poker
	pg1 := NewPokerGroup()
	pg1ValueList := make([][]interface{}, 20)

	for pokerIndex:=0; pokerIndex<20; pokerIndex++ { // FIXME 这里写的有问题

		valueList := make([]interface{}, 20)
		for index, value := range commonSlice[pokerIndex*10:pokerIndex*10+10] {
			valueList[index] = value
		}

		for index, value := range rareSlice[pokerIndex*10:pokerIndex*10+10] {
			valueList[index+10] = value
		}

		pg1ValueList[pokerIndex] = valueList
		pg1.AddPoker(valueList)
	}

	// 新建一个 PokerGroup 10 个 poker
	pg2 := NewPokerGroup()

	// 从每个里边取出2个，包含一个常用的姓，一个不常用的姓
	for pokerIndex:=0; pokerIndex<10; pokerIndex++ {
		eleList := []interface{}{}
		for i:=0; i<20; i++ {
			eleList = append(eleList, pg1ValueList[i][pokerIndex])
			eleList = append(eleList, pg1ValueList[i][pokerIndex+10])
		}
		pg2.AddPoker(eleList)
	}

	// 从这里选出来一个
	fmt.Println(pg1.ToString())
	fmt.Println("选择你的姓所在的行号：")
	input1 := 1
	fmt.Scanln(&input1)

	// 从这里再选出来一个
	fmt.Println(pg2.ToString())
	fmt.Println("选择你的姓所在的行号：")
	input2 := 2
	fmt.Scanln(&input2)

	// 做一个交集
	inSet := IntersectSet(
		pg1.pokerSetList[input1-1],
		pg2.pokerSetList[input2-1],
	)

	for value := range inSet.IteratorChan() {
		if commonSet.Contains(value) {
			fmt.Println("\n\n你的姓是: ", value)
			break
		}
	}
}

2. 抽象出来的卡片组 poker.go

// poker.go
package main

import (
	"fmt"
)

/*
   PokerGroup 代表一组牌，每张牌上若干个姓。每张牌宽高固定
 */
type PokerGroup struct {
	size int               // 有几个set
	pokerSetList []*Set    // 每张牌上的姓，组成一个集合
}

func NewPokerGroup() *PokerGroup {
	return &PokerGroup{
		size: 0,
		pokerSetList: []*Set{},
	}
}

// 新加一张牌
func (pg *PokerGroup) AddPoker(lst []interface{}) {
	pg.size++
	pg.pokerSetList = append(pg.pokerSetList, NewSetFromList(lst))
}

func (pg *PokerGroup) Size() int {
	return pg.size
}

// 每行打印4张牌
func (pg *PokerGroup) ToString() (s string) {
	s = fmt.Sprintf("PokerGroup Size: %d\n", pg.Size())
	for pokerIndex:=0; pokerIndex<pg.Size(); pokerIndex++ {
		s += fmt.Sprintf("%2d : %s\n", pokerIndex+1, pg.pokerSetList[pokerIndex].ToLineString())
	}
	s += "\n"
	return
}

3. 用到的集合类型，用hash table实现 set.go

// set.go
package main

import (
	"strconv"
	"hash/fnv"
	"fmt"
)


/*
    基于hash table 的集合 set
 */

type Key struct {
	value interface{}
}

func NewKey(value interface{}) *Key {
	return &Key{value}
}

func (k *Key) Value() interface{} {
	return k.value
}

func (k *Key) IsEqual(anotherKey *Key) bool {
	return k.Value() == anotherKey.Value()
}

type Set struct {
	keyList []*Key
	size int                // 实际存储的键值対的数量
	m int                   // 数组总大小
	minM int                // 设置的最小的数组的大小
}

func NewSet(initM int) *Set {
	minM := 10
	if initM < minM {
		initM = minM
	}
	return &Set{
		make([]*Key, initM),
		0,
		initM,
		minM,
	}
}

func NewSetFromList(lst []interface{}) (s *Set) {
	s = NewSet(10)
	for _, value := range lst {
		s.Add(value)
	}
	return
}

// resize array
func (b *Set) resize(cap int) {
	that := NewSet(cap)
	for i := 0; i < b.m; i++ {
		thisKey := b.keyList[i]
		if thisKey != nil {
			that.Add(thisKey.Value())
		}
	}
	*b = *that
}

// hash value of key
func (b *Set) hashIndex(item interface{}) (index int) {

	repString := ""
	switch item.(type) {
	case string:
		repString, _ = item.(string)
	case int:
		tempString, _ := item.(int)
		repString = strconv.Itoa(tempString)
	default:
		panic("type not support")
	}

	h := fnv.New32()
	h.Write([]byte(repString))
	index = int(h.Sum32() % uint32(b.m))
	return
}

func (b *Set) nextIndex(nowIndex int) int {
	if nowIndex >= b.m - 1 {
		return 0
	} else {
		return nowIndex + 1
	}
}

func (b *Set) Add(item interface{}) (ifAdd bool) {
	// 插入之前，判断 size
	if b.size > b.m / 2 {
		b.resize(2 * b.m)
	}

	hashIndex := b.hashIndex(item)
	key := NewKey(item)

	for {
		thisKey := b.keyList[hashIndex]

		if thisKey == nil { // 没值，设置新值
			b.keyList[hashIndex] = key
			b.size++
			ifAdd = true
			break
		} else {

			if key.IsEqual(thisKey) { // 命中, 什么也不干
				ifAdd = false
				break
			} else {                          // hashIndex + 1
				hashIndex = b.nextIndex(hashIndex)
			}
		}
	}
	return
}

// 是否包含某个元素
func (b *Set) Contains(item interface{}) (contains bool) {

	key := NewKey(item)

	hashIndex := b.hashIndex(item)

	for {
		thisKey := b.keyList[hashIndex]

		if thisKey == nil { // 没值，说明没找到
			contains = false
			break
		} else {

			if key.IsEqual(thisKey) { // 命中
				contains = true
				break
			} else {                   // hashIndex + 1
				hashIndex = b.nextIndex(hashIndex)
			}
		}
	}
	return
}

func (b *Set) IsEmpty() bool {
	return 0 == b.Size()
}

func (b *Set) Size() int {
	return b.size
}

func (b *Set) IteratorChan() chan interface{} {
	nowSize := 0
	i := 0
	c := make(chan interface{})
	go func () {
		for {
			if !(i<b.m && nowSize<b.size) {
				break
			}

			thisKey := b.keyList[i]

			if thisKey == nil {
				i++
				continue
			}
			nowSize++
			i++
			c <- thisKey.Value()
		}
		close(c)
	}()
	return c
}

func (s *Set) ToString() (str string) {
	str = fmt.Sprintf("Set: %d\n%s\n", s.Size(), s.ToLineString())
	return
}

func (s *Set) ToLineString() (str string) {
	str = ""
	for value := range s.IteratorChan() {
		tmpStr := ""
		switch value.(type) {
		case string:
			tmpStr, _ = value.(string)
		case int:
			tmpInt, _ := value.(int)
			tmpStr = strconv.Itoa(tmpInt)
		default:
			panic("type not support!")
		}
		str += fmt.Sprintf("%s ", tmpStr)
	}
	return
}

func (s *Set) ToList() (lst []interface{}) {
	lst = make([]interface{}, s.Size())
	index := 0
	for value := range s.IteratorChan() {
		lst[index] = value
		index++
	}
	return
}

/*
    下面是几个集合的操作
    UnionSet() ∪
    IntersectSet() ∩
 */
func UnionSet(setList ...*Set) (s *Set) {
	s = NewSet(10)
	for _, set := range setList {
		c := set.IteratorChan()
		for value := range c {
			s.Add(value)
		}
	}
	return
}

func IntersectSet(setList ...*Set) (s *Set) {
	s = NewSet(10)
	minSetIndex := 0
	minSetSize := setList[0].Size()
	if len(setList) > 1 {
		for setIndex, set := range setList[1:] {
			thisSetSize := set.Size()
			if minSetSize > thisSetSize {
				minSetSize = thisSetSize
				minSetIndex = setIndex
			}
		}
	}

	for value := range setList[minSetIndex].IteratorChan() {
		flag := true
		for _, set := range setList {
			if !set.Contains(value) {
				flag = false
				break
			}
		}
		if flag {
			s.Add(value)
		}
	}

	return
}

// s1 - s2
func SubtractSet(s1 *Set, s2 *Set) (s *Set) {
	s = NewSet(10)
	for value := range s1.IteratorChan() {
		if !s2.Contains(value) {
			s.Add(value)
		}
	}
	return
}

纰漏难免，欢迎交流。