Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

Golang で順列・組み合わせ・重複順列・重複組み合わせの列挙

関連記事

本記事は Geek-Space Advent Calendar 2020 の 7 日目です。(間に合ってない)

はじめに

関連記事にある通り、ここまで順列に関して 3 つのやり方を追求していきました。
今回はこの 3 つのやり方(再帰を用いる、スタックを用いる、繰り上がり法)を、組み合わせ、重複順列、重複組合せにも適用することで、この辺のパターンをひと通り網羅しておこうと思います。

計測は今まで同様、以下のオンボロマシンです:

macOS Big Sur
バージョン 11.0.1

MacBook Air (11-inch, Early 2015)
プロセッサ 1.6 GHz デュアルコアIntel Core i5
メモリ 4 GB 1600 MHz DDR3

go version go1.15.5 darwin/amd64

計測結果は少し編集して、実行時間(ns)、使用メモリ容量(B)、メモリ割り当て数(allocs)を載せます。

コードは全てこちらのリポジトリに上げてあります。(これも今までの記事と同様)
https://github.com/ikngtty/benchmark-go-combinatorics

順列

tree-graph.png

詳しくは関連記事に書いた通りです。ここでは結論をまとめ直していきます。

下準備

以下のコードでパフォーマンスを計測しました:

combinatorics/perm_test.go
func BenchmarkPermutations(b *testing.B) {
    const n = 10
    const k = 10

    doSomethingForPattern := func(pattern []int) {
        total := 0
        for i := 1; i < len(pattern); i++ {
            total += pattern[i] - pattern[i-1]
        }
    }

    targets := []struct {
        name string
        f    func()
    }{
        {"テスト対象関数の名前",
            func() {
                // テスト対象関数を用いて、[0, 1, ..., n-1]の数の中からk個選ぶ順列を生成し、
                // 各順列に対して`doSomethingForPattern`を行う。
            }},
        // ...
    }

    for _, target := range targets {
        b.Run(target.name, func(b *testing.B) {
            for try := 0; try < b.N; try++ {
                target.f()
            }
        })
    }
}

再帰を用いたやり方

最も素直な実装はこんな感じでした。

combinatorics/perm.go
func PermutationsRecursive0(a []int, k int) [][]int {
    if k == 0 {
        pattern := []int{}
        return [][]int{pattern}
    }

    ans := [][]int{}
    for i := range a {
        aRest := make([]int, len(a)-1)
        for j := 0; j < i; j++ {
            aRest[j] = a[j]
        }
        for j := i + 1; j < len(a); j++ {
            aRest[j-1] = a[j]
        }

        childPatterns := PermutationsRecursive0(aRest, k-1)
        for _, childPattern := range childPatterns {
            pattern := append([]int{a[i]}, childPattern...)
            ans = append(ans, pattern)
        }
    }

    return ans
}

しかし実測結果は以下のようにズタボロ:

PermutationsRecursive0      6338217782 ns   5168828928 B    89707742 allocs

ここから色々改善し、以下のコードにたどり着きました:

combinatorics/perm.go
func PermutationsRecursive6(n, k int, f func([]int)) {
    checklist := make([]bool, n)
    pattern := make([]int, k)

    var body func(pos int)
    body = func(pos int) {
        if pos == k {
            f(pattern)
            return
        }

        for num := range checklist {
            if checklist[num] {
                continue
            }

            pattern[pos] = num
            checklist[num] = true
            body(pos + 1)
            checklist[num] = false
        }
    }
    body(0)
}
PermutationsRecursive6       191816791 ns           96 B           2 allocs

スタックを用いたやり方

最終的に、スライスでスタックを実装すると良いことが分かりました。
色々細かくスタックの使い方を変えたりしましたが、スライス版の場合は大してパフォーマンスが変わらないものが多かったです。
なので今回はその中でも一番スタンダードっぽい、「樹形図のノードをスタックに積む」という発想のやつをセレクトします。

