重複ありの総当たりを再帰処理で取得する方法がわからない

Question

###前提・実現したいこと

所定の文字全てを重複ありの総当たりで出力するプログラムを書きたいです（パスワードのブルートフォースアタックを行うイメージ）。
for文を使ったロジックは理解していますが、必要な桁数が増えるたびにfor文を書き加えなければならないため再帰呼び出しを使い柔軟な実装にしたいと考えています。

"abc" 3つの文字列を使う場合下記のような結果を期待しています。

a
b
c
aa
ab
ac
ba
bb
bc
ca
cb
cc
aaa
aab
aac

###発生している問題・エラーメッセージ

再帰のロジックがわかりません。
どのようなコードになるか2,3日考えてみましたが頭がこんがらがってしまいます。
恐らく下記コードの★★★部分のブロックのロジックが正しくないのだろうとは思っています。

どなたかご教授頂けないでしょうか……。

###該当のソースコード

func pow(n, a int) int {
	if a == 0 {
		return 1
	}
	x := n
	for i := 1; i < a; i++ {
		n = n * x
	}
	return n
}

func getPasswordCandidate(ss string, count int) string {
	char := "abcde"
	if count < len(char) { // 終了条件
		return ss + string(char[count])
	}
	for i := 0; ; i++ { //★★★
		if pow(len(char), i) > count {
			return getPasswordCandidate(ss+string(char[count/len(char)-1]), count-pow(len(char), i-1))
		}
	}
}

func main() {
	for i := 0; i <= 16; i++ {
		fmt.Println(getPasswordCandidate("", i))
	}
}

上記コードの実行結果

a
b
c
d
e
aa
ab
ac
ad
ae
baa
bab
bac
bad
bae
cbaa
cbab

Answer 1

注意：文章がぶっきらぼうですが丁寧に書く能力がないだけですので気にしないでくださいね。

いろいろ間違っています。
とりあえず、main関数を見て見ましょう。

問題点

main関数

func main() {
    for i := 0; i <= 16; i++ {
        fmt.Println(getPasswordCandidate("", i))
    }
}

iが０から１６になるまで繰り返していますね。
iの値に応じてfmt.Printlnを呼び出していますが、ソースコード全体を見ても、fmt.Printlnを呼び出しているのはここだけです。

つまり、このループを見るだけで、このプログラムはたかだか１７行しか出力しないことがわかります。
この時点で、すべての組み合わせを出力できないことになります。

pow?

おそらく組み合わせの個数を求めるためにpow関数があるのでしょうが、そもそもpowがある時点で間違いです。
いくつの組み合わせがあるかは結果でしかありません。求める解がいくつあるかを考えて、それを終了条件にしている（？）時点で本末転倒です。

powは削除しましょう。

修正案

では、どうしたらよいでしょう？

あるべきmain関数

main関数から考えていきます。

main関数の仕事は、何個の文字を組み合わせるかを指定してgetPasswordCandidateを呼び出すことです。
main関数では出力する必要なありません。というか出来ません。

となると、main関数はシンプルに

func main() {
	for i := 0; i <= 16; i++ {
		getPasswordCandidate("", i)
	}
}

だけになるでしょう。

getPasswordCandidate

getPasswordCandidateのアルゴリズムはどうなるでしょうか。

終了条件

まず終了条件から考えて行きます。

getPasswordCandidateの終了条件は、”引数countが０の時”になります。
この時、引数ssに、元になる文字"abcde"それぞれを追加した文字列を出力すれば良いです。

出力するのは、ここだけになります。

func getPasswordCandidate(ss string, count int) {
	chars := "abcde"
	if count == 0 { // 終了条件
		for i := 0; i < len(chars); i++ {
			fmt.Println(ss + string(chars[i]))
		}
		return
	}
	/*
            省略
	*/
}

再帰

では、残りの再帰部分を考えて行きます。

元になる文字"abcde"から１文字取り出してgetPasswordCandidateを呼び出せばよいでしょう。
この時、引数countには、元のcountから１引いた数を渡してやります。

	for i := 0; i < len(chars); i++ {
		getPasswordCandidate(ss+string(chars[i]), count-1)
	}

これで動作すると思います。
ちなみに、main関数のループを１６まで指定していると、時間がかかりすぎて全然反応が返ってこないので注意してください。

リファクタリング

そもそも元になる文字"abcde"は引数で渡せばいいと思われます。
そこまではやらないので、気になったらご自分で修正してみてください。

