文章目录
  1. 1. 递归算法遍历组合
  2. 2. 非递归算法01转换法遍历组合

近来对德州扑克比较感兴趣,于是想到52张牌,究竟会有多少种德州扑克结果组合。得到皇家同花顺的概率有多大呢?
得到皇家同花顺这个问题比较简单。皇家同花顺每个花色各一个,就只有4种情况会出现。我们只需要计算出所有组合C(52, 5)是多少就行了。
组合数的计算公式如下:

1
C(n, m) = n!/(m!*(n-m)!)

接下来我们使用错排法计算组合,首选我们把组合数公式做一下处理,便于大家理解错排发的原理。(注意:直接使用原始公式,阶乘计算到了xx就会越界,即使是64位,也到了xx会越界,错排法可以避免这个问题,但是如果本身组合数结果会越界,错排法也处理不了)

1
2
3
4
C(n, m) = n!/(m!*(n-m)!)
首先,把n!和(n-m)!做一下除法,得到n*(n-1)...*(n-m+1)
于是:
C(n, m) = n*(n-1)...*(n-m+1) / m*(m-1)*(m-2)*...1

从后往前计算,先计算(n-m+1)/1=X1,再计算(n-m+2)X1/2=X2,再计算(n-m+3)X2/3,代码如下:(这样计算能够保证每次的计算结果都是整数,因为每次的计算结果就是一个组合数)

1
2
3
4
5
6
7
8
9
10
11
func C(var n:Int, var m:Int) -> Int
{
var result:Int = 1;
for var i = 1; i <= m; i++
{
result = result * (n - m + i)/i
}
return result
}
C(52, 5) = 2598960

所以得到皇家同花顺的概率只有:
4/2598960 = 0.00000154 = 0.000154%

80多万次才出一次。。所以别太在意这种情况会不会出现在你身上。。概率比较低就是了。

接下来我们来考虑一下如何把所有的德州扑克的5张牌牌面组合给遍历出来。也就是,从52张牌中,任意选择5张的组合。这里要说明一下,并没有进行去重处理,如果要去重,另外要写一个过滤函数来过滤重复的。这里考虑的是,把所有2598960种情况罗列出来。

递归算法遍历组合

首先我们使用递归算法来解决这个问题,递归算法的思路如下:

1
2
3
4
我们把52张牌抽象成一个Int数组A,数组值从1-52,代表52张牌。
1、首先从数组A抽取一张牌(按顺序依次抽取)
2、然后从余下的数组中抽取一张牌(按顺序依次抽取)
3、判断是否抽取达到5张牌,如果没有,则继续在余下的数组中抽取一张牌,如果达到,则输出。

代码端如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
let N = 52
let M = 5
var list: [Int] = [Int]()
for i in 1...N
{
list.append(i)
}
struct Poker {
var list: [Int] = [Int](count: M, repeatedValue: 0);
}
var indexList: [Int] = [Int](count: M, repeatedValue: 0)
var result: [Poker] = [Poker]()
func combine(var list: [Int], var n: Int,
var m: Int, inout indexList: [Int],
var M: Int)
{
for var i = n; i >= m; i--
{
indexList[m-1] = i - 1;
if m > 1
{
combine(list, i - 1, m - 1, &indexList, M);
}
else
{
var poker: Poker = Poker()
for var j = M - 1; j >= 0; j--
{
poker.list[j] = list[indexList[j]]
}
result.append(poker)
print(poker.list)
}
}
}
combine(list, N, M, &indexList, M)
  • 首先我们定义一些变量,list用来存储扑克的索引,一共有1-52张牌,扑克的数据结构没有给出,可以抽象认为是1-52的数字来表示52张扑克。Poker类存储每种德州扑克的的结果的组合。而result就是存储所有结果的列表
  • combine函数就是实现遍历所有组合结果递归函数。形参list表示原始数组,n表示有多少元素参与组合。m表示选择几个元素。indexList是一个辅助数值,存储选择的扑克的在数值中的下标,用于输出结果时候使用,大小是m,而M是一个不变量,用来控制输出时候的固定长度
  • for循环中,从数组最后一个开始取(也可以从头开始取,大家可以试着自行实现)。m > 1时候,继续取前一个。直到m = 0时,已经满足了组合的个数。这个时候就存储结果。注意递归保存的是数组的下标。最后通过下标取出值,设置给最后的poker的list

