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

Question

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

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

Comments

[退会済みユーザー]

何かの翻訳ですか？原文を載せたほうが良いです。

[miura_bara]

問題文そのままの原文です。プログラミング初心者のため辞書順に探索する方法がわかりません。よろしくお願いいたします。

[PineMatsu]

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

[raccy]

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

Answer 1

こんにちは。

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

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

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

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

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

S
M
入力例
ab

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

出力

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

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

Comments

[miura_bara]

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

[Chironian]

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

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

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

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

Answer 2

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

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

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

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

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

Comments

[miura_bara]

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

[PineMatsu]

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

Answer 3

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

２文字で構成される文字列の組み合わせは 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++ で書き下せばよいとおもいます。
（上の考えは、計算量の観点では問題があります。
是非 もっとよい考え方をみつけて、それをプログラムに落としてみてください)