CareerCup

hope my code is understandable with the comments. the main function is the permute just before the main.

#include <string>
#include <vector>
#include <map>
#include <iostream>
using namespace std;

// init some data structures used later.                                                                                                               
// 1. positionsMap:                                                                                                                                    
// construct a map (key is int, value is a vector of positions where that number occurs)                                                               
// eg:112 , for key=1, val=(0,1) and key=2, val (2).                                                                                                   
//                                                                                                                                                     
// 2. mappings:                                                                                                                                        
// construct a map to find the mappings. eg 1=>A,B,C 2=>D,E,F ... 9=>Y,Z                                                                               
// we only add keys which are present in input.                                                                                                        
void init(const string& input, map<char, vector<size_t> > &positionsMap, map<char, vector<char> > &mappings){
  positionsMap.clear();
  mappings.clear();

  for (unsigned i = 0; i<input.size() ;++i){
    if (input[i] <'1' || input[i] >'9'){
      throw runtime_error("Invalid input");
    }
    if (positionsMap.find(input[i]) != positionsMap.end()){ // already in map add to exisiting vector                                                  
      positionsMap[input[i]].push_back(i);
    }
    else{
      vector<size_t> vec;
      vec.push_back(i);
      positionsMap[input[i]] = vec;
    }

    if (mappings.find(input[i]) == mappings.end() ){
      vector<char> vec;
      unsigned int num = static_cast<int>(input[i]) - '0';
      char start = 'A';
      vec.push_back(start + 3*(num-1));
      vec.push_back(start + 3*(num-1) +1);
      if (num!=9) vec.push_back(start + 3*(num-1)+ 2); // when num=9, we have only 2 values: Y and Z.                                                  
      mappings[input[i]] = vec;
    }
  }
  // print the ds we have just built...for debugging.                                                                                                  
  cout <<"Mappings...\n";
  map<char,vector<char> >::const_iterator mappings_iter = mappings.begin();
  while (mappings_iter != mappings.end()) {
    cout << mappings_iter->first << "=>";
    vector<char> val = mappings_iter->second;
    for (vector<char>::const_iterator i = val.begin(); i!= val.end() ; ++i){
      cout << *i <<"\t";
    }
    cout << endl;
    ++mappings_iter;
  }
  cout <<"Positions map...\n";
  map<char, vector<size_t> >:: const_iterator positions_iter = positionsMap.begin();
  while (positions_iter != positionsMap.end()) {
    cout << positions_iter->first << "=>";
    vector<size_t> val = positions_iter->second;
    for (vector<size_t>::const_iterator i = val.begin(); i!= val.end() ; ++i){
      cout << *i <<"\t";
    }
    cout << endl;
    ++positions_iter;
  }

}

// for all the positions in the string fill it with char c.                                                                                            
void fillStr(string &str, vector<size_t> &positions, char c){
  unsigned len = str.size();
  for (vector<size_t>::const_iterator i = positions.begin() ; i != positions.end() ; ++i){
    if (*i >=len){
      cout <<len <<"<=" <<*i <<endl;
      throw runtime_error("Invalid position");
    }
    str[*i] = c;
  }
}


void permute(const string& input,
             map<char, vector<size_t> > &positionsMap,
             map<char, vector<char> > &mappings,
             string& out,
             map<char,vector<char> >::iterator iter){

  if (iter == mappings.end()){
    // we have filled everything, print the output.                                                                                                    
    cout << out << endl;
    return;
  }
  char key = iter->first;
  vector<char> val = iter->second;
  map<char,vector<char> >::iterator  next = std::next(iter,1);
  for (vector<char>::const_iterator i = val.begin(); i!= val.end() ; ++i){
    fillStr(out,positionsMap[key] ,*i);
    permute(input, positionsMap, mappings, out, next); // <--- main recursive call.                                                                    
  }
}

int main(){
  map<char, vector<size_t> > positionsMap;
  map<char, vector<char> > mappings;
  string input = "112";
  string out = input;
  init(input, positionsMap, mappings);
  cout <<"\n\nOutput:\n";
  permute(input, positionsMap, mappings, out, mappings.begin());
  return 0;
}