非递归算法01转换法遍历组合

原理:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
组合可以分解成以下公式
C(n, m) = C(n-1, m) + C(n-1, m-1)
数组长为n,其中前m个值为1,后面为0的序列,执行移动完毕共C(n, m)步
C(n-1, m): 每次交换01位置,从n-1的序列中产生一个新的组合。
这之前相当于把n-1的序列中移动m位,直到第n位为1为止,共产生C(n-1,m)个组合。
C(n-1, m-1): 当第n位为1了,然后前面(n-1)位中包括m-1个1,
把这m-1个数字从最左边移动到和第n位邻接。这个子问题是C(n-1,m-1)
这2步之后的状态就是将m个1移动到长n的序列的右端的状态。
即C(n, m) = C(n-1, m) + C(n-1, m-1).这个就是组合的地推公式
我们来看看具体的例子理解一下:
假设n=5,m=3
直接看结果递推式:
// 1 1 1 0 0 //1,2,3
// 1 1 0 1 0 //1,2,4
// 1 0 1 1 0 //1,3,4
// 0 1 1 1 0 //2,3,4 --C(n-1, m)=C(4, 3)=4
// 1 1 0 0 1 //1,2,5
// 1 0 1 0 1 //1,3,5
// 0 1 1 0 1 //2,3,5
// 1 0 0 1 1 //1,4,5
// 0 1 0 1 1 //2,4,5
// 0 0 1 1 1 //3,4,5--C(n-1, m-1)=C(4, 2)=6
可以看到,在最后一个1移动到数组末尾之前,执行的是C(n-1, m),
之后执行的是C(n-1, m-1),而在1达到数值末尾的时候,
需要把其他1重置到最前面,这里例子里面是2个1。
你还可以继续拆分C(4,2)=C(3,2)+C(3,1),都是满足这样的推导。

算法逻辑如下:

  • 初始化长度为n的数值,将数组前m个元素置1,表示第一个组合为前m个数。
  • 从左到右扫描数组元素值的“10”组合,找到第一个“10”组合后将其变为“01”组合,同时将其左边的所有“1”全部移动到数组的最左端。
  • 当第一个“1”移动到数组的n-m的位置,即m个“1”全部移动到最右端时,就得到了最后一个组合。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
var assistList: [Int] = [Int](count: N, repeatedValue: 0)
for i in 1...M
{
assistList[i-1] = 1
}
assistList
result = [Poker]()
func getValue(var list: [Int], var valueList : [Int]) -> Poker
{
var poker = Poker()
var count = 0
for var i = 0; i < list.count; i++
{
if list[i] == 1
{
poker.list[count] = valueList[i]
count++
}
}
return poker
}
getValue(assistList, list)

首先,我们定义辅助01数组,标识每一步的中间结果。使用函数getValue来根据01数组获取对应的扑克牌。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
func move(inout list: [Int])
{
var firstIndex = 0
var secondIndex = 1
var resetCount = 0
for i in 0...list.count-1
{
if list[firstIndex] == 1 && list[secondIndex] == 0 && secondIndex <= list.count - 1
{
list[firstIndex] = 0
list[secondIndex] = 1
break
}
if list[firstIndex] == 1
{
resetCount++
}
firstIndex++
secondIndex++
}
//重置前面的数据
for i in 0...firstIndex
{
if i < resetCount
{
list[i] = 1
}
else
{
list[i] = 0
}
}
}

定义函数move来移动01函数。每次移动一步。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func checkEnd(var list: [Int]) -> Bool
{
var isEnd = true
for var i = list.count; i < list.count - M + 1; i--
{
if list[i] == 0
{
isEnd = false
break
}
}
return isEnd
}

定义函数checkEnd判断是否已经完成整个过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func combine01(var list: [Int]) -> [Poker]
{
var result = [Poker]()
do
{
var poker = getValue(assistList, list)
result.append(poker)
move(&assistList)
}while(checkEnd(assistList))
return result
}
//result = combine01(list)

主函数也比较简单,do-while循环,判断assistList是否已经不能移动了。而每移动一次,就会记录一次结果。最后输出整个结果。

程序还有一些优化的空间。等以后做实际项目时候,再来优化吧。

参考资料:

文章目录
  1. 1. 递归算法遍历组合
  2. 2. 非递归算法01转换法遍历组合