nCr과 nPr 구하기

소개



이전에 쓴 기사 "논리 퍼즐을 프로그래밍 방식으로 해결"에서 조합 (nCr)을 요구하는 기사를 썼습니다. 여기에서 파생시켜 순열(nPr)을 구하는 방법을 씁니다.
Swift를 사용하고 있습니다.

1 방법



하는 방법은 분명 여러가지일 것입니다만, 조합을 요구해 그 결과를 바탕으로 순열을 요구합니다.

2 조합 (nCr)



※이전에 쓴 기사 「 논리 퍼즐을 프로그래밍 방식으로 해결 」의 코피페입니다.
「집합 n」으로부터 「r인」 꺼내므로, 이 2개를 인수로서 「집합의 집합」을 반환값으로 하는 함수로 합니다.
① 인수 n의 요소수의 수 반복하는 함수를 r회 재귀시킵니다. ${}_4C_2$이면 $4^2$회의 계산을 실시해, 각각의 집합을 만들어 갑니다.
②완성된 집합 중, 요소수가 r인 것만, 반환값의 집합에 넣습니다.
③ 반환값의 집합은 중복을 배제하므로, 최종적으로는 독특한 집합만이 남습니다.

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$=6 종류의 집합을 할 수 있을 것입니다.
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])]

잘 했어요.
덧붙여서, 범용성을 높이기 위해서 반환값은 제네릭스로 하고 있으므로, 「6명의 클래스 중에서 3명 선택한다」같은 조합도 이런 느낌으로 할 수 있습니다.
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종류의 집합이 생겼습니다.

좋은 웹페이지 즐겨찾기