数独的逻辑:数独算法从入门到精通
上QQ阅读APP看书,第一时间看更新

1.2 排列组合的求法

1.2.1 a×b×c法则(求答数用)

设每件事物各含3个成分,若完成第一成分则有a个方式,完成第二成分则有b个方式,完成第三成分则有c个方式,则全部完成3成分共有a×b×c个方式,这叫作a×b×c法则。故欲求得事物的总排列数或总组合数,或求得事物的总件数,则可按有几成分便设立几个小格,每小格算出其方式数,然后取各方式数连乘起来,其乘积便是总方式数或总件数。但是应当注意并不是所有组合都是直接由a×b×c法则求得的,有些组合应先求得排列总数,再求得每个组合的排列数,最后用排列总数除以每组合的排列数,方得出组合数,这便是公式的运用。

例1, 2顶帽子3件衣服4条裤子可以搭配成几套?

用交叉线图表示如图1-2所示。

图1-2 交叉线图

具体计算结果为:

2×3×4=24套(组合)

上式诸因子2、3、4的顺序可任意颠倒,故乘积为组合数。

例2,从1、2、3三数字任取两个数字,可得几个两位数(见图1-3)?

图1-3 两位数

因十位数可用1、2、3三个数字之任一,故有3方式,个位数只可用余下两个数字之任一,故只有2方式。

按a×b×c法则共有两位数的个数为:

3×2=6方式(排列)

上式中两因子先有3后有2,不可任意颠倒,故乘积属于排列数。6个排列是(排队列表法):

12、13、21、23、31、32。

1.2.2 公式法(求答数用)

1.2.2.1 排列公式

是4物取2之排列,每个排列含2成分(见图1-4)。

图1-4 4物取2的排列

第一物可取4物之任一,故有4方式,轮到第二物仅余3物之任一可取的有3方式。按a×b×c法则,从4起连取2数相乘,总排列数=4×3=12个(排列)。

1.2.2.2 组合公式

为4物取2之组合,每组合含2成分(见图1-5)。

图1-5 总排列数

先求总排列数(见图1-5),总排列数=4×3=12方式(排列)。

再求每组合(2成分)之排列数(见图1-6),每组合之排列数=2×1=2方式(排列)。

图1-6 每组合之排列数

1.2.3 排队列表法(求项目用)

可以用下面的口诀表示排队列表法:

最小先行(a),依次递增(b),

后满前涨(c),涨后复升(d),

如此反复(e),极大而终(f)。

我们举例并运用图解来说明排队列表法的步骤。

例1,从1、2、3、4四个数字中任取两个数字作为两位数,共有哪些两位数?(见图1-7)

图1-7 排队列表法图解

以上图解为排队列表法的用法,其中包含两个要点:(1)记住口诀,(2)弄懂步骤。一旦掌握这两点后,读者不难直接写出排队列表法的下列成果来(并不一定要求读者仿上图写出具体步骤):

12、13、14、21、23、24、31、32、34、41、42、43。

必须指出:排队列表法和a×b×c法则一样,既可用来求排列也可用来求组合。当用于求排列时,成果表中的各项采用有升有降的顺序。

比如本例的12个排列的顺序便是有升有降:

这12项排列按总值均系由左到右、由小到大,按位值便是有升(↗)有降(↘)。

反之,当用于求组合时则成果表各项采用光升不降的顺序。比如本例的组合数是6个,具体如下:

这6项组合按总值仍是后大于前,但按位值则是光升不降(6项组合表是从12项排列表中摘取其中光升不降的顺序而得出的)。

排队列表法是任何书中都找不到的,是作者的首创,是一种直观易懂的通俗方法。作者根据排列公式(n物取r物的排列),从n起连取r个数相乘,则一个井块(九方格)若任意填入1、2、3、4、5、6、7、8、9九个数字,可得九字取九的排列数:=9×8×7×…×2×1=362880个排列。这36万多个排列便可用排队列表法一个不漏地写出来(详见1.2.3条),可见排队列表法的神奇威力!

1.2.4 交叉线图(求答数和项目用)

每件事物由哪几个成分组成便立几个栏目,标明每个栏目有哪些方式,然后各栏目之方式借用直线连接起来,便得出交叉线图。由交叉线图即可获得事物的总件数(排列总数或组合总数),也可获得排列组合成果表。

例1,设定以下一个大列首块。今欲由左至右从每列里各取一字组成一个三字正交线(正交线对大列而言是指由左至右沿横向扫描,从各列任取一字所得的三字线)。问可得多少根正交线?(见图1-8)

图1-8 大列首块

今三字正交线是一个三位数,其成分有百位、十位、个位。百位可用3、6、9三方式,十位可用2、5、8三方式,个位可用1、4、7,亦有三方式,于是可作出以下交叉线图(见图1-9)。

图1-9 三位数之交叉线图

3×3×3 = 27个(排列)

上式因子第一列指百位,第二列指十位,第三列指个位,不可颠倒,故27为排列数。那么欲得出排列成果表有何步骤呢?

用图解表示步骤如下(见图1-10,表示头三步)。

图1-10 三位数构成步骤

由此得以下成果序列(见图1-11)。

图1-11 序列

故27个排列成果如下:

321324 327351 354357 381384 387

621624 627651 654657 681684 687

921924 927951 954957 981984 987

由排队列表法所得出的排列成果表,各项务必通通是由小到大排列,这才能保证由交叉线图的摘取方法是正确的。

注意在引用排列组合方法时是单用一种方法的情况非常少。比如,用排队列表法时往往先用a×b×c法则求得答数,然后再用排队列表法求出答案来。采用交叉线图时,同时要用a×b×c法则和排队列表法。各种排列组合答数没有哪一个不是以a×b×c法则为基础的,求排列如此,求组合亦如此。但求排列时直接用a×b×c法则即可,而求组合时有的可直接运用a×b×c法则,有的得先用a×b×c法则求得总排列数和每组合的排列数,然后再取两排列数之商方得出组合数。

求排列组合时不是都可写出算式的,比如排队列表法就没有算式。又比如选连交叉线图(非全连交叉线图)求答数时也没有算式。

对于一个排列组合的问题,先要确定它是要求组合还是要求排列,然后酌情选用具体的方法。