Перестановки для цифр, представленных номером телефона

Question

У меня собеседование через 2 дня, и мне очень трудно найти решение для этого вопроса: Я хочу ... для любого номера телефона ... программа должна распечатать все возможные строки, которые она представляет. Например,. 2 в числе можно заменить на «а» или «b» или «с», 3 на «d», «e», «f» и т. Д. Таким образом, сколько возможных перестановок может быть сформировано из номер телефона Я не хочу, чтобы кто-нибудь писал для него код ... хороший алгоритм или psuedocode был бы великолепен.

Спасибо

Answer 1

Это популярная таблица соответствия:

d = { '2': "ABC",
'3': "DEF",
'4': "GHI",
'5': "JKL",
'6': "MNO",
'7': "PQRS",
'8': "TUV",
'9': "WXYZ",
}

Учитывая этот или любой другой d (исполняемый) псевдокод для преобразования строки цифр во все возможные строки букв:

def digstolets(digs):
  if len(digs) == 0:
    yield ''
    return
  first, rest = digs[0], digs[1:]
  if first not in d:
    for x in digstolets(rest): yield first + x
    return
  else:
    for x in d[first]:
      for y in digstolets(rest): yield x + y

настраивается в зависимости от того, что вы хотите сделать для символов во входной строке, которые не включены между 2 и 9 (эта версия просто повторяет их! -).

Например,

print list(digstolets('1234'))

в этой версии испускает

['1ADG', '1ADH', '1ADI', '1AEG', '1AEH', '1AEI', '1AFG', '1AFH', '1AFI', 
 '1BDG', '1BDH', '1BDI', '1BEG', '1BEH', '1BEI', '1BFG', '1BFH', '1BFI',
 '1CDG', '1CDH', '1CDI', '1CEG', '1CEH', '1CEI', '1CFG', '1CFH', '1CFI']

Редактировать : ОП просит дополнительных объяснений, вот попытка. Функция digstolets (цифры в буквы) принимает строку цифр digs и возвращает последовательность строк символов, которые могут быть буквами или «не цифрами». 0 и 1 здесь считаются нецифровыми, потому что они не расширяются в буквы, как пробелы и знаки препинания - только цифры 2 до 9 включают расширение до букв (три варианта в каждой в большинстве случаев четыре в двух случаях, поскольку 7 может расширяться до любого из PQRS, а 9 может расширяться до любого из WXYZ).

Во-первых, базовый случай: если ничего не осталось (строка digs пуста), единственный возможный результат - пустая строка, и все, этот рекурсивный вызов завершен, завершен, капут.

Если digs не пусто, его можно разбить на «голову», первый символ и «хвост», все остальные (0 или более символов после первого).

«Голова» либо остается на выходе, если она не является цифрой; или расширяется до любой из трех или четырех возможностей, если это цифра. В любом случае, одно, три или четыре возможных расширения головы должны быть объединены с каждым возможным расширением хвоста - откуда рекурсивный вызов, чтобы получить все возможные расширения хвоста (поэтому мы зациклимся на всех возможных расширение хвоста и получение каждого из одного, трех или четырех возможных расширений головы, соединенных с каждым возможным расширением хвоста). А потом, еще раз, вот и все, ребята.

Я не знаю, как выразить это в терминах, которые являются более элементарными - если ОП ЭТО все еще теряется после ЭТОГО, я могу только рекомендовать серьезный, полный обзор всего, что касается рекурсии. Удаление рекурсии в пользу явно поддерживаемого стека не может упростить эту концептуальную экспозицию - в зависимости от используемого языка (было бы приятно услышать о том, с какими языками OP полностью удобен!), Удаление рекурсии может быть важной оптимизацией, но это никогда не концептуальное упрощение ...! -)

Answer 2

Другая версия на Java.

Сначала он выбирает массивы символов на основе каждой цифры телефонного номера. Затем, используя рекурсию, он генерирует все возможные перестановки.

public class PhonePermutations {
    public static void main(String[] args) {
        char[][] letters = 
            {{'0'},{'1'},{'A','B','C'},{'D','E','F'},{'G','H','I'},{'J','K','L'}, 
            {'M','N','O'},{'P','Q','R','S'},{'T','U','V'},{'W','X','Y','Z'}};
        String n = "1234";
        char[][] sel = new char[n.length()][];
        for (int i = 0; i < n.length(); i++) {
            int digit = Integer.parseInt("" +n.charAt(i));
            sel[i] = letters[digit];
        }
        permutations(sel, 0, "");
    }

    public static void permutations(char[][] symbols, int n,  String s) {
        if (n == symbols.length) {
            System.out.println(s);
            return;
        }
        for (int i = 0; i < symbols[n].length; i ++) {
            permutations(symbols, n+1, s + symbols[n][i]);
        }
    }
}

Answer 3

Если бы меня об этом спросили в интервью, я бы начал с того, что решил проблему. Какие проблемы нужно решить?

Во-первых, вам нужно сопоставить число с набором букв. Некоторые числа будут отображаться на разные цифры букв. Итак, начните с выяснения, как хранить эти данные. По сути, вы хотите карту числа в набор букв.

