PR
キーワードサーチ
▼キーワード検索
カレンダー
コメント新着
2018.08.18
カテゴリ： アルゴリズム
順列と組み合わせ。昔、学校でなんとなく習ったような。でも、数学で習ったのは順列・組み合わせの総数を数えることばかりで、実際に順列・組み合わせをつくってリストアップするというのはやらなかった気がします。
こういう、決まったルールで単純な手順を繰り返すというのは、コンピュータの得意分野ですね。なので、けっこう、解説サイトもたくさんあったりしますが、なぜか、取り上げれられているのは順列ばかりで、組み合わせの列挙アルゴリズムは少ないような気がします。
それでも、 Rosetta Code にはいろんな言語の組み合わせプログラムがあります。powershellもあるんだけど、なにこれ、ただのC#じゃん。powershellの部分は「 $source = @ '」と「add-type」だけじゃん。
で、powershellで作ってみました。
function Combi( $n=$null, [int]$r=$null ) {
if ( ( !$n) -or ( !$r ) ){ return $null}
$ary=$n; $n=$ary.length
}else{
try{
$n=[int64]$n
if ( $n -lt 1 ) { return }
$ary=0..($n-1)|%{[string]$_}
} catch {
return $null
}
}
function bitCount( $n ){
$cnt=0
0..($b.length-1)|%{
if ( $b[$_] -eq "1" ){
$cnt++
}
return $cnt
}
function pow2([int64]$n){
if( $n -lt 0 ){return $null}
if ( test-path global:pow2 ){
return $global:pow2."$n"
} else {
$global:pow2=@{}
$global:pow2."0"=$k=[int64]1
1..62|%{
$k *=[int64]2
$global:pow2."$_"=$k
}
}
return $global:pow2."$n"
}
$res =@()
((pow2 $n)-1)..0|%{
if ( ( bitcount $_ ) -eq $r ){
$subres=@()
$b=[convert]::ToString( $_, 2 ).padleft($n, "0")
0..($n-1)|%{
if ( $b[$_] -eq "1" ){
$subres +=,$ary[$_]
}
}
#"$b`t" + ($subres -join ",")|write-host
$res +=,$subres
}
#@($subres)
}
return $res
}
combi "abcdefg"[0..7] 3|%{$_ -join ","}
combi 10 4|%{$_ -join ","}
アルゴリズムはいろいろあるようだけど二進数を使ったやつを採用。
0～2^n-1の二進数を生成し、立っているビットがちょうどr個のものを集めると、すべての組み合わせを網羅できるという仕組み。ただ、これ、けっこう遅くて
combi 10 3
で0.5秒
combi 15 3
で12.5秒もかかってしまう。ということで、今後改良していくつもりです。
こういう、決まったルールで単純な手順を繰り返すというのは、コンピュータの得意分野ですね。なので、けっこう、解説サイトもたくさんあったりしますが、なぜか、取り上げれられているのは順列ばかりで、組み合わせの列挙アルゴリズムは少ないような気がします。
それでも、 Rosetta Code にはいろんな言語の組み合わせプログラムがあります。powershellもあるんだけど、なにこれ、ただのC#じゃん。powershellの部分は「 $source = @ '」と「add-type」だけじゃん。
で、powershellで作ってみました。
function Combi( $n=$null, [int]$r=$null ) {
if ( ( !$n) -or ( !$r ) ){ return $null}
$ary=$n; $n=$ary.length
}else{
try{
$n=[int64]$n
if ( $n -lt 1 ) { return }
$ary=0..($n-1)|%{[string]$_}
} catch {
return $null
}
}
function bitCount( $n ){
$cnt=0
0..($b.length-1)|%{
if ( $b[$_] -eq "1" ){
$cnt++
}
return $cnt
}
function pow2([int64]$n){
if( $n -lt 0 ){return $null}
if ( test-path global:pow2 ){
return $global:pow2."$n"
} else {
$global:pow2=@{}
$global:pow2."0"=$k=[int64]1
1..62|%{
$k *=[int64]2
$global:pow2."$_"=$k
}
}
return $global:pow2."$n"
}
$res =@()
((pow2 $n)-1)..0|%{
if ( ( bitcount $_ ) -eq $r ){
$subres=@()
$b=[convert]::ToString( $_, 2 ).padleft($n, "0")
0..($n-1)|%{
if ( $b[$_] -eq "1" ){
$subres +=,$ary[$_]
}
}
#"$b`t" + ($subres -join ",")|write-host
$res +=,$subres
}
#@($subres)
}
return $res
}
combi "abcdefg"[0..7] 3|%{$_ -join ","}
combi 10 4|%{$_ -join ","}
アルゴリズムはいろいろあるようだけど二進数を使ったやつを採用。
0～2^n-1の二進数を生成し、立っているビットがちょうどr個のものを集めると、すべての組み合わせを網羅できるという仕組み。ただ、これ、けっこう遅くて
combi 10 3
で0.5秒
combi 15 3
で12.5秒もかかってしまう。ということで、今後改良していくつもりです。
お気に入りの記事を「いいね！」で応援しよう
[アルゴリズム] カテゴリの最新記事
-
組み合わせの生成2 2018.09.06
【毎日開催】
15記事にいいね！で1ポイント
© Rakuten Group, Inc.
