« フォーマル・メソッドと日本語プログラミング | トップページ | 順序関係を列挙する »

2008年3月15日 (土)

4変数の順序関係はいくつあるか?

4つの順序を持つ変数に関して、以下の条件 X があるとします。

 x1 < x2 < x3 < x4

X が 真とならない 4変数の関係はいくつ考えられるでしょうか?

X を二項ずつに書き直します。

 (x1 < x2)
  ∧ (x2 < x3)
  ∧ (x3 < x4)

X の否定 not X をとります。

 (x1 ≧ x2)
  ∨ (x2 ≧ x3)
  ∨ (x3 ≧ x4)

不等号と等号を別にします。

 (x1 > x2)
  ∨ (x2 > x3)
  ∨ (x3 > x4)
  ∨ (x1 = x2)
  ∨ (x2 = x3)
  ∨ (x3 = x4)

4変数のいずれかが存在しない場合も考慮することにします。 ここでは、 "is null" と表記しておきます。

 (x1 > x2)
  ∨ (x2 > x3)
  ∨ (x3 > x4)
  ∨ (x1 = x2)
  ∨ (x2 = x3)
  ∨ (x3 = x4)
  ∨ (x1 is null)
  ∨ (x2 is null)
  ∨ (x3 is null)
  ∨ (x4 is null)

突き詰めますと、この10個の条件のいずれかになるわけですが。全部の数が知りたいので、不等号の場合、等号の場合、変数が存在しない場合、各々について、順に考えてみます。

不等号の場合

不等号をそのままにして、4変数の場所を並べ替えることを考えますと。

 P4 = 4! = 24

4つをとる順列を考えればよく、全部で24個の並びが存在することになります。うちひとつは、 X そのものですので、 X が真とならないものは 23個ですね。

0 x1 < x2 < x3 < x4
1 x1 < x2 < x4 < x3
2 x1 < x3 < x2 < x4
3 x1 < x3 < x4 < x2
4 x1 < x4 < x2 < x3
5 x1 < x4 < x3 < x2
6 x2 < x1 < x3 < x4
7 x2 < x1 < x4 < x3
8 x2 < x3 < x1 < x4
9 x2 < x3 < x4 < x1
10 x2 < x4 < x1 < x3
11 x2 < x4 < x3 < x1
12 x3 < x1 < x2 < x4
13 x3 < x1 < x4 < x2
14 x3 < x2 < x1 < x4
15 x3 < x2 < x4 < x1
16 x3 < x4 < x1 < x2
17 x3 < x4 < x2 < x1
18 x4 < x1 < x2 < x3
19 x4 < x1 < x3 < x2
20 x4 < x2 < x1 < x3
21 x4 < x2 < x3 < x1
22 x4 < x3 < x1 < x2
23 x4 < x3 < x2 < x1

等号の場合

4変数のうち2変数が等しい場合は、

 4C2 = 4 ・ 3 / 2 ・ 1 = 6

4つから2つをとる組合わせの数で6個あります。

4変数のうち3変数が等しい場合は、

 4C3 = 4C1 = 4

4個あります。

4変数のうち4変数が等しい場合は、1個あります。

さらに、等号を不等号を組み合わせるわけですが。これは、等しい変数を1変数にまとめ、その並べ替えを考えれば良いかと思います。

例えば、4変数のうち2変数が等しいとしまして、これが、

 x1 = x2

であるとしますと、これを X12 とまとめまして、3変数の並べ替えを考えます。

 P3 = 3! = 6

6個あります。

1 X12 < x3 < x4
2 X12 < x4 < x3
3 x3 < X12 < x4
4 x3 < x4 < X12
5 x4 < X12 < x3
6 x4 < x3 < X12

まとめますと、

 4C2 ・ P3 + 4C3 ・ P2 + 4C4 ・ P1
  = 6 ・ 6 + 4 ・ 2 + 1
  = 45

45個となります。

変数が存在しない場合

4変数のうち1変数が存在しない場合、4変数のうち2変数が存在しない場合、4変数のうち3変数が存在しない場合、4変数のすべてが存在しない場合、各々の場合を考えます。

 4C1  4C2  4C3  4C4

4変数のうち3変数が存在しない場合、4変数のすべてが存在しない場合、については、順序関係が成り立ちませんので、これ以上を考える必要はありません。

4変数のうち1変数が存在しない場合、4変数のうち2変数が存在しない場合、については、それぞれ、3変数の順序関係、2変数の順序関係がありますので、これを考えます。

4変数のうち1変数が存在しない場合(3変数の順序関係):

 P3 + 3C2 ・ P2 + 3C3 ・ P1
  = 6 + 3 ・ 2 + 1
  = 13

4変数のうち2変数が存在しない場合(2変数の順序関係):

 P2 + 2C2 ・ P1
  = 2 + 1
  = 3

従いまして、

 4C1 ・ 13 + 4C2 ・ 3 + 4C3 + 4C4
  = 4 ・ 13 + 6 ・ 3 + 4 + 1
  = 75

75個となります。

まとめ

以上の結果から、 X が真とならない関係は、

 23 + 45 + 75 = 143

全部で143個となります。

この問題は、コンピュータ・ソフトウエアの仕様を考えるものとしても良いですし、プログラムのテストケースを考えるものとしても良いかと思います。詳細仕様の1つの条件について、143個のケースを顧客と打ち合わせる、というのはかなり困難かもしれませんね。プログラムのテストケースであれば、このぐらいはやることもあるでしょうが。

現実には、なんらかの事前条件が使えると思いますので、ここまでケースが膨らむことはないでしょう。典型的には、 x1 < x3, x2 < x4 などが事前条件として与えられることが多いと思います。4分の1くらいには減らせますかね。

|

« フォーマル・メソッドと日本語プログラミング | トップページ | 順序関係を列挙する »

コメント

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.f.cocolog-nifty.com/t/trackback/80472/11378679

この記事へのトラックバック一覧です: 4変数の順序関係はいくつあるか?:

« フォーマル・メソッドと日本語プログラミング | トップページ | 順序関係を列挙する »