Как только вы окажетесь там, сделайте проще, как бы вы сгенерировали все "слова" для однозначного числа? В основном, как перебрать коллекцию, которая сопоставлена ​​с данным числом. А сколько там возможностей?

Хорошо, теперь следующий шаг - у вас есть два числа и вы хотите сгенерировать все слова. Как бы вы это сделали, если бы собирались сделать это вручную? Вы начнете с первой буквы для первого числа и с первой буквы для второго числа. Затем перейдите к следующей букве для второго числа, оставив первую букву для первого и т. Д. Думайте об этом как о числах (в основном это индексы в наборах для двух чисел, каждое из которых отображается на 3 буквы):

00,01,02,10,11,12,20,21,22

Так как бы вы сгенерировали эту последовательность чисел в коде?

Как только вы сможете это сделать, перевод кода в код должен быть тривиальным.

Удачи!

Answer 4

Вот что я придумал:

import java.util.*;

public class PhoneMmemonics {

    /**
     * Mapping between a digit and the characters it represents
     */
    private static Map<Character,List<Character>> numberToCharacters = new HashMap<Character,List<Character>>();

    static {
        numberToCharacters.put('0',new ArrayList<Character>(Arrays.asList('0')));
        numberToCharacters.put('1',new ArrayList<Character>(Arrays.asList('1')));
        numberToCharacters.put('2',new ArrayList<Character>(Arrays.asList('A','B','C')));
        numberToCharacters.put('3',new ArrayList<Character>(Arrays.asList('D','E','F')));
        numberToCharacters.put('4',new ArrayList<Character>(Arrays.asList('G','H','I')));
        numberToCharacters.put('5',new ArrayList<Character>(Arrays.asList('J','K','L')));
        numberToCharacters.put('6',new ArrayList<Character>(Arrays.asList('M','N','O')));
        numberToCharacters.put('7',new ArrayList<Character>(Arrays.asList('P','Q','R')));
        numberToCharacters.put('8',new ArrayList<Character>(Arrays.asList('T','U','V')));
        numberToCharacters.put('9',new ArrayList<Character>(Arrays.asList('W','X','Y','Z')));
    }

    /**
     * Generates a list of all the mmemonics that can exists for the number
     * @param phoneNumber
     * @return
     */
    public static List<String> getMmemonics(int phoneNumber) {

        // prepare results
        StringBuilder stringBuffer = new StringBuilder();
        List<String> results = new ArrayList<String>();

        // generate all the mmenonics
        generateMmemonics(Integer.toString(phoneNumber), stringBuffer, results);

        // return results
        return results;
    }

    /**
     * Recursive helper method to generate all mmemonics
     * 
     * @param partialPhoneNumber Numbers in the phone number that haven't converted to characters yet
     * @param partialMmemonic The partial word that we have come up with so far
     * @param results total list of all results of complete mmemonics
     */
    private static void generateMmemonics(String partialPhoneNumber, StringBuilder partialMmemonic, List<String> results) {

        // are we there yet?
        if (partialPhoneNumber.length() == 0) {

                   //Printing the pnemmonics
                   //System.out.println(partialMmemonic.toString());

            // base case: so add the mmemonic is complete
            results.add(partialMmemonic.toString());
            return;
        }

        // prepare variables for recursion
        int currentPartialLength = partialMmemonic.length();
        char firstNumber = partialPhoneNumber.charAt(0);
        String remainingNumbers = partialPhoneNumber.substring(1);

        // for each character that the single number represents
        for(Character singleCharacter : numberToCharacters.get(firstNumber)) {

            // append single character to our partial mmemonic so far
            // and recurse down with the remaining characters
            partialMmemonic.setLength(currentPartialLength);
            generateMmemonics(remainingNumbers, partialMmemonic.append(singleCharacter), results);
        }
    }
}

Answer 5

Это проблема подсчета, поэтому обычно она помогает найти решение для более мелкой проблемы, а затем подумайте, как она распространяется на ваш общий случай.

Если бы у вас был 1 значный номер телефона, сколько было бы возможностей? Что если бы у вас было 2 цифр? Как вы переходили от одного к другому, и могли бы вы найти способ решить его для n цифр?

Answer 6

C программа:

char *str[] = {"0", "1", "2abc", "3def", "4ghi", "5jkl", "6mno", "7pqrs", "8tuv", "9wxyz"};

const char number[]="2061234569";

char printstr[15];

int len;

printph(int index)
{

     int i;
     int n;
     if (index == len)
     {
        printf("\n");
        printstr[len] = '\0';
        printf("%s\n", printstr);
        return;
     }

     n =number[index] - '0';
     for(i = 0; i < strlen(str[n]); i++)
     {
        printstr[index] = str[n][i];
        printph(index +1);
     }
}

Звоните

  printph(0); 

Answer 7

#include <sstream>
#include <map>
#include <vector>

map< int, string> keyMap;