public class Mapping {

private char[][] array = { {}, { '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' } };

private String input = "1223";

private char[] c = input.toCharArray();
private char[] index = new char[10];
private char[] result = new char[c.length];

public Mapping() {
for (int i = 0; i < 10; i++) {
index[i] = '0';
}
}

private void judge(int pos) {
if (pos == c.length) {
System.out.println(result);
return;
}
char[] f = { c[pos] };
String s = new String(f);
int k = Integer.parseInt(s);
if (index[k] == '0') {
for (int j = 0; j < array[k].length; j++) {
index[k] = array[k][j];
result[pos] = array[k][j];
judge(pos + 1);
index[k] = '0';
}
} else {
result[pos] = index[k];
judge(pos + 1);
}
}

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
new Mapping().judge(0);
}

}

This should suffice
basically just a permutation generator with remembrance

#include <cstring>
#include <fstream>
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

vector<char> AA;
int coverd[9];
char a[9];
void generate(char a[],int len,int full)
{
	if(len==0)
	{
		for(auto it=AA.begin();it!=AA.end();it++)
			cout<<*it;
		cout<<endl;
	}
	else
	{
		int coeff=(int)(a[full-len]-'1');
		coeff = coeff*3;
		if(coverd[coeff/3]==-1)
		{			
			for(int i=0;i<3;i++)
			{
				coverd[coeff/3] = i;
				AA.push_back((char)('A'+ coeff+i));
				generate(a,len-1,full);
				coverd[coeff/3] = -1;
				AA.pop_back();
				if(coeff==24&i==1)
					i=3;
			}
		}
		else
		{
				AA.push_back((char)('A'+ coeff+coverd[coeff/3]));
				generate(a,len-1,full);
				AA.pop_back();
		}
	}
}
int main()
{
	int sum =0;
	int count = 0;
	char a[100];
	cin>>a;
	for(int i=0;i<9;i++)
		coverd[i] = -1;
	generate(a,strlen(a),strlen(a));
	return 0;
}

This is the inverse of the telephone problem. Here's a quick but complete solution in Python...

from itertools import product

def inverse_phone(mappings, s):
	numbers = set([int(n) for n in s])
	combinations = product(*[mappings[n] for n in numbers])
	output = []
	for combination in combinations:
		possibility = ""
		for c in s:
			possibility += combination[int(c) - 1]
		output.append(possibility)
	return output

mappings = {1: ['a', 'b', 'c'], 2: ['d', 'e', 'f'], 3: ['g', 'h', 'i', 'j']}
print inverse_phone(mappings, "132")

If you want to do it without itertools, you can easily implement product in a few lines. Its official implementation is simply

def product(*args, **kwds):
    # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
    # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
    pools = map(tuple, args) * kwds.get('repeat', 1)
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]
    for prod in result:
        yield tuple(prod)

This will not work for an input like '113'. Thats because numbers in this case would be [1,3] and combination[int(c) - 1] at c=3, will look for combination[2], which is incorrect. One small modification to your code will solve the issue. Store the values of set as a list and find the index of int(c) in the list.

I hope this code is nice and simple. Each recursive branch gets its own re-defined mapping

def gendigs(digits, mapping, stream = None, perms = None):

    if stream is None:
        stream = []

    if perms is	None:
        perms =	[]

    if not digits:
        perms.append("".join(stream))
        return perms

    for letter in mapping[digits[0]]:

        # each branch gets its own stream copy                                                        
        stream_copy = [d for d in stream]
        stream_copy.append(letter)

        # each branch gets its own map                                                                
        map_copy = { k:v for k, v in mapping.iteritems() }
        map_copy[digits[0]] = letter

        # branch for each letter                                                                      
        gendigs(digits[1:], map_copy, stream_copy, perms)

    return perms

mapping = {
    "1": "ABC",
    "2": "DEF",
    "3": "HIJ",
    "4": "KLM"
}

print gendigs("112", mapping)

Why does the output not have ABD or BAD for 112?
Am I missing something here?

/** Given a mapping as follows:
'1' = 'A','B','C' 
'2' = 'D','E','F' 
... 
'9' = 'X','Y','Z'

If each number can represent exactly 1 letter in a given mapping, print all the results
from all possible mappings.

input: 112 
output :ouput = [AAD, BBD, CCD, AAE, AAF, BBE, BBF, CCE, CCF]
*/
public class letterMapping {

