algorithm - todas - generar combinaciones con letras
¿Cómo puedo imprimir todas las combinaciones de letras posibles que puede representar un número de teléfono determinado? (30)
Aquí hay uno para el dolor C. Este tampoco es eficiente (de hecho, no creo que lo sea). Pero hay algunos aspectos interesantes.
- Toma un número y lo convierte en una cadena.
- Solo aumenta el número de semilla una vez cada vez para crear la siguiente cadena secuencial
Lo bueno de esto es que no hay un límite real para el tamaño de la cadena (sin límite de caracteres). Esto le permite generar cadenas más y más largas si es necesario solo por esperar.
#include <stdlib.h>
#include <stdio.h>
#define CHARACTER_RANGE 95 // The range of valid password characters
#define CHARACTER_OFFSET 32 // The offset of the first valid character
void main(int argc, char *argv[], char *env[])
{
int i;
long int string;
long int worker;
char *guess; // Current Generation
guess = (char*)malloc(1); // Allocate it so free doesn''t fail
int cur;
for ( string = 0; ; string++ )
{
worker = string;
free(guess);
guess = (char*)malloc((string/CHARACTER_RANGE+1)*sizeof(char)); // Alocate for the number of characters we will need
for ( i = 0; worker > 0 && i < string/CHARACTER_RANGE + 1; i++ ) // Work out the string
{
cur = worker % CHARACTER_RANGE; // Take off the last digit
worker = (worker - cur) / CHARACTER_RANGE; // Advance the digits
cur += CHARACTER_OFFSET;
guess[i] = cur;
}
guess[i+1] = ''/0''; // NULL terminate our string
printf("%s/t%d/n", guess, string);
}
}
Acabo de intentar mi primera entrevista de programación y una de las preguntas fue escribir un programa que, dado un número de teléfono de 7 dígitos, pudiera imprimir todas las combinaciones posibles de letras que cada número pudiera representar.
Una segunda parte de la pregunta fue ¿qué pasaría si este hubiera sido un número internacional de 12 dígitos? ¿Cómo afectaría eso a tu diseño?
No tengo el código que escribí en la entrevista, pero tengo la impresión de que no estaba contento con eso.
¿Cuál es la mejor manera de hacer esto?
En C ++ (recursivo):
string pattern[] = {"0",".,!","ABC","DEF","GHI","JKL","MNO","PQRS","TUV","WXYZ"};
ofstream keyout("keypad.txt");
void print_keypad(char* str, int k, vector<char> patt, int i){
if(str[k] != ''/0'')
{
int x = str[k] - ''0'';
for(int l = 0; l < pattern[x].length(); l++)
{
patt[i] = pattern[x][l];
print_keypad(str, k+1, patt, i+1);
}
keyout << endl;
}
else if(i == k)
{
string st(patt.data());
keyout << st << endl;
return;
}
}
Esta función se puede llamar con ''k'' e ''i'' igual a cero.
Cualquiera que requiera más ilustración para comprender la lógica, puede combinar la técnica de recursión con la siguiente salida:
ADG
ADH
ADI
AEG
AEH
AEI
AFG
AFH
AFI
BDG
BDH
BDI
BEG
BEH
BEI
BFG
BFH
...
En Java usando recursion:
import java.util.LinkedList;
import java.util.List;
public class Main {
// Number-to-letter mappings in order from zero to nine
public static String mappings[][] = {
{"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"}
};
public static void generateCombosHelper(List<String> combos,
String prefix, String remaining) {
// The current digit we are working with
int digit = Integer.parseInt(remaining.substring(0, 1));
if (remaining.length() == 1) {
// We have reached the last digit in the phone number, so add
// all possible prefix-digit combinations to the list
for (int i = 0; i < mappings[digit].length; i++) {
combos.add(prefix + mappings[digit][i]);
}
} else {
// Recursively call this method with each possible new
// prefix and the remaining part of the phone number.
for (int i = 0; i < mappings[digit].length; i++) {
generateCombosHelper(combos, prefix + mappings[digit][i],
remaining.substring(1));
}
}
}
public static List<String> generateCombos(String phoneNumber) {
// This will hold the final list of combinations
List<String> combos = new LinkedList<String>();
// Call the helper method with an empty prefix and the entire
// phone number as the remaining part.
generateCombosHelper(combos, "", phoneNumber);
return combos;
}
public static void main(String[] args) {
String phone = "3456789";
List<String> combos = generateCombos(phone);
for (String s : combos) {
System.out.println(s);
}
}
}
En JavaScript. Una clase CustomCounter se encarga de incrementar los índices. Luego simplemente saca las diferentes combinaciones posibles.
var CustomCounter = function(min, max) {
this.min = min.slice(0)
this.max = max.slice(0)
this.curr = this.min.slice(0)
this.length = this.min.length
}
CustomCounter.prototype.increment = function() {
for (var i = this.length - 1, ii = 0; i >= ii; i--) {
this.curr[i] += 1
if (this.curr[i] > this.max[i]) {
this.curr[i] = 0
} else {
break
}
}
}
CustomCounter.prototype.is_max = function() {
for (var i = 0, ii = this.length; i < ii; ++i) {
if (this.curr[i] !== this.max[i]) {
return false
}
}
return true
}
var PhoneNumber = function(phone_number) {
this.phone_number = phone_number
this.combinations = []
}
PhoneNumber.number_to_combinations = {
1: [''1'']
, 2: [''2'', ''a'', ''b'', ''c'']
, 3: [''3'', ''d'', ''e'', ''f'']
, 4: [''4'', ''g'', ''h'', ''i'']
, 5: [''5'', ''j'', ''k'', ''l'']
, 6: [''6'', ''m'', ''n'', ''o'']
, 7: [''7'', ''p'', ''q'', ''r'', ''s'']
, 8: [''8'', ''t'', ''u'', ''v'']
, 9: [''9'', ''w'', ''x'', ''y'', ''z'']
, 0: [''0'', ''+'']
}
PhoneNumber.prototype.get_combination_by_digit = function(digit) {
return PhoneNumber.number_to_combinations[digit]
}
PhoneNumber.prototype.add_combination_by_indexes = function(indexes) {
var combination = ''''
for (var i = 0, ii = indexes.length; i < ii; ++i) {
var phone_number_digit = this.phone_number[i]
combination += this.get_combination_by_digit(phone_number_digit)[indexes[i]]
}
this.combinations.push(combination)
}
PhoneNumber.prototype.update_combinations = function() {
var min_indexes = []
, max_indexes = []
for (var i = 0, ii = this.phone_number.length; i < ii; ++i) {
var digit = this.phone_number[i]
min_indexes.push(0)
max_indexes.push(this.get_combination_by_digit(digit).length - 1)
}
var c = new CustomCounter(min_indexes, max_indexes)
while(true) {
this.add_combination_by_indexes(c.curr)
c.increment()
if (c.is_max()) {
this.add_combination_by_indexes(c.curr)
break
}
}
}
var phone_number = new PhoneNumber(''120'')
phone_number.update_combinations()
console.log(phone_number.combinations)
En Python, iterativo:
digit_map = {
''2'': ''abc'',
''3'': ''def'',
''4'': ''ghi'',
''5'': ''jkl'',
''6'': ''mno'',
''7'': ''pqrs'',
''8'': ''tuv'',
''9'': ''wxyz'',
}
def word_numbers(input):
input = str(input)
ret = ['''']
for char in input:
letters = digit_map.get(char, '''')
ret = [prefix+letter for prefix in ret for letter in letters]
return ret
ret es una lista de resultados hasta ahora; inicialmente se rellena con un elemento, la cadena vacía. Luego, para cada carácter en la cadena de entrada, busca la lista de letras que coinciden con el dictado definido en la parte superior. Luego reemplaza la lista ret con cada combinación de prefijo existente y posible letra.
En los teclados numéricos, los textos y los números se colocan en la misma tecla. Por ejemplo, 2 tiene "ABC". Si quisiéramos escribir algo comenzando con ''A'' necesitamos teclear la tecla 2 una vez. Si quisiéramos escribir ''B'', presione la tecla 2 dos veces y tres veces para escribir ''C''. A continuación se muestra la imagen de dicho teclado.
teclado http://d2o58evtke57tz.cloudfront.net/wp-content/uploads/phoneKeyboard.png
Dado un teclado como se muestra en el diagrama, y un número de dígitos, haga una lista de todas las palabras que son posibles presionando estos números.
Por ejemplo, si el número de ingreso es 234, las posibles palabras que pueden formarse son (orden alfabético):
Hagamos algunos cálculos primero. ¿Cuántas palabras son posibles con siete dígitos y cada dígito representa n letras? Para el primer dígito tenemos como máximo cuatro opciones, y para cada elección para la primera letra, tenemos como máximo cuatro opciones para el segundo dígito y así sucesivamente. Así que es matemática simple, será O (4 ^ n). Como las teclas 0 y 1 no tienen ningún alfabeto correspondiente y muchos caracteres tienen 3 caracteres, 4 ^ n sería el límite superior del número de palabras y no las palabras mínimas.
Ahora vamos a hacer algunos ejemplos.
Para el número arriba de 234. ¿Ves algún patrón? Sí, notamos que el último carácter siempre es G, H o I, y cuando se restablece su valor de I a G, el dígito de la izquierda se modifica. De manera similar, cada vez que el segundo último alfabeto restablece su valor, el tercer último alfabeto obtiene cambios y así sucesivamente. El primer carácter se reinicia solo una vez cuando hemos generado todas las palabras. Esto se puede ver desde otro extremo también. Es decir, cuando el carácter en la posición i cambia, el carácter en la posición i + 1 pasa por todos los caracteres posibles y crea un efecto de ondulación hasta que llegamos al final. Dado que 0 y 1 no tienen ningún carácter asociado a ellos. deberíamos romper ya que no habrá iteración para estos dígitos.
Tomemos el segundo enfoque, ya que será fácil implementarlo utilizando la recursión. Vamos hasta el final y volvemos uno por uno. Perfecto estado para la recursión. vamos a buscar el caso base. Cuando alcanzamos el último carácter, imprimimos la palabra con todos los caracteres posibles para el último dígito y regresamos. Caso básico simple. Cuando alcanzamos el último carácter, imprimimos la palabra con todos los caracteres posibles para el último dígito y regresamos. Caso de base simple.
A continuación se muestra la implementación en C del enfoque recursivo para imprimir todas las palabras posibles correspondientes a un número de entrada de dígitos. Tenga en cuenta que el número de entrada se representa como una matriz para simplificar el código.
#include <stdio.h>
#include <string.h>
// hashTable[i] stores all characters that correspond to digit i in phone
const char hashTable[10][5] = {"", "", "abc", "def", "ghi", "jkl",
"mno", "pqrs", "tuv", "wxyz"};
// A recursive function to print all possible words that can be obtained
// by input number[] of size n. The output words are one by one stored
// in output[]
void printWordsUtil(int number[], int curr_digit, char output[], int n)
{
// Base case, if current output word is prepared
int i;
if (curr_digit == n)
{
printf("%s ", output);
return ;
}
// Try all 3 possible characters for current digir in number[]
// and recur for remaining digits
for (i=0; i<strlen(hashTable[number[curr_digit]]); i++)
{
output[curr_digit] = hashTable[number[curr_digit]][i];
printWordsUtil(number, curr_digit+1, output, n);
if (number[curr_digit] == 0 || number[curr_digit] == 1)
return;
}
}
// A wrapper over printWordsUtil(). It creates an output array and
// calls printWordsUtil()
void printWords(int number[], int n)
{
char result[n+1];
result[n] =''/0'';
printWordsUtil(number, 0, result, n);
}
//Driver program
int main(void)
{
int number[] = {2, 3, 4};
int n = sizeof(number)/sizeof(number[0]);
printWords(number, n);
return 0;
}
Salida:
adg adh adi aeg aeh aei afg afh afi bdg bdh bdi beg beh bei bfg bfh bfi cdg cdh cdi ceg ceh cei cfg cfh cfi
Complejidad del tiempo:
La complejidad de tiempo del código anterior es O (4 ^ n) donde n es el número de dígitos en el número de entrada.
Referencias:
Es similar a una pregunta llamada combinación de letras de un número de teléfono , aquí está mi solución.
Funciona para un número arbitrario de dígitos, siempre que el resultado no exceda el límite de memoria.
import java.util.HashMap;
public class Solution {
public ArrayList<String> letterCombinations(String digits) {
ArrayList<String> res = new ArrayList<String>();
ArrayList<String> preres = new ArrayList<String>();
res.add("");
for(int i = 0; i < digits.length(); i++) {
String letters = map.get(digits.charAt(i));
if (letters.length() == 0)
continue;
for(String str : res) {
for(int j = 0; j < letters.length(); j++)
preres.add(str + letters.charAt(j));
}
res = preres;
preres = new ArrayList<String>();
}
return res;
}
static final HashMap<Character,String> map = new HashMap<Character,String>(){{
put(''1'', "");
put(''2'',"abc");
put(''3'',"def");
put(''4'',"ghi");
put(''5'',"jkl");
put(''6'',"mno");
put(''7'',"pqrs");
put(''8'',"tuv");
put(''9'',"wxyz");
put(''0'', "");
}} ;
}
No estoy seguro de cómo los números internacionales de 12 dígitos afectan el diseño.
Edición: los números internacionales también serán manejados
Esta versión en C # es razonablemente eficiente y funciona para dígitos no occidentales (como "۱۲۳۴۵۶۷" por ejemplo).
static void Main(string[] args)
{
string phoneNumber = null;
if (1 <= args.Length)
phoneNumber = args[0];
if (string.IsNullOrEmpty(phoneNumber))
{
Console.WriteLine("No phone number supplied.");
return;
}
else
{
Console.WriteLine("Alphabetic phone numbers for /"{0}/":", phoneNumber);
foreach (string phoneNumberText in GetPhoneNumberCombos(phoneNumber))
Console.Write("{0}/t", phoneNumberText);
}
}
public static IEnumerable<string> GetPhoneNumberCombos(string phoneNumber)
{
phoneNumber = RemoveNondigits(phoneNumber);
if (string.IsNullOrEmpty(phoneNumber))
return new List<string>();
char[] combo = new char[phoneNumber.Length];
return GetRemainingPhoneNumberCombos(phoneNumber, combo, 0);
}
private static string RemoveNondigits(string phoneNumber)
{
if (phoneNumber == null)
return null;
StringBuilder sb = new StringBuilder();
foreach (char nextChar in phoneNumber)
if (char.IsDigit(nextChar))
sb.Append(nextChar);
return sb.ToString();
}
private static IEnumerable<string> GetRemainingPhoneNumberCombos(string phoneNumber, char[] combo, int nextDigitIndex)
{
if (combo.Length - 1 == nextDigitIndex)
{
foreach (char nextLetter in phoneNumberAlphaMapping[(int)char.GetNumericValue(phoneNumber[nextDigitIndex])])
{
combo[nextDigitIndex] = nextLetter;
yield return new string(combo);
}
}
else
{
foreach (char nextLetter in phoneNumberAlphaMapping[(int)char.GetNumericValue(phoneNumber[nextDigitIndex])])
{
combo[nextDigitIndex] = nextLetter;
foreach (string result in GetRemainingPhoneNumberCombos(phoneNumber, combo, nextDigitIndex + 1))
yield return result;
}
}
}
private static char[][] phoneNumberAlphaMapping = new char[][]
{
new char[] { ''0'' },
new char[] { ''1'' },
new char[] { ''a'', ''b'', ''c'' },
new char[] { ''d'', ''e'', ''f'' },
new char[] { ''g'', ''h'', ''i'' },
new char[] { ''j'', ''k'', ''l'' },
new char[] { ''m'', ''n'', ''o'' },
new char[] { ''p'', ''q'', ''r'', ''s'' },
new char[] { ''t'', ''u'', ''v'' },
new char[] { ''w'', ''x'', ''y'', ''z'' }
};
Este es el puerto C # de this respuesta.
Código
public class LetterCombinations
{
private static readonly Dictionary<string, string> Representations = new Dictionary<string, string>
{
{"2", "abc" },
{"3", "def" },
{"4", "ghi" },
{"5", "jkl" },
{"6", "mno" },
{"7", "pqrs" },
{"8", "tuv" },
{"9", "wxyz" },
};
public static List<string> FromPhoneNumber(string phoneNumber)
{
var result = new List<string> { string.Empty };
// go through each number in the phone
for (int i = 0; i < phoneNumber.Length; i++)
{
var pre = new List<string>();
foreach (var str in result)
{
var letters = Representations[phoneNumber[i].ToString()];
// go through each representation of the number
for (int j = 0; j < letters.Length; j++)
{
pre.Add(str + letters[j]);
}
}
result = pre;
}
return result;
}
}
Pruebas unitarias
public class UnitTest
{
[TestMethod]
public void One_Digit_Yields_Three_Representations()
{
var sut = "2";
var expected = new List<string>{ "a", "b", "c" };
var actualResults = LetterCombinations.FromPhoneNumber(sut);
CollectionAssert.AreEqual(expected, actualResults);
}
[TestMethod]
public void Two_Digits_Yield_Nine_Representations()
{
var sut = "22";
var expected = new List<string> { "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc" };
var actualResults = LetterCombinations.FromPhoneNumber(sut);
CollectionAssert.AreEqual(expected, actualResults);
}
[TestMethod]
public void Three_Digits_Yield_ThirtyNine_Representations()
{
var sut = "222";
var actualResults = LetterCombinations.FromPhoneNumber(sut);
var possibleCombinations = Math.Pow(3,3); //27
Assert.AreEqual(possibleCombinations, actualResults.Count);
}
}
La solución obvia es una función para asignar un dígito a una lista de teclas y luego una función que generaría las posibles combinaciones:
El primero es obvio, el segundo es más problemático porque tiene alrededor de 3 ^ número de combinaciones de dígitos, lo que puede ser un número muy grande.
Una forma de hacerlo es mirar cada posibilidad de hacer coincidir los dígitos como un dígito en un número (en la base 4) e implementar algo cercano a un contador (saltando sobre algunos casos, ya que generalmente hay menos de 4 letras asignables a un dígito). ).
Las soluciones más obvias serían los bucles anidados o la recursión, que son menos elegantes, pero en mi opinión son válidos.
Otra cosa que debe tenerse cuidado es evitar problemas de escalabilidad (por ejemplo, mantener las posibilidades en la memoria, etc.) ya que estamos hablando de muchas combinaciones.
PD Otra extensión interesante de la pregunta sería la localización.
Una solución de Python es bastante económica y, dado que utiliza generadores, es eficiente en términos de uso de memoria.
import itertools
keys = dict(enumerate(''::ABC:DEF:GHI:JKL:MNO:PQRS:TUV:WXYZ''.split('':'')))
def words(number):
digits = map(int, str(number))
for ls in itertools.product(*map(keys.get, digits)):
yield ''''.join(ls)
for w in words(258):
print w
Obviamente, itertools.product está resolviendo la mayor parte del problema para usted. Pero escribirlo uno mismo no es difícil. Aquí hay una solución en marcha, que es cuidadosa para reutilizar el result la matriz para generar todas las soluciones y un cierre f para capturar las palabras generadas. Combinados, estos permiten el uso de memoria O (log n) dentro del product .
package main
import (
"bytes"
"fmt"
"strconv"
)
func product(choices [][]byte, result []byte, i int, f func([]byte)) {
if i == len(result) {
f(result)
return
}
for _, c := range choices[i] {
result[i] = c
product(choices, result, i+1, f)
}
}
var keys = bytes.Split([]byte("::ABC:DEF:GHI:JKL:MNO:PQRS:TUV:WXYZ"), []byte(":"))
func words(num int, f func([]byte)) {
ch := [][]byte{}
for _, b := range strconv.Itoa(num) {
ch = append(ch, keys[b-''0''])
}
product(ch, make([]byte, len(ch)), 0, f)
}
func main() {
words(256, func(b []byte) { fmt.Println(string(b)) })
}
Use una lista L donde L [i] = los símbolos que el dígito que puedo representar.
L [1] = @,.,! (por ejemplo) L [2] = a, b, c
Etc.
Entonces puedes hacer algo como esto (pseudo-C):
void f(int k, int st[])
{
if ( k > numberOfDigits )
{
print contents of st[];
return;
}
for each character c in L[Digit At Position k]
{
st[k] = c;
f(k + 1, st);
}
}
Asumiendo que cada lista contiene 3 caracteres, tenemos 3 ^ 7 posibilidades para 7 dígitos y 3 ^ 12 para 12, que no son tantos. Si necesitas todas las combinaciones, no veo una forma mucho mejor. Puedes evitar la recursión y todo eso, pero no vas a obtener algo mucho más rápido que esto sin importar qué.
Encontrará la fuente (Scala) aquí y un applet de trabajo aquí.
Como 0 y 1 no coinciden con los caracteres, construyen puntos de interrupción naturales en números. Pero no aparecen en todos los números (excepto 0 al principio). Los números más largos, como +49567892345 a partir de 9 dígitos que comienzan, pueden llevar a OutOfMemoryErrors. Así que sería mejor dividir un número en grupos como
- 01723 5864
- 0172 35864
Para ver, si puede tener sentido a partir de las partes más cortas. Escribí un programa de este tipo, y probé algunos números de mis amigos, pero rara vez encontré combinaciones de palabras más cortas, que podrían verificarse en un diccionario para encontrar coincidencias, por no hablar de palabras largas y sencillas.
Por lo tanto, mi decisión fue solo apoyar la búsqueda , no la automatización completa, mostrando posibles combinaciones, alentando dividir el número a mano, tal vez varias veces.
Así que encontré + -RAD JUNG (+ -ciclo chico).
Si acepta faltas de ortografía, abreviaturas, palabras extranjeras, números como palabras, números en palabras y nombres, su oportunidad de encontrar una solución es mucho mejor, que sin juguetear.
246848 => 2hot4u (too hot for you)
466368 => goodn8 (good night)
1325 => 1FCK (Football club)
53517 => JDK17 (Java Developer Kit)
son cosas que un humano podría observar: hacer que un algoritmo encuentre tales cosas es bastante difícil.
Oracle SQL: se puede usar con cualquier número de teléfono y puede admitir fácilmente la localización.
CREATE TABLE digit_character_map (digit number(1), character varchar2(1));
SELECT replace(permutations,'' '','''') AS permutations
FROM (SELECT sys_connect_by_path(map.CHARACTER,'' '') AS permutations, LEVEL AS lvl
FROM digit_character_map map
START WITH map.digit = substr(''12345'',1,1)
CONNECT BY digit = substr(''12345'',LEVEL,1))
WHERE lvl = length(''12345'');
Aquí está el código de trabajo para el mismo ... es una recursión en cada paso, verificando la posibilidad de cada combinación al ocurrir el mismo dígito en una serie ... No estoy seguro de que exista una solución mejor desde el punto de vista de complejidad .....
Por favor, hágamelo saber para cualquier problema ...
import java.util.ArrayList;
public class phonenumbers {
/**
* @param args
*/
public static String mappings[][] = {
{"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"}
};
public static void main(String[] args) {
// TODO Auto-generated method stub
String phone = "3333456789";
ArrayList<String> list= generateAllnums(phone,"",0);
}
private static ArrayList<String> generateAllnums(String phone,String sofar,int j) {
// TODO Auto-generated method stub
//System.out.println(phone);
if(phone.isEmpty()){
System.out.println(sofar);
for(int k1=0;k1<sofar.length();k1++){
int m=sofar.toLowerCase().charAt(k1)-48;
if(m==-16)
continue;
int i=k1;
while(true && i<sofar.length()-2){
if(sofar.charAt(i+1)=='' '')
break;
else if(sofar.charAt(i+1)==sofar.charAt(k1)){
i++;
}else{
break;
}
}
i=i-k1;
//System.out.print(" " + m +", " + i + " ");
System.out.print(mappings[m][i%3]);
k1=k1+i;
}
System.out.println();
return null;
}
int num= phone.charAt(j);
int k=0;
for(int i=j+1;i<phone.length();i++){
if(phone.charAt(i)==num){
k++;
}
}
if(k!=0){
int p=0;
ArrayList<String> list2= generateAllnums(phone.substring(p+1), sofar+phone.charAt(p)+ " ", 0);
ArrayList<String> list3= generateAllnums(phone.substring(p+1), sofar+phone.charAt(p), 0);
}
else{
ArrayList<String> list1= generateAllnums(phone.substring(1), sofar+phone.charAt(0), 0);
}
return null;
}
}
Este enfoque usa R y se basa en convertir primero el diccionario a su representación de dígitos correspondiente, luego usarlo como una búsqueda.
La conversión solo toma 1 segundo en mi máquina (la conversión del diccionario de Unix nativo de aproximadamente 100,000 palabras), y las búsquedas típicas de hasta 100 entradas de dígitos diferentes toman un total de .1 segundos:
library(data.table)
#example dictionary
dict.orig = tolower(readLines("/usr/share/dict/american-english"))
#split each word into its constituent letters
#words shorter than the longest padded with "" for simpler retrieval
dictDT = setDT(tstrsplit(dict.orig, split = "", fill = ""))
#lookup table for conversion
#NB: the following are found in the dictionary and would need
# to be handled separately -- ignoring here
# (accents should just be appended to
# matches for unaccented version):
# c("", "''", "á", "â", "å", "ä",
# "ç", "é", "è", "ê", "í", "ñ",
# "ó", "ô", "ö", "û", "ü")
lookup = data.table(num = c(rep(''2'', 3), rep(''3'', 3), rep(''4'', 3),
rep(''5'', 3), rep(''6'', 3), rep(''7'', 4),
rep(''8'', 3), rep(''9'', 4)),
let = letters)
#using the lookup table, convert to numeric
for (col in names(dictDT)) {
dictDT[lookup, (col) := i.num, on = setNames("let", col)]
}
#back to character vector
dict.num = do.call(paste0, dictDT)
#sort both for faster vector search
idx = order(dict.num)
dict.num = dict.num[idx]
dict.orig = dict.orig[idx]
possibilities = function(input) dict.orig[dict.num == input]
#sample output:
possibilities(''269'')
# [1] "amy" "bmw" "cox" "coy" "any" "bow" "box" "boy" "cow" "cox" "coy"
possibilities(''22737'')
# [1] "acres" "bards" "barer" "bares" "barfs" "baser" "bases" "caper"
# [9] "capes" "cards" "cares" "cases"
Este es un algoritmo recursivo en C ++ 11.
#include <iostream>
#include <array>
#include <list>
std::array<std::string, 10> pm = {
"0", "1", "ABC", "DEF", "GHI", "JKL", "MNO", "PQRS", "TUV", "WXYZ"
};
void generate_mnemonic(const std::string& numbers, size_t i, std::string& m,
std::list<std::string>& mnemonics)
{
// Base case
if (numbers.size() == i) {
mnemonics.push_back(m);
return;
}
for (char c : pm[numbers[i] - ''0'']) {
m[i] = c;
generate_mnemonic(numbers, i + 1, m, mnemonics);
}
}
std::list<std::string> phone_number_mnemonics(const std::string& numbers)
{
std::list<std::string> mnemonics;
std::string m(numbers.size(), 0);
generate_mnemonic(numbers, 0, m, mnemonics);
return mnemonics;
}
int main() {
std::list<std::string> result = phone_number_mnemonics("2276696");
for (const std::string& s : result) {
std::cout << s << std::endl;
}
return 0;
}
Solución Scala:
def mnemonics(phoneNum: String, dict: IndexedSeq[String]): Iterable[String] = {
def mnemonics(d: Int, prefix: String): Seq[String] = {
if (d >= phoneNum.length) {
Seq(prefix)
} else {
for {
ch <- dict(phoneNum.charAt(d).asDigit)
num <- mnemonics(d + 1, s"$prefix$ch")
} yield num
}
}
mnemonics(0, "")
}
Suponiendo que cada dígito se asigna a un máximo de 4 caracteres, el número de llamadas recursivas Tsatisface la desigualdad T(n) <= 4T(n-1), que es del orden 4^n.
Soy más bien un novato, por favor corríjame donde sea que esté equivocado.
Lo primero es mirar hacia la complejidad del espacio y el tiempo. Lo que es realmente malo, ya que es factorial, por lo que para factorial (7) = 5040 cualquier algoritmo recursivo haría. Pero para factorial (12) ~ = 4 * 10 ^ 8 que puede causar un desbordamiento de pila en una solución recursiva.
Así que no intentaría un algoritmo recursivo. La solución de bucle es muy sencilla utilizando "Siguiente permutación".
Así que crearía y ordenaría {0, 1, 2, 3, 4, 5} y generaría toda la permutación y, al imprimir, los reemplazaría con los caracteres respectivos, por ejemplo. 0 = A, 5 = F
Siguiente algoritmo Perm funciona de la siguiente manera. Por ejemplo, dado 1,3,5,4 siguiente permutación es 1,4,3,5
Pasos para encontrar la siguiente perm.
De derecha a izquierda, encuentra el primer número decreciente. por ejemplo 3
De izquierda a derecha, encuentre el número más bajo mayor que 3, por ejemplo. 4
Intercambia estos números como invierte el subconjunto. 1,4,5,3 subconjunto inverso 1,4,3,5
Al usar la permutación (o rotación) siguiente, genera un subconjunto específico de permutaciones, suponiendo que desea mostrar 1000 permutaciones a partir de un número de teléfono en particular. Esto puede evitar que tengas todos los números en la memoria. Si almaceno números como enteros de 4 bytes, 10 ^ 9 bytes = 1 GB!
Una opción en Objective-C:
- (NSArray *)lettersForNumber:(NSNumber *)number {
switch ([number intValue]) {
case 2:
return @[@"A",@"B",@"C"];
case 3:
return @[@"D",@"E",@"F"];
case 4:
return @[@"G",@"H",@"I"];
case 5:
return @[@"J",@"K",@"L"];
case 6:
return @[@"M",@"N",@"O"];
case 7:
return @[@"P",@"Q",@"R",@"S"];
case 8:
return @[@"T",@"U",@"V"];
case 9:
return @[@"W",@"X",@"Y",@"Z"];
default:
return nil;
}
}
- (NSArray *)letterCombinationsForNumbers:(NSArray *)numbers {
NSMutableArray *combinations = [[NSMutableArray alloc] initWithObjects:@"", nil];
for (NSNumber *number in numbers) {
NSArray *lettersNumber = [self lettersForNumber:number];
//Ignore numbers that don''t have associated letters
if (lettersNumber.count == 0) {
continue;
}
NSMutableArray *currentCombinations = [combinations mutableCopy];
combinations = [[NSMutableArray alloc] init];
for (NSString *letter in lettersNumber) {
for (NSString *letterInResult in currentCombinations) {
NSString *newString = [NSString stringWithFormat:@"%@%@", letterInResult, letter];
[combinations addObject:newString];
}
}
}
return combinations;
}
Una solución R usando bucles anidados:
# Create phone pad
two <- c("A", "B", "C")
three <- c("D", "E", "F")
four <- c("G", "H", "I")
five <- c("J", "K", "L")
six <- c("M", "N", "O", "P")
seven <- c("Q", "R", "S")
eight <- c("T", "U", "V")
nine <- c("W", "X", "Y", "Z")
# Choose three numbers
number_1 <- two
number_2 <- three
number_3 <- six
# create an object to save the combinations to
combinations <- NULL
# Loop through the letters in number_1
for(i in number_1){
# Loop through the letters in number_2
for(j in number_2){
# Loop through the letters in number_3
for(k in number_3){
# Add each of the letters to the combinations object
combinations <- c(combinations, paste0(i, j, k))
}
}
}
# Print all of the possible combinations
combinations
Publiqué otra solución R más extraña usando más bucles y muestreos en mi blog .
He implementado un caché que ayudó a reducir el número de recursiones. Este caché evitará el escaneo de las letras que ya había hecho para combinaciones anteriores. Por una parte, iba a 120k bucles, después de la implementación del caché se redujo a 40k.
private List<String> generateWords(String phoneNumber) {
List<String> words = new LinkedList<String>();
List<String> wordsCache = new LinkedList<String>();
this.generatePossibleWords("", phoneNumber, words, wordsCache);
return words;
}
private void generatePossibleWords(String prefix, String remainder,
List<String> words, List<String> wordsCache) {
int index = Integer.parseInt(remainder.substring(0, 1));
for (int i = 0; i < phoneKeyMapper.get(index).size(); i++) {
String mappedChar = phoneKeyMapper.get(index).get(i);
if (prefix.equals("") && !wordsCache.isEmpty()) {
for (String word : wordsCache) {
words.add(mappedChar + word);
}
} else {
if (remainder.length() == 1) {
String stringToBeAdded = prefix + mappedChar;
words.add(stringToBeAdded);
wordsCache.add(stringToBeAdded.substring(1));
LOGGER.finest("adding stringToBeAdded = " + stringToBeAdded.substring(1));
} else {
generatePossibleWords(prefix + mappedChar,
remainder.substring(1), words, wordsCache);
}
}
}
}
private void createPhoneNumberMapper() {
if (phoneKeyMapper == null) {
phoneKeyMapper = new ArrayList<>();
phoneKeyMapper.add(0, new ArrayList<String>());
phoneKeyMapper.add(1, new ArrayList<String>());
phoneKeyMapper.add(2, new ArrayList<String>());
phoneKeyMapper.get(2).add("A");
phoneKeyMapper.get(2).add("B");
phoneKeyMapper.get(2).add("C");
phoneKeyMapper.add(3, new ArrayList<String>());
phoneKeyMapper.get(3).add("D");
phoneKeyMapper.get(3).add("E");
phoneKeyMapper.get(3).add("F");
phoneKeyMapper.add(4, new ArrayList<String>());
phoneKeyMapper.get(4).add("G");
phoneKeyMapper.get(4).add("H");
phoneKeyMapper.get(4).add("I");
phoneKeyMapper.add(5, new ArrayList<String>());
phoneKeyMapper.get(5).add("J");
phoneKeyMapper.get(5).add("K");
phoneKeyMapper.get(5).add("L");
phoneKeyMapper.add(6, new ArrayList<String>());
phoneKeyMapper.get(6).add("M");
phoneKeyMapper.get(6).add("N");
phoneKeyMapper.get(6).add("O");
phoneKeyMapper.add(7, new ArrayList<String>());
phoneKeyMapper.get(7).add("P");
phoneKeyMapper.get(7).add("Q");
phoneKeyMapper.get(7).add("R");
phoneKeyMapper.get(7).add("S");
phoneKeyMapper.add(8, new ArrayList<String>());
phoneKeyMapper.get(8).add("T");
phoneKeyMapper.get(8).add("U");
phoneKeyMapper.get(8).add("V");
phoneKeyMapper.add(9, new ArrayList<String>());
phoneKeyMapper.get(9).add("W");
phoneKeyMapper.get(9).add("X");
phoneKeyMapper.get(9).add("Y");
phoneKeyMapper.get(9).add("Z");
}
}
Lo intenté en ruby, y se me ocurrió una forma diferente de hacerlo, probablemente no sea eficiente, como el tiempo y el espacio O (?) En este momento, pero me gusta porque utiliza el método Array incorporado del producto de Ruby. ¿Qué piensas?
EDITAR: veo una solución muy similar en Python arriba, pero no la había visto cuando agregué mi respuesta
def phone_to_abc(phone)
phone_abc = [
''0'', ''1'', ''abc'', ''def'', ''ghi'',
''jkl'', ''mno'', ''pqrs'', ''tuv'', ''wxyz''
]
phone_map = phone.chars.map { |x| phone_abc[x.to_i].chars }
result = phone_map[0]
for i in 1..phone_map.size-1
result = result.product(phone_map[i])
end
result.each { |x|
puts "#{x.join}"
}
end
phone_to_abc(''86352'')
Reescribí la última respuesta a esto ( mencionada anteriormente ), de C a Java . También incluí el soporte para 0 y 1 (como 0 y 1) porque números como 555-5055 no funcionaban en absoluto con el código anterior.
Aquí está. Se conservan algunos comentarios.
public static void printPhoneWords(int[] number) {
char[] output = new char[number.length];
printWordsUtil(number,0,output);
}
static String[] phoneKeys= new String[]{"0", "1", "ABC", "DEF", "GHI", "JKL",
"MNO", "PQRS", "TUV", "WXYZ"};
private static void printWordsUtil(int[] number, int curDigIndex, char[] output) {
// Base case, if current output word is done
if (curDigIndex == output.length) {
System.out.print(String.valueOf(output) + " ");
return;
}
// Try all 3-4 possible characters for the current digit in number[]
// and recurse for the remaining digits
char curPhoneKey[] = phoneKeys[number[curDigIndex]].toCharArray();
for (int i = 0; i< curPhoneKey.length ; i++) {
output[curDigIndex] = curPhoneKey[i];
printWordsUtil(number, curDigIndex+1, output);
if (number[curDigIndex] <= 1) // for 0 or 1
return;
}
}
public static void main(String[] args) {
int number[] = {2, 3, 4};
printPhoneWords(number);
System.out.println();
}
private List<string> strs = new List<string>();
char[] numbersArray;
private int End = 0;
private int numberOfStrings;
private void PrintLetters(string numbers)
{
this.End = numbers.Length;
this.numbersArray = numbers.ToCharArray();
this.PrintAllCombinations(this.GetCharacters(this.numbersArray[0]), string.Empty, 0);
}
private void PrintAllCombinations(char[] letters, string output, int depth)
{
depth++;
for (int i = 0; i < letters.Length; i++)
{
if (depth != this.End)
{
output += letters[i];
this.PrintAllCombinations(this.GetCharacters(Convert.ToChar(this.numbersArray[depth])), output, depth);
output = output.Substring(0, output.Length - 1);
}
else
{
Console.WriteLine(output + letters[i] + (++numberOfStrings));
}
}
}
private char[] GetCharacters(char x)
{
char[] arr;
switch (x)
{
case ''0'': arr = new char[1] { ''.'' };
return arr;
case ''1'': arr = new char[1] { ''.'' };
return arr;
case ''2'': arr = new char[3] { ''a'', ''b'', ''c'' };
return arr;
case ''3'': arr = new char[3] { ''d'', ''e'', ''f'' };
return arr;
case ''4'': arr = new char[3] { ''g'', ''h'', ''i'' };
return arr;
case ''5'': arr = new char[3] { ''j'', ''k'', ''l'' };
return arr;
case ''6'': arr = new char[3] { ''m'', ''n'', ''o'' };
return arr;
case ''7'': arr = new char[4] { ''p'', ''q'', ''r'', ''s'' };
return arr;
case ''8'': arr = new char[3] { ''t'', ''u'', ''v'' };
return arr;
case ''9'': arr = new char[4] { ''w'', ''x'', ''y'', ''z'' };
return arr;
default: return null;
}
}
#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;
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;
}
/**
* Simple Java implementation without any input/error checking
* (expects all digits as input)
**/
public class PhoneSpeller
{
private static final char[][] _letters = new char[][]{
{''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''}
};
public static void main(String[] args)
{
if (args.length != 1)
{
System.out.println("Please run again with your phone number (no dashes)");
System.exit(0);
}
recursive_phoneSpell(args[0], 0, new ArrayList<String>());
}
private static void recursive_phoneSpell(String arg, int index, List<String> results)
{
if (index == arg.length())
{
printResults(results);
return;
}
int num = Integer.parseInt(arg.charAt(index)+"");
if (index==0)
{
for (int j = 0; j<_letters[num].length; j++)
{
results.add(_letters[num][j]+"");
}
recursive_phoneSpell(arg, index+1, results);
}
else
{
List<String> combos = new ArrayList<String>();
for (int j = 0; j<_letters[num].length; j++)
{
for (String result : results)
{
combos.add(result+_letters[num][j]);
}
}
recursive_phoneSpell(arg, index+1, combos);
}
}
private static void printResults(List<String> results)
{
for (String result : results)
{
System.out.println(result);
}
}
}
namespace WordsFromPhoneNumber
{
/// <summary>
/// Summary description for WordsFromPhoneNumber
/// </summary>
[TestClass]
public class WordsFromPhoneNumber
{
private static string[] Chars = { "0", "1", "ABC", "DEF", "GHI", "JKL", "MNO", "PQRS", "TUV", "WXYZ" };
public WordsFromPhoneNumber()
{
//
// TODO: Add constructor logic here
//
}
#region overhead
private TestContext testContextInstance;
/// <summary>
///Gets or sets the test context which provides
///information about and functionality for the current test run.
///</summary>
public TestContext TestContext
{
get
{
return testContextInstance;
}
set
{
testContextInstance = value;
}
}
#region Additional test attributes
//
// You can use the following additional attributes as you write your tests:
//
// Use ClassInitialize to run code before running the first test in the class
// [ClassInitialize()]
// public static void MyClassInitialize(TestContext testContext) { }
//
// Use ClassCleanup to run code after all tests in a class have run
// [ClassCleanup()]
// public static void MyClassCleanup() { }
//
// Use TestInitialize to run code before running each test
// [TestInitialize()]
// public void MyTestInitialize() { }
//
// Use TestCleanup to run code after each test has run
// [TestCleanup()]
// public void MyTestCleanup() { }
//
#endregion
[TestMethod]
public void TestMethod1()
{
IList<string> words = Words(new int[] { 2 });
Assert.IsNotNull(words, "null");
Assert.IsTrue(words.Count == 3, "count");
Assert.IsTrue(words[0] == "A", "a");
Assert.IsTrue(words[1] == "B", "b");
Assert.IsTrue(words[2] == "C", "c");
}
[TestMethod]
public void TestMethod23()
{
IList<string> words = Words(new int[] { 2 , 3});
Assert.IsNotNull(words, "null");
Assert.AreEqual(words.Count , 9, "count");
Assert.AreEqual(words[0] , "AD", "AD");
Assert.AreEqual(words[1] , "AE", "AE");
Assert.AreEqual(words[2] , "AF", "AF");
Assert.AreEqual(words[3] , "BD", "BD");
Assert.AreEqual(words[4] , "BE", "BE");
Assert.AreEqual(words[5] , "BF", "BF");
Assert.AreEqual(words[6] , "CD", "CD");
Assert.AreEqual(words[7] , "CE", "CE");
Assert.AreEqual(words[8] , "CF", "CF");
}
[TestMethod]
public void TestAll()
{
int[] number = new int [4];
Generate(number, 0);
}
private void Generate(int[] number, int index)
{
for (int x = 0; x <= 9; x += 3)
{
number[index] = x;
if (index == number.Length - 1)
{
var w = Words(number);
Assert.IsNotNull(w);
foreach (var xx in number)
{
Console.Write(xx.ToString());
}
Console.WriteLine(" possible words:/n");
foreach (var ww in w)
{
Console.Write("{0} ", ww);
}
Console.WriteLine("/n/n/n");
}
else
{
Generate(number, index + 1);
}
}
}
#endregion
private IList<string> Words(int[] number)
{
List<string> words = new List<string>(100);
Assert.IsNotNull(number, "null");
Assert.IsTrue(number.Length > 0, "length");
StringBuilder word = new StringBuilder(number.Length);
AddWords(number, 0, word, words);
return words;
}
private void AddWords(int[] number, int index, StringBuilder word, List<string> words)
{
Assert.IsTrue(index < number.Length, "index < length");
Assert.IsTrue(number[index] >= 0, "number >= 0");
Assert.IsTrue(number[index] <= 9, "number <= 9");
foreach (var c in Chars[number[index]].ToCharArray())
{
word.Append(c);
if (index < number.Length - 1)
{
AddWords(number, index + 1, word, words);
}
else
{
words.Add(word.ToString());
}
word.Length = word.Length - 1;
}
}
}
}
public class Permutation {
//display all combination attached to a 3 digit number
public static void main(String ar[]){
char data[][]= new char[][]{{''a'',''k'',''u''},
{''b'',''l'',''v''},
{''c'',''m'',''w''},
{''d'',''n'',''x''},
{''e'',''o'',''y''},
{''f'',''p'',''z''},
{''g'',''q'',''0''},
{''h'',''r'',''0''},
{''i'',''s'',''0''},
{''j'',''t'',''0''}};
int num1, num2, num3=0;
char tempdata[][]= new char[3][3];
StringBuilder number = new StringBuilder("324"); // a 3 digit number
//copy data to a tempdata array-------------------
num1= Integer.parseInt(number.substring(0,1));
tempdata[0] = data[num1];
num2= Integer.parseInt(number.substring(1,2));
tempdata[1] = data[num2];
num3= Integer.parseInt(number.substring(2,3));
tempdata[2] = data[num3];
//display all combinations--------------------
char temp2[][]=tempdata;
char tempd, tempd2;
int i,i2, i3=0;
for(i=0;i<3;i++){
tempd = temp2[0][i];
for (i2=0;i2<3;i2++){
tempd2 = temp2[1][i2];
for(i3=0;i3<3;i3++){
System.out.print(tempd);
System.out.print(tempd2);
System.out.print(temp2[2][i3]);
System.out.println();
}//for i3
}//for i2
}
}
}//end of class
static final String[] keypad = {"", "", "ABC", "DEF", "GHI", "JKL", "MNO", "PQRS", "TUV", "WXYZ"};
String[] printAlphabet(int num){
if (num >= 0 && num < 10){
String[] retStr;
if (num == 0 || num ==1){
retStr = new String[]{""};
} else {
retStr = new String[keypad[num].length()];
for (int i = 0 ; i < keypad[num].length(); i++){
retStr[i] = String.valueOf(keypad[num].charAt(i));
}
}
return retStr;
}
String[] nxtStr = printAlphabet(num/10);
int digit = num % 10;
String[] curStr = null;
if(digit == 0 || digit == 1){
curStr = new String[]{""};
} else {
curStr = new String[keypad[digit].length()];
for (int i = 0; i < keypad[digit].length(); i++){
curStr[i] = String.valueOf(keypad[digit].charAt(i));
}
}
String[] result = new String[curStr.length * nxtStr.length];
int k=0;
for (String cStr : curStr){
for (String nStr : nxtStr){
result[k++] = nStr + cStr;
}
}
return result;
}