satocchiaブログ

組み合わせの生成１

順列と組み合わせ。昔、学校でなんとなく習ったような。でも、数学で習ったのは順列・組み合わせの総数を数えることばかりで、実際に順列・組み合わせをつくってリストアップするというのはやらなかった気がします。　こういう、決まったルールで単純な手順を繰り返すというのは、コンピュータの得意分野ですね。なので、けっこう、解説サイトもたくさんあったりしますが、なぜか、取り上げれられているのは順列ばかりで、組み合わせの列挙アルゴリズムは少ないような気がします。 　それでも、​Rosetta　Code​にはいろんな言語の組み合わせプログラムがあります。powershellもあるんだけど、なにこれ、ただのC#じゃん。powershellの部分は「$source = @'」と「add-type」だけじゃん。　　で、powershellで作ってみました。function    Combi( $n=$null, [int]$r=$null ) {    if ( ( !$n) -or ( !$r ) ){ return $null}    if ( $n.gettype().name -match "\[\]$"){         $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 ){        $b=[convert]::ToString($n,2)        $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秒もかかってしまう。ということで、今後改良していくつもりです。