Julia(Combinatorics)で順列、組み合わせの問題を解く方法

どうも、木村(@kimu3_slime)です。

今回は、Julia(Combinatorics)で順列、組み合わせの問題を解く方法を紹介します。

 

準備

Combinatoricsを使うので、持っていなければインストールしておきましょう。

準備として、以下のコードを実行しておきます。

 

順列、組み合わせの個数

階乗\(n!\)は「factorial(n)」です。

 

順列の個数\(_n P_k\)は、「partialderangement(n,k)」です。

 

組み合わせの個数\(_n C _k\)は、「binomial(n,k)」です。

階乗と組み合わせは、Combinatoricsと関係なく、基本的な関数(Base)として使えます。

 

順列、組み合わせの求め方

3つの文字\(a,b,c\)を使って、異なる3文字を選んで並べた文字列の順列を求めてみましょう。

文字の候補を配列として用意し、「collect(permutations(配列))」です。

 

「collect(permutations(配列,サイズ))」で、サイズを指定した順列が求められます。3文字から異なる2文字を並べる順列なら次の通り。

 

順列では\(ab\)と\(ba\)が区別されています。

順番を区別しない考え方、組み合わせは「collect(combinations(配列,サイズ))」です。

 

与える文字列(配列)の順序を変えてみましょう。

順列の順番も変わっています。得られる結果を辞書式にしたいならば、「sort」を使いましょう。

 

重複する文字がある配列を与えると、どうなるでしょうか。

配列に同じ文字aがあっても、順列としては区別して計算されていますね。

これらから重複しない結果を得るには「unique」を使うと良いでしょう。

 

今までの関数を利用して、次のような問題を解いてみましょう。

GAKKOUの6文字を並び替えてできる360個の文字列を辞書式に並べるとき、100番目の文字列を求めよ 数学科 若月一模

引用:電車内「答え出た時泣くかと思った」…受験生への応援メッセージに数学Aの問題 作成した予備校講師に聞いた思い – まいどなニュース

 

与えられた文字のリストから文字列を作るのは、順列の問題です。与える文字に重複「K」があるので、結果の重複のない順列を求めます。

 

確かに360個の文字列ができるわけですが、これらを辞書式に並べ替えて、100番目の要素を取り出してみましょう。

「GOKAKU」という文字列、すなわち合格という答えが得られました。ちょうど100番目というのが良くできた問題ですね。

 

「100番目」という情報を知らないとして、「GOKAKU」という文字列が辞書式で何番目なのか求めてみましょう。

「indexin(配列B, 配列A)」で、配列Aにおいて配列Bの要素が何番目なのか(index)をまとめた配列が求められます。

これを使えば、

と何番目にあるか求めることができました。

 

以上、Julia(Combinatorics)で順列、組み合わせの問題を解く方法を紹介してきました。

与えられた単語に対し、その文字列を入れ替えて別の単語を作る遊びは、アナグラムと呼ばれています。Combinatoricsを使えば、アナグラムの問題や回答が作りやすそうですね。

木村すらいむ(@kimu3_slime)でした。ではでは。

 

1から始める Juliaプログラミング
進藤 裕之(著), 佐藤 建太(著)
コロナ社 (2020-03-26T00:00:01Z)
5つ星のうち4.5
¥7,353 (コレクター商品)

 

こちらもおすすめ

組み合わせ・二項係数nCkの覚え方:パスカルの三角形