nCr과 nPr 구하기
소개
이전에 쓴 기사 "논리 퍼즐을 프로그래밍 방식으로 해결"에서 조합 (nCr)을 요구하는 기사를 썼습니다. 여기에서 파생시켜 순열(nPr)을 구하는 방법을 씁니다.
Swift를 사용하고 있습니다.
1 방법
하는 방법은 분명 여러가지일 것입니다만, 조합을 요구해 그 결과를 바탕으로 순열을 요구합니다.
2 조합 (nCr)
※이전에 쓴 기사 「 논리 퍼즐을 프로그래밍 방식으로 해결 」의 코피페입니다.
「집합 n」으로부터 「r인」 꺼내므로, 이 2개를 인수로서 「집합의 집합」을 반환값으로 하는 함수로 합니다.
① 인수 n의 요소수의 수 반복하는 함수를 r회 재귀시킵니다. ${}_4C_2$이면 $4^2$회의 계산을 실시해, 각각의 집합을 만들어 갑니다.
②완성된 집합 중, 요소수가 r인 것만, 반환값의 집합에 넣습니다.
③ 반환값의 집합은 중복을 배제하므로, 최종적으로는 독특한 집합만이 남습니다.
nCr.swiftimport 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.swiftimport 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종류의 집합이 생겼습니다.
Reference
이 문제에 관하여(nCr과 nPr 구하기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://qiita.com/s140/items/e10350a76bdeeba91a43
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
하는 방법은 분명 여러가지일 것입니다만, 조합을 요구해 그 결과를 바탕으로 순열을 요구합니다.
2 조합 (nCr)
※이전에 쓴 기사 「 논리 퍼즐을 프로그래밍 방식으로 해결 」의 코피페입니다.
「집합 n」으로부터 「r인」 꺼내므로, 이 2개를 인수로서 「집합의 집합」을 반환값으로 하는 함수로 합니다.
① 인수 n의 요소수의 수 반복하는 함수를 r회 재귀시킵니다. ${}_4C_2$이면 $4^2$회의 계산을 실시해, 각각의 집합을 만들어 갑니다.
②완성된 집합 중, 요소수가 r인 것만, 반환값의 집합에 넣습니다.
③ 반환값의 집합은 중복을 배제하므로, 최종적으로는 독특한 집합만이 남습니다.
nCr.swiftimport 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.swiftimport 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종류의 집합이 생겼습니다.
Reference
이 문제에 관하여(nCr과 nPr 구하기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://qiita.com/s140/items/e10350a76bdeeba91a43
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
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
}
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(["山本", "佐藤", "吉田"])]
순열은 조합으로 작성한 집합에 더 순서를 생각하면 좋을 뿐입니다. 따라서 함수 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종류의 집합이 생겼습니다.
Reference
이 문제에 관하여(nCr과 nPr 구하기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://qiita.com/s140/items/e10350a76bdeeba91a43텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)