void MakeCombinations( string first, string joinThis , vector<string>& eachResult )
{
    if( !first.size() )
        return;

    int length = joinThis.length();
    vector<string> result;

    while( length )
    {
        string each;
        char firstCharacter = first.at(0);
        each =  firstCharacter;
        each += joinThis[length -1];
        length--;

        result.push_back(each);     
    }

    first = first.substr(1);

    vector<string>::iterator begin = result.begin();    
    vector<string>::iterator end = result.end();
    while( begin != end)
    {
        eachResult.push_back( *begin);
        begin++;
    }

    return MakeCombinations( first, joinThis, eachResult);
}


void ProduceCombinations( int inNumber, vector<string>& result)
{
    vector<string> inputUnits;

    vector<string> finalres;

    int number = inNumber;
    while( number )
    {
        int lastdigit ;

        lastdigit = number % 10;
        number = number/10;
        inputUnits.push_back( keyMap[lastdigit]);
    }

    if( inputUnits.size() == 2)
    {
        MakeCombinations(inputUnits[0], inputUnits[1], result);
    }
    else if ( inputUnits.size() > 2 )
    {
        MakeCombinations( inputUnits[0] , inputUnits[1], result);

        vector<string>::iterator begin = inputUnits.begin();    
        vector<string>::iterator end = inputUnits.end();


        begin += 2;
        while(  begin != end )
        {
            vector<string> intermediate = result;
            vector<string>::iterator ibegin = intermediate.begin(); 
            vector<string>::iterator iend = intermediate.end(); 

            while( ibegin != iend)
            {
                MakeCombinations( *ibegin , *begin, result);
                //resultbegin =  
                ibegin++; 
            }
            begin++;            
        }
    }
    else
    {

    }

    return;
}

int _tmain(int argc, _TCHAR* argv[])
{
    keyMap[1] = "";
    keyMap[2] = "abc";
    keyMap[3] = "def";
    keyMap[4] = "ghi";
    keyMap[5] = "jkl";
    keyMap[6] = "mno";
    keyMap[7] = "pqrs";
    keyMap[8] = "tuv";
    keyMap[9] = "wxyz";
    keyMap[0] = "";

    string  inputStr;
    getline(cin, inputStr);

    int number = 0;

    int length = inputStr.length();

    int tens = 1;
    while( length )
    {
        number += tens*(inputStr[length -1] - '0');
        length--;
        tens *= 10;
    }

    vector<string> r;
    ProduceCombinations(number, r);

    cout << "[" ;

    vector<string>::iterator begin = r.begin(); 
    vector<string>::iterator end = r.end();

    while ( begin != end)
    {
        cout << *begin << "," ;
        begin++;
    }

    cout << "]" ;

    return 0;
}

Answer 8

Похоже, что ОП запрашивает реализацию, так как он пытается понять псевдокод выше. Возможно, этот Tcl скрипт поможет:

array set d {
    2 {a b c}
    3 {d e f} 
    4 {g h i}
    5 {j k l}
    6 {m n o}
    7 {p q r s}
    8 {t u v}
    9 {w x y z}
}

proc digstolets {digits} {
    global d

    set l [list]
    if {[string length $digits] == 0} {
        return $l
    }

    set first [string index $digits 0]
    catch {set first $d($first)}

    if {[string length $digits] == 1} {
        return $first
    }

    set res [digstolets [string range $digits 1 end]]
    foreach x $first {
        foreach y $res {
            lappend l $x$y
        }
    }

    return $l
}

puts [digstolets "1234"]

Answer 9

Вопрос, который мне приходит в голову, это вопрос о том, какими должны быть 0 и 1 в такой системе? В противном случае вы можете просто рекурсивно пройтись по буквам для каждого значения в диапазоне 2–9, чтобы простым методом перебора всех значений набрать грубую силу.

Предполагая нормальную длину телефонного номера в Северной Америке и игнорируя изначально специальные коды города, также возникает вопрос о том, сколько цифр представляют 4 значения вместо 3, так как 7 и 9 имеют тенденцию получать эти часто неиспользуемые буквы Q и Z, поскольку счетчик может варьироваться от 3 ^ 10 = 59 049 до 4 ^ 10 = 1 048 576. Последний - 1024 в квадрате, я только что заметил.

Answer 10

Используйте рекурсию и хорошую структуру данных для хранения возможных символов. Поскольку мы говорим числами, массив массив будет работать.

char [] [] toChar = {{'0'}, {'1'}, {'2', 'A', 'B', 'C'}, ..., {'9', «W», «X». 'Y'}};

Обратите внимание, что i-й массив в этом массиве массивов содержит символы, соответствующие i-й кнопке на телефоне. То есть tochar [2] [0] - это «2», tochar [2] [1] - это «A» и т. Д.

Рекурсивная функция примет индекс в качестве параметра. Он будет иметь цикл for, который выполняет итерацию по заменяющим символам, заменяя символ по этому индексу на один из массива. Если длина равна длине входной строки, она выводит строку.

В Java или C # вы хотели бы использовать строковый буфер для хранения изменяющейся строки.

function recur(index)
    if (index == input.length) output stringbuffer
    else
        for (i = 0; i < tochar[input[index]].length; i++)
             stringbuffer[index] = tochar[input[index]][i]
             recur(index + 1)