알고리즘 문제:문자 조합
https://stackoverflow.com/questions/102468
-
01-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
다음을 수행하는 코드를 작성하려고 합니다.
0부터 9까지의 숫자를 선택하고 이 숫자에 하나 이상의 문자를 할당하십시오.예를 들어:
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이지만 일반적인 힌트는 높이 평가하겠습니다.
업데이트:
추가 배경:(그리고 빠른 답변 정말 감사드립니다!)
내 질문의 기본 아이디어는 사람들이 기억하고 싶은 숫자를 훨씬 더 쉽게 기억할 수 있는 단어로 쉽게 변환하는 데 도움이 되는 스크립트를 작성하는 것입니다.이것은 때때로 "의사 수비학"으로 불립니다.
나는 스크립트가 제거된 단어의 데이터베이스에 대해 유지될 수 있는 모든 가능한 조합을 제공하기를 원합니다.이 제거된 단어는 사전에서 나온 것이며 내 질문에서 언급한 모든 문자가 제거되었습니다.이러한 방식으로 인코딩할 숫자는 일반적으로 하나 이상의 데이터베이스 레코드와 쉽게 관련될 수 있습니다.그리고 그런 일이 발생하면 기억하고 싶은 숫자를 기억하는 데 사용할 수 있는 단어 목록이 완성됩니다.
해결책
숫자 -> 문자 할당을 유지하려는 일반적인 구조는 다음과 유사한 배열입니다.
// 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
참고로 'ch'에 대한 매핑은 없습니다. 'c'는 삭제되고 'h'는 어쨌든 8로 변환되기 때문입니다.
그런 다음 사전 단어의 각 문자를 반복하여 일치하는 항목이 있으면 적절한 숫자를 출력하고, 일치하지 않으면 아무 작업도 수행하지 않기만 하면 됩니다.
생성된 모든 숫자 문자열을 데이터베이스의 다른 필드로 저장합니다.뭔가를 찾고 싶을 때, 잠재적인 단어를 수십 번(또는 수백 번, 수천 번) 검색할 필요 없이 입력한 숫자에 대해 간단한 쿼리를 수행하기만 하면 됩니다.
이런 종류의 문제는 일반적으로 재귀를 통해 해결됩니다.루비에서는 하나의 (빠르고 더러운) 해결책은 다음과 같습니다.
@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이 됩니다.
일대다 일치 항목이 발견될 때마다 한 옵션을 사용하여 결과 배열에 새 행을 추가하고 다른 옵션을 사용하여 기존 결과를 업데이트합니다.따라서 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]에 대해 가능한 각 코드를 추가하는 것입니다.최악의 경우 문자열 길이에 따라 성능이 기하급수적으로 증가한다는 점을 명심하세요. 실제로 코딩 체계에는 많은 모호성이 존재하기 때문입니다.