combinatorics/perm.go
func PermutationsWithSlice2(n, k int, f func([]int)) {
    checklist := make([]bool, n)
    patternNodeStack := make([]patternNode2, 1)
    pattern := make([]int, k)

    patternNodeStack[0] = patternNode2{pos: -1, number: 0}
    for len(patternNodeStack) > 0 {
        patternNode := patternNodeStack[len(patternNodeStack)-1]
        patternNodeStack = patternNodeStack[:len(patternNodeStack)-1]

        for i := patternNode.pos; i < k; i++ {
            if i > -1 && pattern[i] > -1 {
                checklist[pattern[i]] = false
                pattern[i] = -1
            }
        }

        if patternNode.pos > -1 {
            pattern[patternNode.pos] = patternNode.number
            checklist[patternNode.number] = true
        }

        if patternNode.pos == k-1 {
            f(pattern)
            continue
        }

        for num := n - 1; num >= 0; num-- {
            if checklist[num] {
                continue
            }

            childNode := patternNode2{
                pos: patternNode.pos + 1, number: num,
            }
            patternNodeStack = append(patternNodeStack, childNode)
        }
    }
}
PermutationsWithSlice2       186323035 ns         2112 B           8 allocs

繰り上がり法

分かりやすいやつとループをまとめて工夫したやつ、2 つ取り上げます。

combinatorics/perm.go
func PermutationsWithCarrying1(n, k int, f func([]int)) {
    checklist := make([]bool, n)
    pattern := make([]int, k)
    for i := range pattern {
        pattern[i] = i
        checklist[i] = true
    }

    for {
        f(pattern)

        pos := k - 1
        for {
            if pos == -1 {
                return
            }

            oldNum := pattern[pos]
            checklist[oldNum] = false

            willBreak := false
            for newNum := oldNum + 1; newNum < n; newNum++ {
                if checklist[newNum] {
                    continue
                }

                pattern[pos] = newNum
                checklist[newNum] = true
                willBreak = true
                break
            }
            if willBreak {
                break
            }

            pos--
        }

        for pos++; pos < k; pos++ {
            for num := 0; num < k; num++ {
                if checklist[num] {
                    continue
                }

                pattern[pos] = num
                checklist[num] = true
                break
            }
        }
    }
}

func PermutationsWithCarrying2(n, k int, f func([]int)) {
    checklist := make([]bool, n)
    pattern := make([]int, k)
    for i := range pattern {
        pattern[i] = i
        checklist[i] = true
    }

    pos := k
    for pos > -1 {
        if pos == k {
            f(pattern)
            pos--
            continue
        }

        oldNum := pattern[pos]
        if oldNum > -1 {
            checklist[oldNum] = false
        }

        willContinue := false
        for newNum := oldNum + 1; newNum < n; newNum++ {
            if checklist[newNum] {
                continue
            }

            pattern[pos] = newNum
            checklist[newNum] = true
            pos++
            willContinue = true
            break
        }
        if willContinue {
            continue
        }

        pattern[pos] = -1
        pos--
    }
}
PermutationsWithCarrying1    149944171 ns           96 B           2 allocs
PermutationsWithCarrying2    170103707 ns           96 B           2 allocs

計測結果まとめ

PermutationsRecursive0      6338217782 ns   5168828928 B    89707742 allocs
PermutationsRecursive6       191816791 ns           96 B           2 allocs
PermutationsWithSlice2       186323035 ns         2112 B           8 allocs
PermutationsWithCarrying1    149944171 ns           96 B           2 allocs
PermutationsWithCarrying2    170103707 ns           96 B           2 allocs

組み合わせ

tree-graph.png

1 桁目の数字 < 2 桁目の数字 < ... < k 桁目の数字 という制約をつければ、あとは順列と同様に列挙することができます。
というか、今までは「x 桁目に使える数字」を考える時に「1 〜 x-1 桁目までに使われた数字を全て把握する」ということが必要でしたが(そのために「使用済み番号チェックリスト」という概念を持ち出したりしました)、今回の場合は「x-1 桁目の数字より上の数字が全部使える」とはっきり分かるので、その辺の処理が一気に楽になります。
ただ、例えば [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] から 6 個選ぶ組み合わせの時に、3 桁目とかに 9 を使ってしまうと、4 桁目以降に使える数字がなくなってしまったりします。一番大きい組み合わせが {4, 5, 6, 7, 8, 9} となるのを考えると、3 桁目の上限は 6 ですね。
この辺を加味すると、[0, 1, ..., n-1] から k 個選ぶ組み合わせにおいて x 桁目に使える数字は、「x-1 桁目の数字より上で、n-1-k+x 以下」となってきます。
ここまで整理できれば実装できたも同然です。

