Question

•• P11.1 Phone numbers and PIN codes can be easier to remember when you find words that
spell out the number on a standard phone keypad. For example, instead of remembering
the combination 2633, you can just think of CODE.
Write a recursive function that, given a number, yields all possible spellings (which
may or may not be real words).
•• P11.2 Continue Exercise P11.1, checking the words against the /usr/share/dict/words file on
your computer, or the words.txt file in the companion code for this book. For a given
number, return only actual words.
••• P11.3 With a longer number, you may need more than one word to remember it on a
phone pad. For example, 846-386-2633 is TIME TO CODE. Using your work from
Exercise P11.2, write a program that, given any number, lists all word sequences that
spell the number on a phone pad.
••• P11.4 Change the permutations function of Section 11.4 (which computed all permutations
at once) to a PermutationIterator (which computes them one at a time).
class PermutationIterator
{
public:
PermutationIterator(string s) { . . . }
string next_permutation() { . . . }
bool has_more_permutations() { . . . }
};
Here is how you would print out all permutations of the string "eat":
PermutationIterator iter("eat");
while (iter.has_more_permutations())
{
cout << iter.next_permutation() << endl;
}
Now we need a way to iterate through the permutations recursively. Consider the
string "eat". As before, we’ll generate all permutations that start with the letter 'e',

then those that start with 'a', and finally those that start with 't'. How do we generate
the permutations that start with 'e'? Make another PermutationIterator object
(called tail_iterator) that iterates through the permutations of the substring "at". In
the next_permutation function, simply ask tail_iterator what its next permutation is,
and then add the 'e' at the front. However, there is one special case. When the tail
iterator runs out of permutations, all permutations that start with the current letter
have been enumerated. Then
• Increment the current position.
• Compute the tail string that contains all letters except for the current one.
• Make a new permutation iterator for the tail string.
You are done when the current position has reached the end of the string.
••• P11.5 The following program generates all permutations of the numbers 0, 1, 2, ... , n – 1,
without using recursion.
#include <iostream>
#include <vector>
using namespace std;
void swap(int& x, int& y)
{
int temp = x;
x = y;
y = temp;
}
void reverse(vector<int>& a, int i, int j)
{
while (i < j)
{
swap(a[i], a[j]); i++; j--;
}
}
bool next_permutation(vector<int>& a)
{
for (int i = a.size() - 1; i > 0; i--)
{
if (a[i - 1] < a[i])
{
int j = a.size() - 1;
while (a[i - 1] > a[j]) { j--; }
swap(a[i - 1], a[j]);
reverse(a, i, a.size() - 1);
return true;
}
}
return false;
}
void print(const vector<int>& a)
{
for (int i = 0; i < a.size(); i++)
{
cout << a[i] << " ";
}
cout << endl;

}
int main()
{
const int n = 4;
vector<int> a(n);
for (int i = 0; i < a.size(); i++) { a[i] = i; }
print(a);
while (next_permutation(a)) { print(a); }
return 0;
}
The algorithm uses the fact that the set to be permuted consists of distinct numbers.
Thus, you cannot use the same algorithm to compute the permutations of the
characters in a string. You can, however, use this technique to get all permutations of
the character positions and then compute a string whose ith character
is s[a[i]]. Use
this approach to reimplement the generate_permutations function without recursion.
•• P11.6 Refine the is_palindrome function to work with arbitrary strings, by ignoring nonletter
characters and the distinction between upper- and lowercase letters. For
example, if the input string is
"Madam, I’m Adam!"
then you’d first strip off the last character because it isn’t a letter, and recursively
check whether the shorter string
"Madam, I’m Adam"
is a palindrome.

Answer 1

P11.1 :

CODE:

=====================================================================================

#include <bits/stdc++.h>

using namespace std;
//taking the souce characters for each button
const char source[10][5] = {"", "", "ABC", "DEF", "GHI", "JKL","MNO", "PQRS", "TUV", "WXYZ"};

//recursive function "digits"
void digits(int m[], int x, char codes[], int y)
{
    int n;
    if (x == y)
    {
  //priting "," after every string
        cout<<codes<<", ";
        return;
    }
//using for loop
    for (n=0; n<strlen(source[m[x]]); n++)
    {
        codes[x] = source[m[x]][n];
//calling function recursively
        digits(m, x+1, codes, y);
        if(m[x] == 0 || m[x] == 1)
        {
            return;
        }
    }
}
//function "check" to call the function
void check(int m[], int y)
{
    char codes[y+1];
    codes[y] ='\0';
    digits(m, 0, codes, y);
}

int main(void)
{
//input code to print
    int m[] = {2,6,3,3};
    int y = sizeof(m)/sizeof(m[0]);
    check(m, y);
    return 0;
}

=======================================================================================