Write a method to compute all permutations of a string

Problem

Write a method to compute all permutations of a string

For example: given an input string, "abc", your program should print the following permutations:

a

ab

abc

ac

acb

b

ba

bac

bc

bca

c

ca

cab

cb

cba

Answer

This question is similar to "Finding all the subset of the given set" problem except for the fact that the order of the element in the subset is important. This means "ab" and "ba" are different.

DFS approach with duplicate subset check. $O(N \times N!)$

Unlike the "Finding all the subset of the given set" problem, we can perform the DFS from 0 to N-1 position, where N is the length of the input string.

While we produce the substring, we will encounter duplicate permutations. To prevent that we can use a hash table to check if we have already produced the current permutation before.
In C++, I used std::set for this purpose. This gives $O(\log N)$ search time.

This algorithm will run in $O(N \times N!$, where N is the length of the input string.
Here is the complete code.

	#include<set>
	#include<string>
	#include<iostream>
	using namespace std;
	void permutate(string left, string cur, set<string>& subset)
	{
	if (cur.length() && subset.find(cur) == subset.end())
	subset.insert(cur);
	if (left.length() == 0)
	return;
	for (int i = 0; i < left.length(); i++)
	{
	string r = left;
	cur.push_back(left[i]);
	r.erase(i, 1);
	permutate(r, cur, subset);
	cur.pop_back();
	}
	}
	set<string> find_all_permutation(string input)
	{
	set<string> subset;
	permutate(input, "", subset);
	return subset;
	}
	int main()
	{
	string input = "abcd";
	set<string> result = find_all_permutation(input);
	set<string>::iterator iter;
	for(iter = result.begin(); iter != result.end(); iter++)
	cout<< *iter <<endl;
	return 1;
	}

view raw find_all_permutation.cpp hosted with ❤ by GitHub

Practice statistics

16:50: made one logical flaw due to the confusion of the usage of std::set. erase method. 

UPDATE(2022-06-13): Solved in python. Had to compose the sub input excluding already used characters. This is a little wasteful in terms of memory since I had to use two buffers one to hold the temporary chars and the other to store the permutation. This way does not require the hashtable since we remove already used chars during the search.

	def permute(input, buffer, result):
	for i in range(len(input)):
	buffer.append(input[i])
	sub_input = input[:i] + input[i+1:]
	# add to the result
	result.append("".join(buffer))
	permute(sub_input, buffer, result)
	buffer.pop()
	return result
	input = "abc"
	result = permute(input, [], [])
	print ("result = {}".format(result))

view raw find_all_permutation.py hosted with ❤ by GitHub