下準備

以下のコードで計測(ほとんど n と k を弄っただけです):

combinatorics/combi_test.go
func BenchmarkCombinations(b *testing.B) {
    const n = 24
    const k = 12

    doSomethingForPattern := func(pattern []int) {
        total := 0
        for i := 1; i < len(pattern); i++ {
            total += pattern[i] - pattern[i-1]
        }
    }

    targets := []struct {
        name string
        f    func()
    }{
        {"テスト対象関数の名前",
            func() {
                // テスト対象関数を用いて、[0, 1, ..., n-1]の数の中からk個選ぶ組み合わせを生成し、
                // 各組み合わせに対して`doSomethingForPattern`を行う。
            }},
        // ...
    }

    for _, target := range targets {
        b.Run(target.name, func(b *testing.B) {
            for try := 0; try < b.N; try++ {
                target.f()
            }
        })
    }
}

再帰を用いたやり方

素直に書けばこう:

combinatorics/combi.go
// [begin, begin+1, ..., end-1](半開区間)からk個選ぶ組み合わせ
func CombinationsRecursive0(begin, end, k int) [][]int {
    if k == 0 {
        pattern := []int{}
        return [][]int{pattern}
    }

    ans := [][]int{}
    for num := begin; num < end-k+1; num++ {
        childPatterns := CombinationsRecursive0(num+1, end, k-1)
        for _, childPattern := range childPatterns {
            pattern := append([]int{num}, childPattern...)
            ans = append(ans, pattern)
        }
    }

    return ans
}

「x-1 桁目の数字より上の数字が x 桁目に使える数字の範囲」ということで、使える数字を範囲で受け取る形で書いています。

CombinationsRecursive0      5270823668 ns   5060925400 B    70747903 allocs

ここから同様に工夫を凝らすとこうなります:

combinatorics/combi.go
func CombinationsRecursive1(n, k int, f func([]int)) {
    pattern := make([]int, k)

    var body func(pos, begin int)
    body = func(pos, begin int) {
        if pos == k {
            f(pattern)
            return
        }

        for num := begin; num < n+pos-k+1; num++ {
            pattern[pos] = num
            body(pos+1, num+1)
        }
    }
    body(0, 0)
}
CombinationsRecursive1        55564969 ns           96 B           1 allocs

処理時間のオーダーが 2 桁違うので笑うしかない。

ちなみに、「x-1 桁目の数字」はわざわざ引数で渡さなくても生成中の組み合わせを見れば分かることなので、これを踏まえれば引数を 1 つ減らすことができます。

combinatorics/combi.go
func CombinationsRecursive2(n, k int, f func([]int)) {
    // 0桁目からでも-1桁目の数字を見れるように先頭にダミーを1桁追加している
    pattern := make([]int, k+1)
    // 生成中の順列には、「まだちゃんと値を入れていない」という情報を
    // ちゃんと-1として埋め込む必要が出てきた
    pattern[0] = -1

    var body func(pos int)
    body = func(pos int) {
        if pos == k+1 {
            f(pattern[1:]) // ダミーを除いて使用
            return
        }

        for num := pattern[pos-1] + 1; num < n+pos-k; num++ {
            pattern[pos] = num
            body(pos + 1)
        }
    }
    body(1)
}
CombinationsRecursive2        58998589 ns          112 B           1 allocs

なんかむしろ遅くなりました。ボツですね。

スタックを用いたやり方

combinatorics/combi.go
// 順列のコードから流用
type patternNode3 struct {
    pos    int
    number int
}