    public static void main (String[] args) {
        map.put('1', one);
        map.put('2', two);
        map.put('3', three);
        possibleMappings(112);
    }
    public static void possibleMappings(int input) {
        char[] test = new char[8];
        int mod = 0;
        for (int i = 0;;i++) {
            if (input - Math.pow(10, i) < 0) {
                mod = i - 1;
                break;
            }
        }
        possibleMappings(input, "", mod,test);
    }
    public static void possibleMappings(int input, String result, int mod, char[] memo) {
        if (input == 0) {
            System.out.println(result);
            return;
        }
        int curr = (int) (input / ((Math.pow(10, mod))));
        if (memo[curr] != 0) {
            possibleMappings(input - (int)(curr * (Math.pow(10, mod))), result + memo[curr], mod - 1, memo);
            return;
        }
        for (char c : map.get(Character.forDigit(curr, 10))) {
            memo[curr] = c;
            possibleMappings(input - (int)(curr * (Math.pow(10, mod))), result + c, mod - 1, memo);
            memo[curr] = 0;
        }
    }
    
    static HashMap<Character, char[]> map = new HashMap<>();
    static char[] one = {'A','B','C'};
    static char[] two = {'D', 'E', 'F'};
    static char[] three = {'G', 'H', 'I'}; 
    
}

// C solution, by simulating permutation

void Print()
{
char array[8][4] = {"ABC", "DEF", "GHI", ... "XYZ"};
char output[4];

output[3] = '\0';

printCore(array, output, 3, -1);
}

void PrintCore(char array[][4], char output[], int length, int index)
{
if (index == length - 1)
{
printf("%s ", output);
return;
}

for (i = 0; i < 3; ++i)
{
output[index+1] = array[index + 1][i];
PrintCore(array, output, length, index + 1);
}
}

// C

void Print()
{
char array[8][4] = {"ABC", "DEF", "GHI", ... "XYZ"};
char output[4];
char input = "112"; // could be scanf a string here, modify later

output[3] = '\0';

printCore(array, output, 3, -1);
}

void PrintCore(char array[][4], char output[], char input[], int length, int index)
{
int i;

if (index == length - 1)
{
printf("%s ", output);
return;
}

while (input[i])
{
output[index+1] = array[index + 1][input[i] - '0'];
PrintCore(array, output, length, index + 1);
}
}

//keep array for digits such that it is -1 if character is unlocked(not used before) and else store the index to which it should belong. see the code below

#define N 9
#define M 3
#define SIZE 10

void permute(char * str,int hash[],char arr[N][M],int pos)
{
    static char si[SIZE];
    int i;       //this iterates over all possible choices
    if(str[pos] == '\0')
    {
        si[pos] = '\0';
        printf("\n%s",si);
        return;
    }
    //take the current element of the string str
    //str[i] can be between 1 to 9 ,map it to index 0 to 8
    if(hash[str[pos]-'0'-1] != -1)          //some index fixed from 0 to 2
    {
    si[pos] = arr[str[pos]-'0'-1][hash[str[pos]-'0'-1]];
    permute(str,hash,arr,pos+1);
    }
    else
    { 
        //hash[str[pos]-'0'-1] == -1 so this is not a locked character
        int end = ((str[pos] == '9')?M-2:M-1);          //'9' has two letters only Y and Z
        for(i = 0; i <= end; i++)
        {
            //try all permutations
            si[pos] = arr[str[pos]-'0'-1][i];
            hash[str[pos]-'0'-1] = i;      //lock the character
            permute(str,hash,arr,pos+1);
            hash[str[pos]-'0'-1] = -1;     //unlock the character
        }
    }
}
    

int main()
{
    char arr[N][M] = {{'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','0'}};
    int hash[N];
    for(int i = 0; i < N; i++)
    hash[i] = -1;
    char * str = "112";
    permute(str,hash,arr,0);
}

/* Modify program to print desired above mentioned */

char* mapping[] ={"","ABC","DEF","GHI","JKL","MNO","PQR","STU","VWX","YZ"};
void printallcombination(char* s, int idx, char* res)
{
if(idx > strlen(s))
{
cout<<res<<"\n";
return;
}

int c = (int)(s[idx-1] - '0');
for(int i=0; i< strlen(mapping[c]);i++)
{
char* temp = (char*)malloc(sizeof(char) * 100);
memset(temp, 0, sizeof(char) * 100);
temp[0] = mapping[c][i];

char* temp1 = (char*)malloc(sizeof(char) * 100);
memset(temp1, 0, sizeof(char) * 100);
strcat(temp1, res);
printallcombination(s,idx+1, strcat(res, temp));
strcpy(res, temp1);
delete(temp);
delete(temp1);
}
}



void main( )
{
char* result = (char*)malloc(sizeof(char)*100);
memset(result, 0, sizeof(char)*100);
printallcombination("12",1,result);
}