Comments

[xa20256]

アルゴリズムの面で最も詳細に回答頂いたのでベストアンサーとさせて頂きたいと思います。
ありがとうございました。

Answer 2

https://github.com/dieyushi/golang-brutedict

公開されているライブラリでは参考になりませんでしたか？

---

https://docs.python.jp/3/library/itertools.html#itertools.product
pythonでの実装。

https://stackoverflow.com/questions/23412146/create-cartesian-product-in-go
それと同等なgolangの実装。

---

私もそのロジックは理解できませんでしたが、正しそうな結果は得られました。

package main
import "fmt"

func get_strings(ss []string, count int) []string {
    searched := len(ss[len(ss)-1])
    char := "abcde"
    if searched < count-1 {
      ss = get_strings(ss, count-1)
    }
    for _, s := range ss {
        for _, c := range char {
            ss = append(ss, s + string(c))
        }
    }
    if count == 1 {
        ss = ss[1:]
    }
    return ss
}

func main() {
    ans := []string{""}
    fmt.Println(get_strings(ans, 3))
}

Answer 3

純粋にアルゴリズムから考えましょう。
文字の集合 p と最大文字長 n があったとして、出力関数 f は、

1. n == 1 のとき、p の構成要素数分ループして、p を構成する各文字を1つ出力し改行する
2. n >= 2 のとき、まず（n-1)文字までは f(n-1) の出力になり、それに最後の1文字として p を構成する各文字を出力し、改行する

もう少し読み替えると、n == 1 のときは f(0) の出力が「空文字」であれば、2 と 1 は同じにできます。なので、

1. n == 0 のときは何も出力せずに戻る
2. n >= 1 のときは、p の分だけ以下を繰り返す

　f(n-1)を出力し、pの構成要素を出力する

function f(char[] p, int n, bool b) {
  if (n == 0) {
    return;
  } else {
    foreach(char c in p) {
      f(p, n-1, false);
      print c;
      if(b) { println; }
  }
}

ただし、これは動きを考えるとわかりますが、「最長文字列から順に出てくる」という形になっています。
aaaaa, aaaab, aaaac, aaaad, aaaae, aaaba, aaabb, ....
となります。

Answer 4

短い順番に出力するという条件を気にせずに、取り得る組み合わせをどう単純に組み合わせるかを考えますと・・・

現在「生成済みの文字列」に「その後ろにくっつけてもよい文字の候補」および「最長何文字までくっつけた結果を求めたいか」を関数の引数とすれば、生成済みの文字列に候補となる文字を順番にくっつけ、それを印字し、さらにそれより長い文字列の生成のために自分自身を呼び出すという作戦が考え付きます。

abのの箇所の候補としてb以前の文字は含めたくないので再帰呼び出すする際にスライスによって候補を制限するようにしてみました。(リスト1)

リスト1:

package main

import "fmt"

func cr(s, candidates string, limit int) {
  if (len(s) < limit) {
    for i, c := range candidates {
      sNext := s + string(c)
      fmt.Println(sNext)
      cr(sNext, candidates[i:], limit)
    }
  }
}

func main() {
  cr("", "abc", 3)
}

生成した文字列を短い順番に印字するという条件が必要ならもう少しひねらないといけなさそうです。効率を考えないなら「今現在印字しようとしている文字列長の文字列が生成できたら印字する」というように印字タイミングを変更するのはどうでしょうか。(リスト2)

この作戦では論理は単純ですが、例えば長さLの組み合わせを生成・印字する際に長さがL未満の組み合わせを再度生成しなければならないため、効率はよろしくありません。論理を作る訓練としてならさらに効率について工夫してみるとよいと思います。

リスト2:

package main

import "fmt"

func crForLen(s, candidates string, l int) {
  if (len(s) >= l) {
    fmt.Println(s)
  } else {
    for i, c := range candidates {
      crForLen(s + string(c), candidates[i:], l)
    }
  }
}

func crUntilLen(candidates string, limit int) {
  for l := 1; l <= limit; l++ {
    crForLen("", candidates, l)
  }
}

func main() {
  crUntilLen("abc", 3)
}

本件の本質には関係ないと思ったのでruneの配慮はしてません。ASCII文字など単一のbyteに収まる文字セット前提です。

Comments

[KSwordOfHaste]

えと・・・すみませんが、ご質問のコードの問題の指摘は全然できてません。「再帰であたまがこんがらがると」のことでしたので「こんな考え方もあると思う」というコメントです。