Во время собеседования я получил вопрос о создании массива и распечатке всех возможных буквенных комбинаций телефонного номера. Во время интервью я получил шепот от интервьюера о рекурсии и о том, как это невозможно сделать с помощью петель. Очень неестественно для меня получать информацию от другого программиста, я доверял его советам вместо моего собственного обучения и продолжал писать неаккуратный беспорядок рекурсии. Это не так хорошо. До получения информации, поскольку я никогда не сталкивался с этой проблемой, мой мозг вычислял основную воспроизводимую математическую формулу. Прошептав мне под нос: «Я не могу просто умножить на три, некоторые из них на четыре», так как мой разум начал мчаться с короткими часами, думая об одном ответе, когда начинает писать другой. Только в конце недели мне позвонили, чтобы сообщить мне грустные новости. Позже той ночью я решил посмотреть, действительно ли это проблема рекурсии. Оказывается, это не так.
Мое решение, приведенное ниже, написано на PHP, не является рекурсивным, работает с любой длиной ввода, и я даже включил некоторые комментарии, чтобы помочь описать, что означают мои переменные. Это мой официальный и неизменный окончательный ответ на этот вопрос. Я надеюсь, что это поможет кому-то еще в будущем, пожалуйста, не стесняйтесь переводить это на другие языки.
Метод Me включает вычисление общего количества комбинаций и создание буфера, достаточно большого для каждого байта. Длина моего буфера равна длине, которую вы ожидаете получить от работающего рекурсивного алгоритма. Я делаю массив, который содержит группы букв, которые представляют каждое число. Мой метод в первую очередь работает, потому что ваша общая сумма всегда будет делиться на количество букв в текущей группе. Если вы можете представить себе в уме вертикальный список выходных данных этого алгоритма или увидеть список вертикально, а не горизонтально написанный список комбинаций, мой алгоритм начнет обретать смысл. Этот алгоритм позволяет нам циклически проходить через каждый байт сверху вниз, начиная слева, а не горизонтально слева направо, и заполнять каждый байт индивидуально, не требуя рекурсии. Я использую буфер, как будто это байтовый массив для экономии времени и энергии.
НЕРЕКУРСИВНЫЙ, ИТЕРАЦИОННЫЙ PHP
<?php
// Display all possible combinations of letters for each number.
$input = '23456789';
// ====================
if(!isset($input[0]))
die('Nothing to see here!');
$phone_letters = array(
2 => array('a', 'b', 'c'),
3 => array('d', 'e', 'f'),
4 => array('g', 'h', 'i'),
5 => array('j', 'k', 'l'),
6 => array('m', 'n', 'o'),
7 => array('p', 'q', 'r', 's'),
8 => array('t', 'u', 'v'),
9 => array('w', 'x', 'y', 'z')
);
$groups = array();
$combos_total = 1;
$l = strlen($input);
for($i = 0; $i < $l; ++$i) {
$groups[] = $phone_letters[$input[$i]];
$combos_total *= count($phone_letters[$input[$i]]);
}
$count = $combos_total / count($groups[0]);
$combos = array_fill(0, $combos_total, str_repeat(chr(0), strlen($input)));
for(
$group = 0, // Index for the current group of letters.
$groups_count = count($groups), // Total number of letter groups.
$letters = count($groups[0]), // Total number of letters in the current group.
$width = $combos_total, // Number of bytes to repeat the current letter.
$repeat = 1; // Total number of times the group will repeat.
;
) {
for($byte = 0, $width /= $letters, $r = 0; $r < $repeat; ++$r)
for($l = 0; $l < $letters; ++$l)
for($w = 0; $w < $width; ++$w)
$combos[$byte++][$group] = $groups[$group][$l];
if(++$group < $groups_count) {
$repeat *= $letters;
$letters = count($groups[$group]);
}
else
break;
}
// ====================
if(is_array($combos)) {
print_r($combos);
echo 'Total combos:', count($combos), "\n";
}
else
echo 'No combos.', "\n";
echo 'Expected combos: ', $combos_total, "\n";
НЕРЕКУРСИВНЫЙ, НЕИТЕРАТИВНЫЙ, НЕТУФЕР, НЕЗАВИСИМЫЙ РЕЗЬБА, ТОЛЬКО МАТЕМАТИКА + НЕРЕКУРСИВНЫЙ, ИТЕРАЦИОННЫЙ ОБЪЕКТ PHP С ИСПОЛЬЗОВАНИЕМ МНОГОБАЗОВОГО БОЛЬШОГО ENDIAN
Когда я работал над новым домом на днях, я осознал, что могу использовать математику из моей первой функции в сочетании со своими знаниями по основам для обработки всех возможных буквенных комбинаций моего ввода как многомерного числа. .
Мой объект предоставляет функции, необходимые для сохранения предпочтительной комбинации в базе данных, преобразования букв и цифр, если это необходимо, выбора комбинации из любого места в области комбинации с использованием предпочтительной комбинации или байта, и все это очень хорошо работает с многопоточность.
При этом, используя мой объект, я могу предоставить второй ответ, который использует базу, без буфера, без итераций и, самое главное, без рекурсии.
<?php
class phone {
public static $letters = array(
2 => array('a', 'b', 'c'),
3 => array('d', 'e', 'f'),
4 => array('g', 'h', 'i'),
5 => array('j', 'k', 'l'),
6 => array('m', 'n', 'o'),
7 => array('p', 'q', 'r', 's'),
8 => array('t', 'u', 'v'),
9 => array('w', 'x', 'y', 'z')
);
// Convert a letter into its respective number.
public static function letter_number($letter) {
if(!isset($letter[0]) || isset($letter[1]))
return false;
for($i = 2; $i < 10; ++$i)
if(in_array($letter, phone::$letters[$i], true))
return $i;
return false;
}
// Convert letters into their respective numbers.
public static function letters_numbers($letters) {
if(!isset($letters[0]))
return false;
$length = strlen($letters);
$numbers = str_repeat(chr(0), $length);
for($i = 0; $i < $length; ++$i) {
for($j = 2; $j < 10; ++$j) {
if(in_array($letters[$i], phone::$letters[$j], true)) {
$numbers[$i] = $j;
break;
}
}
}
return $numbers;
}
// Calculate the maximum number of combinations that could occur within a particular input size.
public static function combination_size($groups) {
return $groups <= 0 ? false : pow(4, $groups);
}
// Calculate the minimum bytes reqired to store a group using the current input.
public static function combination_bytes($groups) {
if($groups <= 0)
return false;
$size = $groups * 4;
$bytes = 0;
while($groups !== 0) {
$groups >> 8;
++$bytes;
}
return $bytes;
}
public $input = '';
public $input_len = 0;
public $combinations_total = 0;
public $combinations_length = 0;
private $iterations = array();
private $branches = array();
function __construct($number) {
if(!isset($number[0]))
return false;
$this->input = $number;
$input_len = strlen($number);
$combinations_total = 1;
for($i = 0; $i < $input_len; ++$i) {
$combinations_total *= count(phone::$letters[$number[$i]]);
}
$this->input_len = $input_len;
$this->combinations_total = $combinations_total;
$this->combinations_length = $combinations_total * $input_len;
for($i = 0; $i < $input_len; ++$i) {
$this->branches[] = $this->combination_branches($i);
$this->iterations[] = $this->combination_iteration($i);
}
}
// Calculate a particular combination in the combination space and return the details of that combination.
public function combination($combination) {
$position = $combination * $this->input_len;
if($position < 0 || $position >= $this->combinations_length)
return false;
$group = $position % $this->input_len;
$first = $position - $group;
$last = $first + $this->input_len - 1;
$combination = floor(($last + 1) / $this->input_len) - 1;
$bytes = str_repeat(chr(0), $this->input_len);
for($i = 0; $i < $this->input_len; ++$i)
$bytes[$i] = phone::$letters[$this->input[$i]][($combination / $this->branches[$i]) % count(phone::$letters[$this->input[$i]])];
return array(
'combination' => $combination,
'branches' => $this->branches[$group],
'iterations' => $this->iterations[$group],
'first' => $first,
'last' => $last,
'bytes' => $bytes
);
}
// Calculate a particular byte in the combination space and return the details of that byte.
public function combination_position($position) {
if($position < 0 || $position >= $this->combinations_length)
return false;
$group = $position % $this->input_len;
$group_count = count(phone::$letters[$this->input[$group]]);
$first = $position - $group;
$last = $first + $this->input_len - 1;
$combination = floor(($last + 1) / $this->input_len) - 1;
$index = ($combination / $this->branches[$group]) % $group_count;
$bytes = str_repeat(chr(0), $this->input_len);
for($i = 0; $i < $this->input_len; ++$i)
$bytes[$i] = phone::$letters[$this->input[$i]][($combination / $this->branches[$i]) % count(phone::$letters[$this->input[$i]])];
return array(
'position' => $position,
'combination' => $combination - 1,
'group' => $group,
'group_count' => $group_count,
'group_index' => $index,
'number' => $this->input[$group],
'branches' => $this->branches[$group],
'iterations' => $this->iterations[$group],
'first' => $first,
'last' => $last,
'byte' => phone::$letters[$this->input[$group]][$index],
'bytes' => $bytes
);
}
// Convert letters into a combination number using Multi-Base Big Endian.
public function combination_letters($letters) {
if(!isset($letters[$this->input_len - 1]) || isset($letters[$this->input_len]))
return false;
$combination = 0;
for($byte = 0; $byte < $this->input_len; ++$byte) {
$base = count(phone::$letters[$this->input[$byte]]);
$found = false;
for($value = 0; $value < $base; ++$value) {
if($letters[$byte] === phone::$letters[$this->input[$byte]][$value]) {
$combination += $value * $this->branches[$byte];
$found = true;
break;
}
}
if($found === false)
return false;
}
return $combination;
}
// Calculate the number of branches after a particular group.
public function combination_branches($group) {
if($group >= 0 && ++$group < $this->input_len) {
$branches = 1;
for($i = $group; $i < $this->input_len; ++$i)
$branches *= count(phone::$letters[$this->input[$i]]);
return $branches === 1 ? 1 : $branches;
}
elseif($group === $this->input_len)
return 1;
else
return false;
}
// Calculate the number of iterations before a particular group.
public function combination_iteration($group) {
if($group > 0 && $group < $this->input_len) {
$iterations = 1;
for($i = $group - 1; $i >= 0; --$i)
$iterations *= count(phone::$letters[$this->input[$i]]);
return $iterations;
}
elseif($group === 0)
return 1;
else
return false;
}
// Iterations, Outputs array of all combinations using a buffer.
public function combinations() {
$count = $this->combinations_total / count(phone::$letters[$this->input[0]]);
$combinations = array_fill(0, $this->combinations_total, str_repeat(chr(0), $this->input_len));
for(
$group = 0, // Index for the current group of letters.
$groups_count = $this->input_len, // Total number of letter groups.
$letters = count(phone::$letters[$this->input[0]]), // Total number of letters in the current group.
$width = $this->combinations_total, // Number of bytes to repeat the current letter.
$repeat = 1; // Total number of times the group will repeat.
;
) {
for($byte = 0, $width /= $letters, $r = 0; $r < $repeat; ++$r)
for($l = 0; $l < $letters; ++$l)
for($w = 0; $w < $width; ++$w)
$combinations[$byte++][$group] = phone::$letters[$this->input[$group]][$l];
if(++$group < $groups_count) {
$repeat *= $letters;
$letters = count(phone::$letters[$this->input[$group]]);
}
else
break;
}
return $combinations;
}
}
// ====================
$phone = new phone('23456789');
print_r($phone);
//print_r($phone->combinations());
for($i = 0; $i < $phone->combinations_total; ++$i) {
echo $i, ': ', $phone->combination($i)['bytes'], "\n";
}