func CombinationsWithSlice0(n, k int, f func([]int)) {
    patternNodeStack := make([]patternNode3, 1)
    pattern := make([]int, k)

    patternNodeStack[0] = patternNode3{pos: -1, number: -1}
    for len(patternNodeStack) > 0 {
        patternNode := patternNodeStack[len(patternNodeStack)-1]
        patternNodeStack = patternNodeStack[:len(patternNodeStack)-1]

        if patternNode.pos > -1 {
            pattern[patternNode.pos] = patternNode.number
        }

        if patternNode.pos == k-1 {
            f(pattern)
            continue
        }

        for num := n + patternNode.pos - k + 1; num >= patternNode.number+1; num-- {
            childNode := patternNode3{
                pos: patternNode.pos + 1, number: num,
            }
            patternNodeStack = append(patternNodeStack, childNode)
        }
    }
}

チェックリストが必要なくなったので、ちょっとスッキリしています。

CombinationsWithSlice0        44367916 ns         8256 B           9 allocs

繰り上がり法

こちらも分かりやすいやつとループまとめて工夫したやつの 2 つ用意しました。

combinatorics/combi.go
func CombinationsWithCarrying0(n, k int, f func([]int)) {
    pattern := make([]int, k)
    for i := range pattern {
        pattern[i] = i
    }

    for {
        f(pattern)

        pos := k - 1
        for {
            if pos == -1 {
                return
            }

            oldNum := pattern[pos]
            if oldNum == n+pos-k {
                pos--
                continue
            }

            pattern[pos]++
            break
        }

        for pos++; pos < k; pos++ {
            pattern[pos] = pattern[pos-1] + 1
        }
    }
}

func CombinationsWithCarrying1(n, k int, f func([]int)) {
    pattern := make([]int, k)
    for i := range pattern {
        pattern[i] = i
    }

    pos := k
    for pos > -1 {
        if pos == k {
            f(pattern)
            pos--
            continue
        }

        oldNum := pattern[pos]
        if oldNum == n+pos-k {
            pattern[pos] = -1
            pos--
            continue
        }

        if oldNum == -1 {
            pattern[pos] = pattern[pos-1] + 1
        } else {
            pattern[pos]++
        }
        pos++
    }
}

順列と比べてだいぶ書きやすくなりましたね。ある桁の値を増やす時、飛び飛びの増え方をすることがなく、必ず 1 増やせばいいだけなのはデカいです。ループで少しずつ増やしながら試すということがなくなっています。
ただし、左向きに繰り上がりしながら値を増やそうとする時と、繰り上げた桁を後から右向きに振り返って埋め直す時の処理が、今回は共通化できず条件分岐しています。まあそれぐらいです。

CombinationsWithCarrying0     36928434 ns           96 B           1 allocs
CombinationsWithCarrying1     49481598 ns           96 B           1 allocs

なんか妙に差が出てる…。

計測結果まとめ

CombinationsRecursive0      5270823668 ns   5060925400 B    70747903 allocs
CombinationsRecursive1        55564969 ns           96 B           1 allocs
CombinationsRecursive2        58998589 ns          112 B           1 allocs
CombinationsWithSlice0        44367916 ns         8256 B           9 allocs
CombinationsWithCarrying0     36928434 ns           96 B           1 allocs
CombinationsWithCarrying1     49481598 ns           96 B           1 allocs

重複組合せ

tree-graph.png

順番前後して、先に重複組合せを取り上げます。
なぜかというと、重複組合せの列挙は組み合わせの時とほっとんど同じだからです。
組み合わせは 1 桁目の数字 < 2 桁目の数字 < ... < k 桁目の数字 という考え方をしましたが、これを 1 桁目の数字 <= 2 桁目の数字 <= ... <= k 桁目の数字 に変えてしまうだけで重複組合せになります。
なので組み合わせの次に並べたかったというわけです。

[0, 1, ..., n-1] から k 個選ぶ組み合わせにおいて x 桁目に使える数字を考えると、組合わせの時は「x-1 桁目の数字より上で、n-1-k+x 以下」でしたが、今回は「x-1 桁目の数字以上で、n以下」です。もっと簡単ですね。

下準備

また n と k を調整しただけですが、以下のコードで計測:

combinatorics/dup_combi_test.go
func BenchmarkDupCombinations(b *testing.B) {
    const n = 18
    const k = 9

    doSomethingForPattern := func(pattern []int) {
        total := 0
        for i := 1; i < len(pattern); i++ {
            total += pattern[i] - pattern[i-1]
        }
    }

    targets := []struct {
        name string
        f    func()
    }{
        {"テスト対象関数の名前",
            func() {
                // テスト対象関数を用いて、[0, 1, ..., n-1]の数の中からk個選ぶ重複組み合わせを生成し、
                // 各重複組み合わせに対して`doSomethingForPattern`を行う。
            }},
        // ...
    }

    for _, target := range targets {
        b.Run(target.name, func(b *testing.B) {
            for try := 0; try < b.N; try++ {
                target.f()
            }
        })
    }
}

再帰を用いたやり方

素直なやつ:

combinatorics/dup_combi.go
func DupCombinationsRecursive0(begin, end, k int) [][]int {
    if k == 0 {
        pattern := []int{}
        return [][]int{pattern}
    }

    ans := [][]int{}
    for num := begin; num < end; num++ {
        childPatterns := DupCombinationsRecursive0(num, end, k-1)
        for _, childPattern := range childPatterns {
            pattern := append([]int{num}, childPattern...)
            ans = append(ans, pattern)
        }
    }

    return ans
}

begin に渡す数字が num+1 ではなく num になり、ループ条件 num < end-k+1num < end になっています。そんだけ。

DupCombinationsRecursive0       4282572542 ns   4187600032 B    60615826 allocs

そんで改良:

combinatorics/dup_combi.go
func DupCombinationsRecursive1(n, k int, f func([]int)) {
    pattern := make([]int, k)

    var body func(pos, begin int)
    body = func(pos, begin int) {
        if pos == k {
            f(pattern)
            return
        }

        for num := begin; num < n; num++ {
            pattern[pos] = num
            body(pos+1, num)
        }
    }
    body(0, 0)
}
DupCombinationsRecursive1         47771265 ns           80 B           1 allocs

スタックを用いたやり方

combinatorics/dup_combi.go
// 順列のコードから流用
type patternNode3 struct {
    pos    int
    number int
}

func DupCombinationsWithSlice0(n, k int, f func([]int)) {
    patternNodeStack := make([]patternNode3, 1)
    pattern := make([]int, k)

    patternNodeStack[0] = patternNode3{pos: -1, number: 0}
    for len(patternNodeStack) > 0 {
        patternNode := patternNodeStack[len(patternNodeStack)-1]
        patternNodeStack = patternNodeStack[:len(patternNodeStack)-1]

        if patternNode.pos > -1 {
            pattern[patternNode.pos] = patternNode.number
        }

        if patternNode.pos == k-1 {
            f(pattern)
            continue
        }

        for num := n - 1; num >= patternNode.number; num-- {
            childNode := patternNode3{
                pos: patternNode.pos + 1, number: num,
            }
            patternNodeStack = append(patternNodeStack, childNode)
        }
    }
}

-1 桁目に入れるダミーの数字が -1 から 0 になってたりします。

DupCombinationsWithSlice0         42335223 ns         8240 B           9 allocs

繰り上がり法

combinatorics/dup_combi.go
func DupCombinationsWithCarrying0(n, k int, f func([]int)) {
    pattern := make([]int, k)

    for {
        f(pattern)

        pos := k - 1
        for {
            if pos == -1 {
                return
            }

            oldNum := pattern[pos]
            if oldNum == n-1 {
                pos--
                continue
            }

            pattern[pos]++
            break
        }

        numToReplace := pattern[pos]
        for pos++; pos < k; pos++ {
            pattern[pos] = numToReplace
        }
    }
}

func DupCombinationsWithCarrying1(n, k int, f func([]int)) {
    pattern := make([]int, k)

    pos := k
    for pos > -1 {
        if pos == k {
            f(pattern)
            pos--
            continue
        }

        oldNum := pattern[pos]
        if oldNum == n-1 {
            pattern[pos] = -1
            pos--
            continue
        }

        if oldNum == -1 {
            pattern[pos] = pattern[pos-1]
        } else {
            pattern[pos]++
        }
        pos++
    }
}

pattern には最初の重複組み合わせをセットする必要があるんですが、最初の組み合わせが {0, 1, 2} のような形になるのに対し、最初の重複組合せは {0, 0, 0} のような形になるので、配列を生成した時点でセット完了になっており、そのためセット処理が消えました。

