Write a recursive function for generating all permutations of an input string. Return them as a set.
Don't worry about time or space complexity—if we wanted efficiency we'd write an iterative version.
To start, assume every character in the input string is unique.
Your function can have loops—it just needs to also be recursive.
Let's break the problem into subproblems. How could we re-phrase the problem of getting all permutations for "cats" in terms of a smaller but similar subproblem?
Let's make our subproblem be getting all permutations for all characters except the last one. If we had all permutations for "cat," how could we use that to generate all permutations for "cats"?
We could put the "s" in each possible position for each possible permutation of "cat"!
These are our permutations of "cat":
cat
cta
atc
act
tac
tca
For each of them, we add "s" in each possible position. So for "cat":
cat
scat
csat
cast
cats
And for "cta":
cta
scta
csta
ctsa
ctas
And so on.
Now that we can break the problem into subproblems, we just need a base case and we have a recursive algorithm!
If we're making all permutations for "cat," we take all permutations for "ca" and then put "t" in each possible position in each of those permutations. We use this approach recursively:
// Implements a set
// Set * setNew(void);
// void setFree(Set *set);
// int setContainsString(const Set *set, const char *str);
// void setInsertString(Set *set, const char *str);
// SetIterator setIterationStart(const Set *set);
// SetIterator setIterationNext(const SetIterator it);
// int setIterationIsEnd(const SetIterator it);
// char * setIteratorGetStringValue(const SetIterator it);
#include "Cake/Set.h"
// Returns a dynamically allocated new string that is the original string
// with the character spliced in
char * insertCharacterInString(const char *stringWithoutCharacter,
char character, size_t position)
{
size_t lengthAfterInsert = strlen(stringWithoutCharacter) + 1;
assert(position < lengthAfterInsert);
char *stringWithCharacter = malloc(lengthAfterInsert + 1);
assert(stringWithCharacter != NULL);
if (position > 0) {
memcpy(stringWithCharacter, stringWithoutCharacter, position);
}
stringWithCharacter[position] = character;
if (position < lengthAfterInsert) {
memcpy(stringWithCharacter + position + 1,
stringWithoutCharacter + position,
lengthAfterInsert - position);
}
stringWithCharacter[lengthAfterInsert] = '\0';
return stringWithCharacter;
}
Set * getPermutations(const char *inputString)
{
size_t inputLength = strlen(inputString);
Set *permutations = setNew();
SetIterator item;
// base case
if (inputLength <= 1) {
setInsertString(permutations, inputString);
return permutations;
}
char *allCharsExceptLast = malloc(inputLength);
assert(allCharsExceptLast != NULL);
strncpy(allCharsExceptLast, inputString, inputLength - 1);
allCharsExceptLast[inputLength - 1] = 0;
char lastChar = inputString[inputLength - 1];
// recursive call: get all possible permutations for all chars except last
Set *permutationsOfAllCharsExceptLast = getPermutations(allCharsExceptLast);
free(allCharsExceptLast);
// put the last char in all possible positions for each of the above permutations
for (item = setIterationStart(permutationsOfAllCharsExceptLast); !setIterationIsEnd(item);
item = setIterationNext(item)) {
size_t position;
char *permutationOfAllCharsExceptLast = setIteratorGetValue(item);
assert(strlen(permutationOfAllCharsExceptLast) == inputLength - 1);
for (position = 0; position < inputLength; position++) {
char *permutation = insertCharacterInString(permutationOfAllCharsExceptLast,
lastChar, position);
setInsertString(permutations, permutation);
free(permutation);
}
}
setFree(permutationsOfAllCharsExceptLast);
return permutations;
}
How does the problem change if the string can have duplicate characters?
What if we wanted to bring down the time and/or space costs?
This is one where playing with a sample input is huge. Sometimes it helps to think of algorithm design as a two-part process: first figure out how you would solve the problem "by hand," as though the input was a stack of paper on a desk in front of you. Then translate that process into code.
Interview Cake
