Programming exercise: permutations of a string

The problem is to implement a function that outputs all possible permutations of the characters in a string. Unlike combinations, two permutations are considered distinct if they contain the same characters, but in a different order. Also, for the purposes of this exercise, each occurrence of a repeated character is considered to be a distinct character. That is, if the input is “aaa”, the output should be six repetitions of “aaa”. The permutations may be output in any order.

This exercise, like the previous one on combinations of a string, is from the book Programming Interviews Exposed by John Mongan and Noah Suojanen^[1]\(\).

For a string of length \(n\), there are \(n! = n \times (n-1) \times (n-2) \times \cdots \times 1\) permutations. It’s fairly easy to see how these arise. A permutation may begin with any of the \(n\) characters. Having fixed this first character, the second one may be chosen from the remaining \((n – 1)\) characters. And so on.

The recursive structure of the problem is then obvious. To compute the permutations of a string of \(n\) characters, first cycle through the characters in the string. For each character, remove it from the string, compute the permutations of the remaining \((n – 1)\) characters, and then prepend the previously removed character to each of the resulting permutations. The base case is the empty string, whose only permutation is itself.

The problem stipulates that each occurrence of a repeated character is to be treated as a distinct character. Consider the input string “aba”. When dealing with the first “a”, the program should remove it, compute the permutations of “ba” (which are “ba” and “ab”), and then prepend “a” to those permutations (resulting in “aba” and “aab”). However, when dealing with the second occurrence of “a”, the program should remove that “a”, and compute the permutations of the remaining string, “ab”. This seems to cause some difficulty, as it will mean that our program has to distinguish between the removal of the first “a” and the removal of the second “a”. Note, however, that the permutations of “ab” are the same as the permutations of “ba” (though they might be output in a different order). A little thought shows that any time we need to remove a character, we can always just remove its first occurrence, since the permutations of the resulting characters will be the same regardless of which occurrence we remove.

To begin with, we need a function to remove the first occurrence of an item from a list. This is basically an exercise from “Scheme 101″:

1
2
3
4
5
6

(define (remove-once the-item the-list)
    (cond ((null? the-list) '())
          ((equal? the-item (car the-list)) (cdr the-list))
          (else (cons (car the-list) (remove-once the-item (cdr the-list))))
    )
)

The heart of our solution will be a function called permute. Given an empty set, it returns a set containing only the empty set. Otherwise, it calls itself recursively. The outline looks like this:

(define (permute the-list)
    (if (null? the-list) '(())
        (...)
    )
)

What goes into the (...) above? We can build this up from the inside out. We know that there is a recursive call to permute, but with the selected character removed (ignoring for the moment how we select this character):

(permute (remove-once the-selected the-list))

The selected character should be prepended to each of the resulting permutations:

(map (lambda (the-rest) (cons the-selected the-rest))
    (permute (remove-once the-selected the-list)))

Each of the characters should become the selected character in turn:

(map (lambda (the-selected) 
    (map (lambda (the-rest) (cons the-selected the-rest))
        (permute (remove-once the-selected the-list)))) 
                 the-list)

Running the above code on the input '(a b c d e) will result in something like '( (a-perms) (b-perms) (c-perms) (d-perms) (e-perms) ), where x-perms are permutations beginning with the letter x. This list of lists of permutations should be flattened by applying append. The rest of the program in Scheme is then:

8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

(define (permute the-list)
    (if (null? the-list) '(())
        (apply append
            (map (lambda (the-selected) 
                         (map (lambda (the-rest) (cons the-selected the-rest))
                              (permute (remove-once the-selected the-list)))) 
                 the-list)
        )
    )
)
 
(define (permutations the-string)
    (map (lambda (s) (apply string s))
        (permute (string->list the-string)))
)
 
(define test-input "abcde")
(display (permutations test-input))

Because we need to output \(n!\) permutations (note that the factorial grows faster than the exponential function), it’s probably a good idea in most cases not to keep the permutations in memory, but rather to print them out as they are generated.

The following Python program uses logic similar to the above Scheme program, but prints out each permutation right away. The only difference in the logic is that, because the Python program uses strings and indices into strings, it distinguishes between each occurrence of a repeated character:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def print_permutations(input_string):
 
    def print_permutations_helper(set_of_chars, output_string):
        if set_of_chars == "":
            print output_string,
        else:
            for index, char in enumerate(set_of_chars):
                print_permutations_helper(
                    set_of_chars[:index]+set_of_chars[index+1:], 
                    output_string + char)
 
    print_permutations_helper(input_string, "")
 
test_input = "abcde"
print_permutations(test_input)

One can manipulate sets, lists, or strings in C++ using STL classes, but it’s probably much faster to just use a boolean array to keep track of which letters have been “removed” from use. The following C++ program produces the same output as the above Python program:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

#include<iostream>
#include<string.h>
using namespace std;
 
void print_permutations_helper(char *input, char *output, bool *used,
    int len, int depth)
{
    // At the current depth, cycle through all the letters.
    for( int i = 0; i < len; i++ ) {
 
        // If the letter hasn't been used yet, use it.
        if( !used[i] ) {
            output[depth] = input[i];
 
            if( depth == len - 1 ) {
                cout << output << " ";
            } else {
                used[i] = true;
                print_permutations_helper(input, output, used, len, depth+1);
                used[i] = false;
            }
        }
    }
}
 
void print_permutations(char *input) 
{
    // Allocate a new character buffer to hold the output, and also
    // an array of flags for keeping track of which letters have
    // already been used.  (Assume that this always succeeds, or
    // that error handling is taken care of elsewhere.)
    int len = strlen(input);
    char *output = new char[len+1];
    output[len] = '\ 0';
    bool *used = new bool[len+1];
 
    // Initialise all the letters as unused.
    for( int i = 0; i < len; i++ ) {
        used[i] = false;
    }
 
    // Recursively print the permutations. 
    print_permutations_helper(input, output, used, len, 0);
    cout << endl;
 
    // Free the memory.    
    delete output;
    delete used;
}
 
int main()
{
    char test_input[] = "abcde";
    print_permutations(test_input);
}

As with the previous exercise on combinations of a string, this exercise also demonstrates how the typical approach to solving a problem will differ depending on whether Scheme or C++ (or some other language) is used. One can postulate a version of the Sapir-Whorf hypothesis for programming languages, that the language used to tackle a problem has an effect on the way in which it is solved.

– davinci 11804

Be Sociable, Share!

•