DupCombinationsWithCarrying0      35562403 ns           80 B           1 allocs
DupCombinationsWithCarrying1      48869797 ns           80 B           1 allocs

計測結果まとめ

DupCombinationsRecursive0       4282572542 ns   4187600032 B    60615826 allocs
DupCombinationsRecursive1         47771265 ns           80 B           1 allocs
DupCombinationsWithSlice0         42335223 ns         8240 B           9 allocs
DupCombinationsWithCarrying0      35562403 ns           80 B           1 allocs
DupCombinationsWithCarrying1      48869797 ns           80 B           1 allocs

重複順列

tree-graph.png

後回しにした重複順列ですが、実は一番簡単です。
なんせ、各桁は他の桁が何を使っているかを全く意識する必要がありません。
全桁独立して考えれば OK です。
もちろんチェックリストも要りません。

下準備

n と k を調整した計測コード:

combinatorics/dup_perm_test.go
func BenchmarkDupPermutations(b *testing.B) {
    const n = 8
    const k = 7

    doSomethingForPattern := func(pattern []int) {
        total := 0
        for i := 1; i < len(pattern); i++ {
            total += pattern[i] - pattern[i-1]
        }
    }

    targets := []struct {
        name string
        f    func()
    }{
        {"テスト対象関数の名前",
            func() {
                // テスト対象関数を用いて、[0, 1, ..., n-1]の数の中からk個選ぶ重複順列を生成し、
                // 各重複順列に対して`doSomethingForPattern`を行う。
            }},
        // ...
    }

    for _, target := range targets {
        b.Run(target.name, func(b *testing.B) {
            for try := 0; try < b.N; try++ {
                target.f()
            }
        })
    }
}

再帰を用いたやり方

素直なやつ:

combinatorics/dup_perm.go
func DupPermutationsRecursive0(n, k int) [][]int {
    if k == 0 {
        pattern := []int{}
        return [][]int{pattern}
    }

    ans := [][]int{}
    for num := 0; num < n; num++ {
        childPatterns := DupPermutationsRecursive0(n, k-1)
        for _, childPattern := range childPatterns {
            pattern := append([]int{num}, childPattern...)
            ans = append(ans, pattern)
        }
    }

    return ans
}
DupPermutationsRecursive0       2145949059 ns   2020474264 B    30689223 allocs

改良:

combinatorics/dup_perm.go
func DupPermutationsRecursive1(n, k int, f func([]int)) {
    pattern := make([]int, k)

    var body func(pos int)
    body = func(pos int) {
        if pos == k {
            f(pattern)
            return
        }

        for num := 0; num < n; num++ {
            pattern[pos] = num
            body(pos + 1)
        }
    }
    body(0)
}
DupPermutationsRecursive1         23847135 ns           64 B           1 allocs

スタックを用いたやり方

combinatorics/dup_perm.go
// 順列のコードから流用
type patternNode3 struct {
    pos    int
    number int
}

func DupPermutationsWithSlice0(n, k int, f func([]int)) {
    patternNodeStack := make([]patternNode3, 1)
    pattern := make([]int, k)

    patternNodeStack[0] = patternNode3{pos: -1, number: 0}
    for len(patternNodeStack) > 0 {
        patternNode := patternNodeStack[len(patternNodeStack)-1]
        patternNodeStack = patternNodeStack[:len(patternNodeStack)-1]

        if patternNode.pos > -1 {
            pattern[patternNode.pos] = patternNode.number
        }

        if patternNode.pos == k-1 {
            f(pattern)
            continue
        }

        for num := n - 1; num >= 0; num-- {
            childNode := patternNode3{
                pos: patternNode.pos + 1, number: num,
            }
            patternNodeStack = append(patternNodeStack, childNode)
        }
    }
}
DupPermutationsWithSlice0         23043210 ns         2080 B           7 allocs

繰り上がり法

N 進法そのまんまなので、「繰り上がり」のニュアンスは重複順列が一番よく表れています。

ちなみに「繰り上がった桁を後でなるべく小さい数字で埋め直す」という作業ですが、今回は繰り上がった桁の数字は必ず 0 になるので、繰り上がると分かった時にさっさと 0 を入れてしまえばあとで埋め直す必要すらないです。

