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

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

新規登録して質問してみよう
ただいま回答率
85.50%
C#

C#はマルチパラダイムプログラミング言語の1つで、命令形・宣言型・関数型・ジェネリック型・コンポーネント指向・オブジェクティブ指向のプログラミング開発すべてに対応しています。

ソート

複数のデータを、順序性に従って並べ替えること。 データ処理を行う際に頻繁に用いられ、多くのアルゴリズムが存在します。速度、容量、複雑さなどに違いがあり、高速性に特化したものにクイックソートがあります。

配列

配列は、各データの要素(値または変数)が連続的に並べられたデータ構造です。各配列は添え字(INDEX)で識別されています。

Q&A

3回答

2062閲覧

配列復元のアルゴリズム

opeeeen

総合スコア12

C#

C#はマルチパラダイムプログラミング言語の1つで、命令形・宣言型・関数型・ジェネリック型・コンポーネント指向・オブジェクティブ指向のプログラミング開発すべてに対応しています。

ソート

複数のデータを、順序性に従って並べ替えること。 データ処理を行う際に頻繁に用いられ、多くのアルゴリズムが存在します。速度、容量、複雑さなどに違いがあり、高速性に特化したものにクイックソートがあります。

配列

配列は、各データの要素(値または変数)が連続的に並べられたデータ構造です。各配列は添え字(INDEX)で識別されています。

0グッド

2クリップ

投稿2015/03/07 04:07

お世話になります。

趣味用のプログラムを書いていてわからないことがでてきたので、質問させて頂きます。

A-Zのアルファベットを3つずつ使った未知な26×3文字の環状の配列があるとします。
ここで、各アルファベットに対してそれの次のインデックスのアルファベット3種類がわかっているとして、
長くても1時間程度で元の配列を復元するアルゴリズムはありますか?

よろしくお願いします。

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

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答3

0

おそらく問題の意図は、簡単化すると
例えば,AEABCDEDBC
というA-Eのアルファベットをそれぞれ2つ用いてできた循環配列の各アフファベットの次の文字は
A: B, E
B: C, C
C: A, D
D: B, E
E: A, D
となっており、これを基に元の配列「AEABCDEDBC」を復元するアルゴリズムがあるかどうかという問題だと思います。(違っていたらすみません)

質問は1時間程度て復元するアルゴリズムが存在するか?
というものですが、まずは情報の形状を変換した際に,そもそも可逆性があるのかを考えなければなりません。

例で出した問題では
A: [B, E], B: [C, C], C: [A, D], D: [B, E], E: [A, D]
が配列復元の情報源となりますが,手作業で復元を試みると

AーBーCーAーEーDーBーCーDーE ○1
| | \E×
| \DーBーCーAーEーDーE ○2
| \EーAーEーDーBーC ○3
| \DーBーCーAーE ○4
\EーAーBーCーDーBーC ×
| \EーDーBーC ○5
\DーBーCーAーBーCーDーE ○6
| \DーEーAーBーC ○7
\EーAーBーCーDーBーC ○8

となり,8通り,正確には循環配列なので1=7, 2=8, 3=6, 4=5であり4通りの循環配列ができてしまいます。

したがって元の配列を復元することは一般的に不可能で,アルゴリズムも存在しないと思われます.(いくつかの候補を列挙することは可能ではあります.また,例えば「AABBCCDDEE」や「ABCDEEDCBA」という循環配列だと一意に決まります.)

しかし,以前考えたことがあるような問題ですごく既視感がありますね...
ゲノム解析や動的計画法と関連するようなものだと思うので調べてみると良いかもしれません

投稿2015/03/07 15:49

編集2015/03/07 16:35
YasuhiroMitsuno

総合スコア13

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

opeeeen

2015/03/08 03:50

ありがとうございます。 わかりにくい質問になってしまい申し訳ありません。問題はYasuhiroMitsuno さんがおっしゃるとおりです。 1つでも見つける方法があるといいのですが。 一応アルゴリズムの本には目を通したのですがちゃんと理解できてないのでもう少し動的計画法について調べてみます。
guest

0

環状と言うのはキュー(先頭と末尾がくっついてる)のようなものだと思いますが違いますか?
あと、bigfatratさんの質問に追記します。
・元の配列と言うのはどういったものなのでしょうか?

投稿2015/03/07 10:30

編集2015/03/07 10:36
cateye

総合スコア6851

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

アルゴリズムは必要ないと思うのですが、念のため

前提条件をはっきりさせたいのですが・・・

26×3文字の環状の配列があるとします

26個のデータがあると言う事でしょうか?
それとも78個でしょうか?

環状と言うことは 日⇒月⇒火⇒水⇒木⇒金⇒土⇒日⇒月 のように延々と続くの意味でしょうか?

次のインデックスのアルファベット3種類

アルファベット三種類と言うのはセットなのでしょうか?

元の配列を復元する

元の、と言う事は現状はランダムに並び替えられている前提で良いのでしょうか?

投稿2015/03/07 10:15

編集2015/03/07 10:16
bigfatrat

総合スコア187

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

まだベストアンサーが選ばれていません

会員登録して回答してみよう

アカウントをお持ちの方は

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

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問