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

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

ただいまの
回答率

88.33%

文字列を1文字変換したパターンの列挙

解決済

回答 3

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 854

miura_bara

score 24

プログラミングを学習中に理解できずに悩んでしまいましたどなたかお願いします。

a, b, c, d のみで構成された文字列 S が与えられます。 文字列 S から 1 文字以下の文字の変更を行ったのち、文字の順番を並び替えることで作れる文字列を、危険なパスワードとします。 ただし、変更後の文字列も a, b, c, d のみで構成されているものとします。 全ての危険なパスワードを辞書順に列挙してください。

制約
1≤|S|≤3
S は a, b, c, d からなる

入力
入力は以下の形式で標準入力から与えられる。
S

出力
危険なパスワードを、一行に一個ずつ、辞書順に列挙せよ。

入力例
ab
出力例
aa
ab
ac
ad
ba
bb
bc
bd
ca
cb
da
db

  • 気になる質問をクリップする

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

質問への追記・修正、ベストアンサー選択の依頼

  • PineMatsu

    2016/04/25 18:28

    辞書順が分からないの?Googleで「辞書順 ソート c」を検索してみたら?

    キャンセル

  • raccy

    2016/04/25 22:20

    Cか、C++か、それが問題だ。

    キャンセル

  • 退会済みユーザー

    2016/04/26 01:48

    こちらの質問が他のユーザから「やってほしいことだけを記載した丸投げの質問」という指摘を受けました
    「質問を編集する」ボタンから編集を行い、調査したこと・試したことを記入していただくと、回答が得られやすくなります。

回答 3

+4

こんにちは。

情報の追加・修正欄では狭いので、こちらから。

プログラミングを学習中に理解できずに悩んでしまいましたどなたかお願いします。

何を「お願い」したいのか、整理された方がよいと思います。
プログラムを教えて欲しい、アルゴリズムを教えてほしいでは「丸投げ」になります。
どこが分からないのか、整理下さい。

ところで、そもそも問題文がかなり曖昧です。
|S|の意味を記載下さい。文字列Sの文字数のような印象ですが、その通りですか?

入力は以下の形式で標準入力から与えられる。 


入力例 
ab 

Mはどこに行ったのでしょうか?

出力 
S に M 回操作を行って得られる文字列を出力せよ。

1回の操作がどのような操作か未定義です。

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2016/04/25 17:47

    すみません。プログラミング初心者のためプログラム自体を教えていただければと思います。
    また、問題文を修正しました。よろしくお願いいたします。

    キャンセル

  • 2016/04/25 18:08

    初心者かどうかに関係なく、丸投げ質問はここでは非推奨です。
    質問を組み立てるスキルは技術者にとって必須スキルです。そこをなおざりにしてはいけません。

    https://teratail.com/help/avoid-asking
    --- 推奨していない質問 ---
    コードをください・デバッグしてください等の丸投げの質問
    何かを作りたいのでコードを書いてほしい、学校の課題を解いてほしい等の質問は、具体的にプログラミングで困っている質問ではないと考え、推奨していません。
    問題や質問は実際に調査や作業に取り組み、具体的なところで生まれると考えるためです。
    まずは実際に作業に取り組み、つまづいたところで投稿をしてみてください。
    ----------------------------

    ところで、初心者がチャレンジするには難易度が高すぎる問題かも知れません。
    見当も付かないのでしたら、もう少し初心者向けの問題に挑戦されることをお薦めします。
    学校の課題でしたら先生に状況を説明して噛み砕いて貰った方がmiura_baraさんのためになると思います。

    厳しいことを書きましたが、この道へ進まれたと言うことは、好きで選ばれた道と思います。頑張って下さい。

    キャンセル

+3

たぶん授業か何かの課題だと思いますが、こういうのは自分で考えないと、身につかないと思うのでヒントだけ。

Sは1文字から3文字までで、文字はa,b,c,dの4つでしょ。
どう求めるかですが、まず辞書順というのは、最後の出力の話なので検討は別で行います。

やり方の一つとして、入力された文字列の「文字数」から作ることのできる「全文字列」を列挙して、変更の条件に合うものだけ抜き出す方法が考えられます。(あわないものを削除するのでも同じこと)

条件というのは「変更文字が1文字以下」ということです。つまり、2文字なら2文字のうち少なくとも1文字は含まれていることが条件、3文字なら少なくともそのうちの2文字が含まれていることが条件になります。

