组合数学

第4章 生成排列和组合

4.6 练习题

6、确定 1,2, ,8 的下列排列的逆序列。 ⅰ) 35168274 ⅱ) 83476215

解：ⅰ）它的逆序列是2，4，0，4，0，0，1，0

□

ⅱ）它的逆序列是6，5，1，1，3，2，1，0

7、构造 1,2, ,8 的排列，其逆序列是 ⅰ) 2，5，5，0，2，1，1，0 ⅱ) 6，6，1，4，2，1，0，0

解：ⅰ）8 8 7 87 6 867 5 8657 4 48657 3 486573 2 4865723 1 48165723

因此，该逆序的排列是48165723

ⅱ）1： 1

2： 1 2 3： 3 1 2 4： 3 4 1 2 5： 3 5 4 1 2 6： 3 6 5 4 1 2 7： 7 3 6 5 4 1 2 8： 7 3 6 5 8 4 1 2 1 2 3 4 5 6 7 8 因此，该逆序的排列是73658412

15、对于 x7,x6, ,x1,x0 的下列每一个组合，通过使用基为2的生成算法确定其直接后继组合： ⅰ) x4,x1,x0 ⅱ) x7,x5,x3 ⅲ) x7,x5,x4,x3,x2,x1,x0 ⅳ) x0

—第1页—

□□□

组合数学

解：ⅰ) x4,x1,x0 对应的二进制数是00010011。使用基为2的运算

00010011+1=00010100

所以 x4,x1,x0 的直接后继组合是 x4,x2

□

ⅱ) x7,x5,x3 对应的二进制数是10101000。使用基为2的运算

10101000+1=10101001

所以 x7,x5,x3 的直接后继组合是 x7,x5,x3,x0

□

ⅲ) x7,x5,x4,x3,x2,x1,x0 对应的二进制数是10111111。使用基为2的运算

10111111+1=11000000

所以 x7,x5,x4,x3,x2,x1,x0 的直接后继组合是 x7,x6

□

ⅳ) x0 对应的二进制数是00000001。使用基为2的运算

00000001+1=00000010

所以 x0 的直接后继组合是 x1

□

23、确定下列9阶反射Gray码中9-元组的直接后继。 ⅰ) 010100110 ⅱ) 110001100 ⅲ) 111111111

解：ⅰ)∵ (010100110)=4

∴010100110的直接后继是010100111

□

ⅱ)∵ (110001100)=4

∴110001100的直接后继是110001101

□

ⅲ)∵ (111111111)=9

∴111111111的直接后继是111111101

□

27、使用在4.4节中描述的算法，以字典序生成{1，2，3，4，5，6}的3-组合。

解：它们是：

{1,2,3}、{1,2,4}、{1,3,4}、{1,2,5}、{1,3,5}、{1,4,5}、{1,2,6}、{1,3,6}、{1,4,6}、{1,5,6}、{2,3,4}、{2,3,5}、{2,4,5}、{2,3,6}、{2,4,6}、{2,5,6}、 {3,4,5}、{3,4,6}、{3,5,6}、 {4,5,6}

□

—第2页—