アルゴリズムの問題:文字の組み合わせ
https://stackoverflow.com/questions/102468
-
01-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
次のことを行うコードを書こうとしています。
0 ～ 9 の数字を取得し、この数字に 1 つ以上の文字を割り当てます。例えば：
0 = N,
1 = L,
2 = T,
3 = D,
4 = R,
5 = V or F,
6 = B or P,
7 = Z,
8 = H or CH or J,
9 = G
0123 のようなコードがある場合、それをエンコードするのは簡単です。これは明らかにコード NLTD を構成します。5、6、8 などの数字が導入されると、状況は異なります。051 のような数字では、複数の可能性が考えられます。
NVLとNFL
5、6、8 などの複数の桁を含む長い数字では、これがさらに「悪化」することは明らかです。
私は数学がかなり苦手なので、プログラムに大量の数値を入力して、考えられる文字の組み合わせをすべて吐き出すことができる適切な解決策をまだ思いつきません。それで、私はそれを理解できないように見えるので、それについて助けてほしいです。順列と組み合わせに関する情報をいくつか探しましたが、うまくいきませんでした。
ご提案/ヒントをありがとうございます。コードを記述するために必要な言語は PHP ですが、一般的なヒントをいただければ幸いです。
アップデート：
もう少し背景を:(そして素早い対応に感謝します!)
私の質問の背後にある考え方は、人々が覚えておきたい数字を、はるかに覚えやすい単語に簡単に変換できるようにするスクリプトを構築することです。これは「疑似数秘術」と呼ばれることもあります。
スクリプトには、取り除かれた単語のデータベースに対して保持されるすべての可能な組み合わせが表示されるようにしたいと考えています。これらの削除された単語は辞書から抜粋されたもので、質問で言及したすべての文字が削除されています。そうすることで、通常、エンコードされる数値を 1 つ以上のデータベース レコードに簡単に関連付けることができます。そうなると、覚えておきたかった数字を思い出すために使用できる単語のリストができあがります。
解決
数値 -> 文字の割り当てを保持する一般的な構造は、次のような配列です。
// 0 = N, 1 = L, 2 = T, 3 = D, 4 = R, 5 = V or F, 6 = B or P, 7 = Z,
// 8 = H or CH or J, 9 = G
$numberMap = new Array (
0 => new Array("N"),
1 => new Array("L"),
2 => new Array("T"),
3 => new Array("D"),
4 => new Array("R"),
5 => new Array("V", "F"),
6 => new Array("B", "P"),
7 => new Array("Z"),
8 => new Array("H", "CH", "J"),
9 => new Array("G"),
);
次に、少しの再帰ロジックにより、次のような関数が得られます。
function GetEncoding($number) {
$ret = new Array();
for ($i = 0; $i < strlen($number); $i++) {
// We're just translating here, nothing special.
// $var + 0 is a cheap way of forcing a variable to be numeric
$ret[] = $numberMap[$number[$i]+0];
}
}
function PrintEncoding($enc, $string = "") {
// If we're at the end of the line, then print!
if (count($enc) === 0) {
print $string."\n";
return;
}
// Otherwise, soldier on through the possible values.
// Grab the next 'letter' and cycle through the possibilities for it.
foreach ($enc[0] as $letter) {
// And call this function again with it!
PrintEncoding(array_slice($enc, 1), $string.$letter);
}
}
再帰に三声で乾杯！これは次の方法で使用されます。
PrintEncoding(GetEncoding("052384"));
本当に配列として使いたい場合は、出力バッファリングを試して、分割文字列として「 」を使用して展開します。
他のヒント
再帰的に簡単に実行できます。
サイズ n のコード全体を処理するには、最初に n - 1 桁を処理する必要があるという考えです。n-1 桁のすべての答えが得られたら、最後の数字の正しい文字を追加することによって、全体の答えが推定されます。
実際には、数値の可能な翻訳をすべて列挙して調べるよりもはるかに優れた解決策があります。辞書内のすべての単語に対して逆計算を実行し、数字の文字列を別のフィールドに保存するだけです。したがって、マッピングが次の場合:
0 = N,
1 = L,
2 = T,
3 = D,
4 = R,
5 = V or F,
6 = B or P,
7 = Z,
8 = H or CH or J,
9 = G
逆マッピングは次のとおりです。
N = 0,
L = 1,
T = 2,
D = 3,
R = 4,
V = 5,
F = 5,
B = 6,
P = 6,
Z = 7,
H = 8,
J = 8,
G = 9
「c」は削除され、「h」はとにかく 8 に変換されるため、「ch」にはマッピングがないことに注意してください。
次に、辞書の単語内の各文字を繰り返し処理し、一致するものがあれば適切な数字を出力し、一致しない場合は何も実行するだけです。
生成されたすべての数字列をデータベースの別のフィールドとして保存します。何かを調べたいときは、入力された数字に対して単純なクエリを実行するだけでよく、潜在的な単語を何十回 (または何百回、何千回) も検索する必要がありません。
この種の問題は通常、再帰によって解決されます。Ruby では、(手早くて汚い) 解決策の 1 つは次のとおりです。
@values = Hash.new([])
@values["0"] = ["N"]
@values["1"] = ["L"]
@values["2"] = ["T"]
@values["3"] = ["D"]
@values["4"] = ["R"]
@values["5"] = ["V","F"]
@values["6"] = ["B","P"]
@values["7"] = ["Z"]
@values["8"] = ["H","CH","J"]
@values["9"] = ["G"]
def find_valid_combinations(buffer,number)
first_char = number.shift
@values[first_char].each do |key|
if(number.length == 0) then
puts buffer + key
else
find_valid_combinations(buffer + key,number.dup)
end
end
end
find_valid_combinations("",ARGV[0].split(""))
これをコマンドラインから実行すると、次の結果が得られます。
$ ruby r.rb 051
NVL
NFL
これに関連するのは、 ブルートフォース検索 そして 後戻りする
これは Python での再帰的な解決策です。
#!/usr/bin/env/python
import sys
ENCODING = {'0':['N'],
'1':['L'],
'2':['T'],
'3':['D'],
'4':['R'],
'5':['V', 'F'],
'6':['B', 'P'],
'7':['Z'],
'8':['H', 'CH', 'J'],
'9':['G']
}
def decode(str):
if len(str) == 0:
return ''
elif len(str) == 1:
return ENCODING[str]
else:
result = []
for prefix in ENCODING[str[0]]:
result.extend([prefix + suffix for suffix in decode(str[1:])])
return result
if __name__ == '__main__':
print decode(sys.argv[1])
出力例:
$ ./demo 1
['L']
$ ./demo 051
['NVL', 'NFL']
$ ./demo 0518
['NVLH', 'NVLCH', 'NVLJ', 'NFLH', 'NFLCH', 'NFLJ']
次のことをしていただけますか:結果の配列を作成します。値「」を持つ配列内に項目を作成します
たとえば 051 などの数字をループして、それぞれを個別に分析します。
数値間の 1 対 1 の一致が見つかるたびに、結果配列内のすべての項目に正しい値が追加されます。したがって、「」は N になります。
1 対多の一致が見つかるたびに、1 つのオプションで結果配列に新しい行を追加し、もう 1 つのオプションで既存の結果を更新します。したがって、N は NV になり、新しいアイテムが作成されます NF
最後の数字は1対1の一致であるため、結果アレイのアイテムはNVLとNFLになります
結果を生成するには、結果の配列をループしたり、結果を印刷したりします。
させて pn 指定された数値文字列の可能なすべての文字の組み合わせのリストである s 以下 n番目 桁。
次に、次のアルゴリズムが生成します pn+1:
digit = s[n+1];
foreach(letter l that digit maps to)
{
foreach(entry e in p(n))
{
newEntry = append l to e;
add newEntry to p(n+1);
}
}
最初の反復はやや特殊なケースです。-1 は未定義です。pを初期化するだけで済みます0 最初の文字として使用できるすべての文字のリストとして。
したがって、051 の例は次のようになります。
反復 0:
p(0) = {N}
反復 1:
digit = 5
foreach({V, F})
{
foreach(p(0) = {N})
{
newEntry = N + V or N + F
p(1) = {NV, NF}
}
}
反復 2:
digit = 1
foreach({L})
{
foreach(p(1) = {NV, NF})
{
newEntry = NV + L or NF + L
p(2) = {NVL, NFL}
}
}
あなたが望む形式はおそらく次のようなものです:
function combinations( $str ){
$l = len( $str );
$results = array( );
if ($l == 0) { return $results; }
if ($l == 1)
{
foreach( $codes[ $str[0] ] as $code )
{
$results[] = $code;
}
return $results;
}
$cur = $str[0];
$combs = combinations( substr( $str, 1, $l ) );
foreach ($codes[ $cur ] as $code)
{
foreach ($combs as $comb)
{
$results[] = $code.$comb;
}
}
return $results;}
pidgin-php は醜いので、最初に確認してください。基本的な考え方は、[1..n] からの文字列のすべての組み合わせを生成し、str[0] の考えられる各コードをそれらすべての組み合わせの先頭に追加することです。実際のコーディング スキームには多くのあいまいさが存在するため、最悪の場合、文字列の長さによってパフォーマンスが指数関数的に向上することに注意してください。