Output :
ABD
ABE
ABF
ACD
ACE
ACF
BAD
BAE
BAF
BBD
BBE
BBF
BCD
BCE
BCF
CAD
CAE
CAF
CBD
CBE
CBF
CCD
CCE
CCF

/* Modify program to print desired above mentioned */

char* mapping[] ={"","ABC","DEF","GHI","JKL","MNO","PQR","STU","VWX","YZ"};
void printallcombination(char* s, int idx, char* res)
{
if(idx > strlen(s))
{
cout<<res<<"\n";
return;
}

int c = (int)(s[idx-1] - '0');
for(int i=0; i< strlen(mapping[c]);i++)
{
char* temp = (char*)malloc(sizeof(char) * 100);
memset(temp, 0, sizeof(char) * 100);
temp[0] = mapping[c][i];

char* temp1 = (char*)malloc(sizeof(char) * 100);
memset(temp1, 0, sizeof(char) * 100);
strcat(temp1, res);
printallcombination(s,idx+1, strcat(res, temp));
strcpy(res, temp1);
delete(temp);
delete(temp1);
}
}



void main( )
{
char* result = (char*)malloc(sizeof(char)*100);
memset(result, 0, sizeof(char)*100);
printallcombination("12",1,result);
}


Output :
ABD
ABE
ABF
ACD
ACE
ACF
BAD
BAE
BAF
BBD
BBE
BBF
BCD
BCE
BCF
CAD
CAE
CAF
CBD
CBE
CBF
CCD
CCE
CCF

void printcombinations(deque<int>&digits, map<int ,int>&index,vector<string>& dictionary) {
	if(index[digits[0]]==3) {
		return;
	}
	for(int i=digits.size()-1;i>=0;i--) {
		int nextIndex=index[digits[i]];
		if(nextIndex==3 && index[digits[0]]!=3 ){
			if(i-1>=0) {
				index[digits[i-1]]++;
			}

			index[digits[i]]=0;
		}
		if(index[digits[0]]==3) {return;}
	}

	for(int i=0;i<digits.size();i++) {
		printf("%c",dictionary[digits[i]][index[digits[i]]]);
		fflush(stdout);
	}
	printf("\n");
	index[digits[digits.size()-1]]++;
	printcombinations(digits,index,dictionary);


}

void printCombinationsOfMapping(int n) {
	vector<string> dictionary;

	dictionary.push_back("");
	dictionary.push_back("ABC");
	dictionary.push_back("DEF");
	dictionary.push_back("GHI");
	dictionary.push_back("JKL");
	dictionary.push_back("MNO");
	dictionary.push_back("PQR");
	dictionary.push_back("STU");
	dictionary.push_back("VWX");

	deque<int>digits;
	int temp=n;
	while(temp>0) {
		int digit=temp%10;
		digits.push_front(digit);
		temp=temp/10;
	}
	map<int,int> index;
	for(int i=0;i<digits.size();i++) {
		index[digits[i]]=0;
	}
	printcombinations(digits,index,dictionary);
}

Input: 112
Out:
[A, A, D]
[A, A, E]
[A, A, F]
[A, B, D]
[A, B, E]
[A, B, F]
[A, C, D]
[A, C, E]
[A, C, F]
[B, A, D]
[B, A, E]
[B, A, F]
[B, B, D]
[B, B, E]
[B, B, F]
[B, C, D]
[B, C, E]
[B, C, F]
[C, A, D]
[C, A, E]
[C, A, F]
[C, B, D]
[C, B, E]
[C, B, F]
[C, C, D]
[C, C, E]
[C, C, F]

public static void main(String[] args) {
		 Map<Integer, List<Character>> map = new HashMap<Integer, List<Character>>();
		 map.put(1, Arrays.asList('A', 'B', 'C'));
		 map.put(2, Arrays.asList('D', 'E', 'F'));
		 map.put(3, Arrays.asList('G', 'H', 'I'));
		 map.put(4, Arrays.asList('J', 'K', 'L'));
		 String input = "112";
		 char[] output = new char[input.length()];
		 printCombinations(input.toCharArray(), 0, output, map);
	 }
	 
	 public static void printCombinations(char[] input, int index, char[] output, Map<Integer, List<Character>> map) {
		 if(index == output.length) {
			 System.out.println(Arrays.toString(output));
			 output = new char[input.length];
		 }
		 else {
			 List<Character> list = map.get(Integer.parseInt(input[index]+""));
			 for(Character c: list) {
				 output[index] = c;
				 printCombinations(input, index+1, output, map);
			 }
		 }
	 }

This problem is known as telephone words and can be solved using simple recursion.