UNIXコマンドで順列・組み合わせの問題を解こう

最終更新日: 2001-02-07 (公開日: 2001-01-03)

薩摩順吉著『確率・統計』 p.15 の問題を UNIXコマンドと順列生成プログ ラムを使っていんちきなやり方で解きます。 (注意: この方法は、文字列が長くなるとすぐに破綻します)

準備

文字列の順列を生成するプログラム permstr が必要です (Schemeで書かれていま す)。permstr を動かすには guile が必要です。
permstrの動作例:

    % permstr abcde | column
    abcde   adceb   bcade   becda   cdabe   daceb   deabc   ebcda
    abced   adebc   bcaed   bedac   cdaeb   daebc   deacb   ebdac
    abdce   adecb   bcdae   bedca   cdbae   daecb   debac   ebdca
    abdec   aebcd   bcdea   cabde   cdbea   dbace   debca   ecabd
    abecd   aebdc   bcead   cabed   cdeab   dbaec   decab   ecadb
    abedc   aecbd   bceda   cadbe   cdeba   dbcae   decba   ecbad
    acbde   aecdb   bdace   cadeb   ceabd   dbcea   eabcd   ecbda
    acbed   aedbc   bdaec   caebd   ceadb   dbeac   eabdc   ecdab
    acdbe   aedcb   bdcae   caedb   cebad   dbeca   eacbd   ecdba
    acdeb   bacde   bdcea   cbade   cebda   dcabe   eacdb   edabc
    acebd   baced   bdeac   cbaed   cedab   dcaeb   eadbc   edacb
    acedb   badce   bdeca   cbdae   cedba   dcbae   eadcb   edbac
    adbce   badec   beacd   cbdea   dabce   dcbea   ebacd   edbca
    adbec   baecd   beadc   cbead   dabec   dceab   ebadc   edcab
    adcbe   baedc   becad   cbeda   dacbe   dceba   ebcad   edcba

問: IWANAMI という語の7文字をすべて用いて並べるとき、次の総数を求めよ

(i) 異なる順列の総数

    % permstr iwanami | sort | uniq | wc -l 
       1260

(ii) AA という並び方と、 II という並び方を、ともに含む順列の総数

    % permstr iwanami | sort | uniq | grep aa | grep ii | wc -l 
        120

(iii) AI という並び方または IA という並び方を少なくとも1つ含む順列の総数

    % permstr iwanami | sort | uniq | egrep '(ai|ia)' | wc -l 
       1008

類題: りんご 5 個を袋 A, B, C にいれる分け方は何通りあるか

ただし (0, 0, 5) のように 1個も入っていない袋があってもよい。 

   % permstr ooooo:: | sort | uniq | wc -l
      21

おまけ: 括弧の色を薄くしよう

Emacs で Lisp プログラムを編集するときは、括弧の色を薄くして います。comp.lang.scheme で話題になっていた設定を真似ました。 C言語でも同様です。括弧が目立たないとPython 風でなかなかいい です。

[emacs image]

~/.emacs の設定方法

  (defvar paren-face 'paren-face)
  (make-face 'paren-face)
  (set-face-foreground 'paren-face "#88aaff")

  (defvar brace-face 'brace-face)
  (make-face 'brace-face)
  (set-face-foreground 'brace-face "#ffaa88")

  (defvar bracket-face 'bracket-face)
  (make-face 'bracket-face)
  (set-face-foreground 'bracket-face "#aaaa00")

  (setq lisp-font-lock-keywords-2
        (append '(("(\\|)" . paren-face))
                lisp-font-lock-keywords-2))

  (setq lisp-font-lock-keywords-2
        (append '(("(\\|)" . paren-face))
                lisp-font-lock-keywords-2))

  (add-hook 'scheme-mode-hook
            '(lambda ()
               (setq scheme-font-lock-keywords-2
                     (append '(("(\\|)" . paren-face))
                             scheme-font-lock-keywords-2))))

  (setq c-font-lock-keywords-3
        (append '(("(\\|)" . paren-face))
                '(("{\\|}" . brace-face))
                '(("\\[\\|\\]" . bracket-face))
                c-font-lock-keywords-3))
Satoru Takabayashi