nCrとnPrを求める

17023 ワード
再帰 Swift 数学 順列組み合わせ 数学 テキストリンク

はじめに

以前書いた記事「論理パズルをプログラムで解く」で、組み合わせ(nCr)を求める記事を書きました。ここから派生させて順列(nPr)を求める方法を書きます。
Swiftを使用しています。

1　やりかた

やりかたはきっと色々あるのでしょうが、組み合わせを求めてその結果をもとに順列を求めます。

2　組み合わせ(nCr)

※以前書いた記事「論理パズルをプログラムで解く」のコピペです。
「集合n」から「r人」取り出すので、この２つを引数として「集合の集合」を戻り値とする関数とします。
①引数nの要素数の数繰り返す関数をr回再帰させます。${}_4C_2$であれば、$4^2$回の計算を行い、それぞれの集合を作っていきます。
②出来上がった集合のうち、要素数がｒのものだけ、戻り値の集合に入れます。
③戻り値の集合は、重複を排除するので、最終的にはユニークな集合のみが残ります。

nCr.swift
import UIKit

func nCr<T>(n:Set<T>,r:Int)->Set<Set<T>>{                  //引数nは集合、rは整数、戻り値は集合の集合（ジェネリクス）
    var results:Set<Set<T>> = []                           //戻り値用の変数(results)
    func rec(itr:Int,result:Set<T>){                       //再帰関数。引数は再帰回数itrと作成中の集合result
        guard itr<r else{                                  //他の言語のwhileみたいなの。rがitrと同じになれば再帰終了。
            result.count == r ? results.insert(result):nil //出来上がった集合resultの要素数がrであれば、resultsに代入
            return
        }
        for num:T in n{                                    //関数nCrの要素をひとつずつ取り出す。
            var myResult:Set<T> = result                   //次の再帰関数の引数用の集合myResultを用意
            myResult.insert(num)                           //myResultに集合nから取り出した要素numを追加
            rec(itr: itr + 1, result: myResult)            //再帰させる
        }
    }
    rec(itr: 0, result: [])                                //再帰関数の開始
    return results
}

ためしに[1,2,5,10]から2つ取り出す組み合わせを作ってみましょう。${}_4C_2$＝６種類の集合ができるはずです。

print(nCr(n: [1,2,5,10], r: 2))
//[Set([1, 10]), Set([10, 2]), Set([10, 5]), Set([2, 1]), Set([5, 1]), Set([2, 5])]

うまくできました。
ちなみに、汎用性を高めるために戻り値はジェネリクスにしていますので、「６人のクラスの中から３人選ぶ」みたいな組み合わせもこんな感じでできます。

print(nCr(n: ["佐藤","鈴木","吉田","高橋","山本","斎藤"],r: 3))
//[Set(["山本", "高橋", "吉田"]), Set(["鈴木", "佐藤", "吉田"]), Set(["鈴木", "高橋", "吉田"]), Set(["吉田", "佐藤", "高橋"]), Set(["吉田", "斎藤", "高橋"]), Set(["鈴木", "山本", "高橋"]), Set(["鈴木", "佐藤", "高橋"]), Set(["山本", "佐藤", "高橋"]), Set(["鈴木", "斎藤", "吉田"]), Set(["山本", "佐藤", "斎藤"]), Set(["山本", "斎藤", "吉田"]), Set(["鈴木", "佐藤", "斎藤"]), Set(["鈴木", "山本", "佐藤"]), Set(["吉田", "佐藤", "斎藤"]), Set(["鈴木", "山本", "吉田"]), Set(["鈴木", "斎藤", "高橋"]), Set(["山本", "斎藤", "高橋"]), Set(["鈴木", "山本", "斎藤"]), Set(["高橋", "佐藤", "斎藤"]), Set(["山本", "佐藤", "吉田"])]

${}_6C_3$＝20種類の集合ができました。

3 順列(nPr)

順列は、組み合わせで作成した集合に更に順番を考えればいいだけです。よって、関数nCrの答えをそのまま受け取って、要素数に応じた順番を作成する関数を作ればよいことになります。

nPr.swift
import UIKit
func nCr<T>(n:Set<T>,r:Int)->Set<Set<T>>{                  //引数nは集合、rは整数、戻り値は集合の集合（ジェネリクス）
    var results:Set<Set<T>> = []                           //戻り値用の変数(results)
    func rec(itr:Int,result:Set<T>){                       //再帰関数。引数は再帰回数itrと作成中の集合result
        guard itr<r else{                                  //他の言語のwhileみたいなの。rがitrと同じになれば再帰終了。
            result.count == r ? results.insert(result):nil //出来上がった集合resultの要素数がrであれば、resultsに代入
            return
        }
        for num:T in n{                                    //関数nCrの要素をひとつずつ取り出す。
            var myResult:Set<T> = result                   //次の再帰関数の引数用の集合myResultを用意
            myResult.insert(num)                           //myResultに集合nから取り出した要素numを追加
            rec(itr: itr + 1, result: myResult)            //再帰させる
        }
    }
    rec(itr: 0, result: [])                                //再帰関数の開始
    return results
}

func nPr<T>(n:Set<T>,r:Int)->Set<[T]>{//nCrはSet<Set<T>>だけど、nPrは、Set<[T]>が戻り値
    var results:Set<[T]> = []                           //戻り値用の変数(results)
    func rec(myArray:[T],result:[T]){//再帰関数
        guard myArray.count != 0 else{
            results.insert(result)
            return
        }
        for i in 0..<myArray.count{//与えられた配列から要素を取り出して
            var myNewArray = myArray//変数にして処理
            myNewArray.remove(at: i)
            var myResult = result
            myResult.append(myArray[i])
            rec(myArray: myNewArray, result: myResult)//再帰させる
        }
    }

    for mySet:Set<T> in nCr(n: n, r: r){//関数nCrで集合の集合を作って分解
        var myArray:[T] = mySet.map({(myValue) in myValue})//mapを使って、集合を配列にする
        rec(myArray: myArray, result: [])//再帰開始
    }
    return results
}

ためしてみます。

print(nPr(n: ["佐藤","鈴木","吉田","高橋","山本","斎藤"],r: 3)

${}_6P_3$＝120種類の集合ができました。