問題文がわかりにくければわかるように言い換えてみればいいのです。

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2016/04/25 17:46 編集

    すみません。プログラミング初心者のためプログラム自体を教えていただければと思います。
    また、問題文を修正しました。よろしくお願いいたします。

    キャンセル

  • 2016/04/25 18:13

    Chironianさんと同じ意見です。
    「コードを書いてみたのですが動きません。助けてください」くらいならまだ答えることができますが。
    厳しく言うようですが、安易に回答に飛びつくくらいならプログラマーになることは諦めたほうがいい。そのほうが今より幸せになれると思うよ。

    キャンセル

checkベストアンサー

0

文字列の長さが2の場合で考えます。

2文字で構成される文字列の組み合わせは 4 ** 2 (= 16) 通りです。
0 .. 15 の数字に "aa", "ab", .. を割り当てることにします。(辞書順になる)
0 .. 15 の数字を 4 進数で表現したら、 0 -> a, 1 -> b, 2 -> c, 3 -> d に置換すれば、番号に相当する文字列を得ることができます。
00 -> aa
01 -> ab
02 -> ac
03 -> ad
...
33 -> dd

文字列が与えられたとき、[a の出現回数、b の出現回数, c の出現回数, d の出現回数] を得る処理を作成します。
2 つの文字列があたえられた時、それぞれの [a の出現回数、b の出現回数, c の出現回数, d の出現回数] を計算してから
対応する要素毎に引き算をすると [a の出現回数の変化, b の出現回数の変化, d の出現回数の変化, d の出現回数の変化]
を得ることができます。
これが [-1, 1, 0 , 0] のような場合は a を b にしたのだということがわかります。
このようにして 2 つも文字列が 1 文字お置換しただけの関係かをしらべることができます。

以上のことを踏まえ、ruby で記述してみたのが ↓です。
先頭にある S を変更してから走らせることで、回答を得られます。

# S = 'a'.freeze  # 入力文字列を設定する
S = 'ab'.freeze  # 入力文字列を設定する
#S = 'dd'.freeze  # 入力文字列を設定する
# S = 'abc'.freeze  # 入力文字列を設定する

S_split = S.tr('abcd', '0123').split('').freeze
S_counts = '0123'.split('').map { |x| S_split.find_all { |y| x == y }.size }.freeze
DIFFS = [-1, 0, 0, 1].freeze
FORMAT = "%0#{S.length}d".freeze

# S から1文字以下の文字を変更して順番をかえたものであるかを調べる
def checked(s)
  split = s.split('')
  # [a の出現回数, b の出現回数, c の出現回数, d の出現回数] の配列を得る
  counts = '0123'.split('').map { |x| split.find_all { |y| x == y }.size }
  # 文字のい入れ替えがないなら、 true を返す
  return true if S_counts == counts
  # [a の出現回数の変化, b の出現回数の変化, c の出現回数の変化, d の出現回数の変化] を得る
  diffs = (0..counts.size - 1).map { |i| S_counts[i] - counts[i] }
  # 一文字も入れ替えになっているなら true を返す
  diffs.sort == DIFFS
end

if S.length == 1
  'abcd'.split('').map { |x| puts "#{x}" }
else
  # S の長さが 2 なら 00 .. 15 までループする。
  # 00 は "aa", 01 = 'ab', .... も対応させる。
  # (数字を 4 進数で表記して、0 -> a, 1 -> b, 2 -> c, 3 -> d に対応をさせる)
  (0..(4 ** S.length - 1)).each do |x|
    s = format(FORMAT, x.to_s(4).to_i)
    puts s.tr('0123', 'abcd') if checked(s)
  end
end


実行結果

S = "a" の場合
a
b
c
d

S = "ab" の場合
aa
ab
ac
ad
ba
bb
bc
bd
ca
cb
da
db

S = "dd" の場合
ad
bd
cd
da
db
dc
dd

ruby が分かるなら、これを C/CLL に書き換えるとよいと思います。
rby がからないなら、考え方を C/C++ で書き下せばよいとおもいます。
(上の考えは、計算量の観点では問題があります。
是非 もっとよい考え方をみつけて、それをプログラムに落としてみてください)

投稿

編集

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

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

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

関連した質問

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