combinatorics/dup_perm.go
func DupPermutationsWithCarrying0(n, k int, f func([]int)) {
    pattern := make([]int, k)

    for {
        f(pattern)

        pos := k - 1
        for {
            if pos == -1 {
                return
            }

            oldNum := pattern[pos]
            if oldNum == n-1 {
                pattern[pos] = 0
                pos--
                continue
            }

            pattern[pos]++
            break
        }
    }
}

func DupPermutationsWithCarrying1(n, k int, f func([]int)) {
    pattern := make([]int, k)

    pos := k
    for pos > -1 {
        if pos == k {
            f(pattern)
            pos--
            continue
        }

        oldNum := pattern[pos]
        if oldNum == n-1 {
            pattern[pos] = 0
            pos--
            continue
        }

        pattern[pos]++
        pos = k // 右端に一気に飛んで良い
    }
}

デッドリー・シンプルですね。

DupPermutationsWithCarrying0      15678811 ns           64 B           1 allocs
DupPermutationsWithCarrying1      22888059 ns           64 B           1 allocs

N 進法表記に変換するやり方

せっかくなのでちょっと特殊解を試します。

[0, 1, ..., n-1] から k 個選ぶ重複順列の列挙は、n 進法表記で k 桁の数字を全て並べる処理と同値です。
なので、10 進法の int をインクリメントしていきながら都度 n 進法に変換することで、重複順列を全て列挙することができます。
順列、組み合わせ、重複組み合わせは全て変則的な n 進法であり、単純な変換は難しい(多分)です。なので、重複順列の場合のみ使えるやり方になってきます。

ちなみに n = 2 として、 2 進法への変換をビット演算で行うと、よくあるビット全探索になります。

combinatorics/dup_perm.go
func DupPermutationsWithBaseConverting0(n, k int, f func([]int)) {
    pattern := make([]int, k)

    for deciNum := 0; deciNum < Pow(n, k); deciNum++ {
        rest := deciNum
        for pos := k - 1; pos >= 0; pos-- {
            pattern[pos] = rest % n
            rest /= n
        }
        f(pattern)
    }
}
combinatorics/util.go
func Pow(base, exponent int) int {
    answer := 1
    for i := 0; i < exponent; i++ {
        answer *= base
    }
    return answer
}
DupPermutationsWithBaseConverting1   232745482 ns           64 B           1 allocs

残念ながら他より 10 倍ぐらいかかっている模様。
やはり重複順列毎に k 桁全部の値を書き込み直しているのが痛いですね。

計測結果まとめ

DupPermutationsRecursive0           2145949059 ns   2020474264 B    30689223 allocs
DupPermutationsRecursive1             23847135 ns           64 B           1 allocs
DupPermutationsWithSlice0             23043210 ns         2080 B           7 allocs
DupPermutationsWithCarrying0          15678811 ns           64 B           1 allocs
DupPermutationsWithCarrying1          22888059 ns           64 B           1 allocs
DupPermutationsWithBaseConverting1   232745482 ns           64 B           1 allocs

まとめ

実装難易度を振り返ってみると、「重複順列 < 重複組合せ <= 組み合わせ << 順列」と言えそうです。
実はここまで難しい順に進んできたことになります。
今までの順列の実装が難しく感じた人は、一旦こっちの重複順列とかの実装を読んだ方が良いかもしれませんね。

私はこの後、自分用の競プロライブラリとして、再帰を用いたやつをひと通りまとめておく予定です。(再帰のやり方が一番書きやすく、いざという時に弄りやすそうなので。)
色々実装を追求して計測して比較した後なので、「この実装で良いな」とそこそこ自信を持てるようになりました。大満足です。

TODO: 寄せられた情報によると、フィッシャー–イェーツのシャッフルについて調べることで、配列の中身をスワップしながら爆速で順列を列挙する方法が出てくるらしい。そのうち詳しく調べたいところ。

おわり。

ikngtty
580日ぐらい無職やりました。社会人リハビリ中。
http://ikngtty.hatenablog.com/
realglobe
「世界のすべてをWebAPI化する」ことを目指す技術ベンチャーです。
https://realglobe.jp
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away