質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.37%

  • Go

    670questions

    Go(golang)は、Googleで開発されたオープンソースのプログラミング言語です。

  • アルゴリズム

    533questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

  • 再帰

    36questions

    情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。

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

解決済

回答 4

投稿

  • 評価
  • クリップ 0
  • VIEW 1,654

xa20256

score 1

前提・実現したいこと

所定の文字全てを重複ありの総当たりで出力するプログラムを書きたいです(パスワードのブルートフォースアタックを行うイメージ)。
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
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 4

checkベストアンサー

+1

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

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

 問題点

 main関数

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

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

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

 pow?

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

powは削除しましょう。

 修正案

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

 あるべきmain関数

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

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

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

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

だけになるでしょう。

 getPasswordCandidate

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

 終了条件

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

getPasswordCandidateの終了条件は、”引数countが0の時”になります。
この時、引数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"から1文字取り出してgetPasswordCandidateを呼び出せばよいでしょう。
この時、引数countには、元のcountから1引いた数を渡してやります。

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

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

 リファクタリング

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/01/30 16:26

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

    キャンセル

+1

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))
}

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

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

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

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に収まる文字セット前提です。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/01/23 00:43 編集

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

    キャンセル

0

純粋にアルゴリズムから考えましょう。
文字の集合 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, ....
となります。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.37%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

同じタグがついた質問を見る

  • Go

    670questions

    Go(golang)は、Googleで開発されたオープンソースのプログラミング言語です。

  • アルゴリズム

    533questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

  • 再帰

    36questions

    情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。