はじめに
以前書いた記事「論理パズルをプログラムで解く」で、組み合わせ(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種類の集合ができました。