Computing permutations of sequences in C++


Posted by Diego Assencio on 2016.09.19 under Programming (C/C++)

Suppose you have a sequence of $n$ objects of type $T$ and wish to compute all permutations of the objects in this sequence. There are multiple approaches to this problem; for instance, this implementation works for sequences which are strings with $n$ characters but can be can be easily extended for sequences of objects of arbitrary types.

Instead of writing your own solution to this problem, though, consider using the STL algorithm std::next_permutation. We will first shown an example of how it should be used, then will go over the details:

#include <vector>
#include <iostream>
#include <algorithm>

int main()
{
	std::vector<int> v = { 1, 2, 3 };

	do
	{
		for (const int x : v)
		{
			std::cout << x << " ";
		}
		std::cout << "\n";
	}
	while (std::next_permutation(v.begin(), v.end()) == true);

	return 0;
}

The output of this program shows all permutations of the set {1,2,3}:

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

The std::next_permutation algorithm assumes that there is an ordering criterion for the objects in the sequence, i.e., that any two objects in the sequence can be compared using a "less than" operation. By default, std::next_permutation uses the operator < to compare objects, but you can provide your own comparison function as we will show below.

If the objects in the sequence can be compared using a "less than" operation, we can naturally order all permutations of this sequence lexicographically, i.e., we can order the permutations just like we do for words in the dictionary. This is the mechanism which std::next_permutation is based on: given a sequence of objects, it will permute them in place to turn the sequence into its next permutation in the lexicographical order. If a "next larger" sequence exists, i.e., if there is a next permutation on the "permutation dictionary", std::next_permutation returns true; if we already reached the "largest" permutation according to the lexicographical order, i.e., the one in which the sequence is sorted in descending order (largest element first, smallest element last), then std::next_permutation returns false and turns the sequence into the "smallest" one in the lexicographical order, i.e., the one with all objects sorted in ascending order.

The requirement that objects in the sequence can be ordered is a disadvantage since there are many types for which an order is not naturally defined. For those types, we can either overload operator< or directly pass a comparison function to std::next_permutation as shown below:

#include <vector>
#include <string>
#include <iostream>
#include <algorithm>

struct Person
{
	std::string name;
	int age;
};

/* ordering criterion for Persons: order by names */
bool compare(const Person& a, const Person& b)
{
	return a.name < b.name;
}

int main()
{
	std::vector<Person> v = { {"John",35}, {"Mary",27}, {"Bob",22} };

	/*
	 * this step (sorting v) is required for sequences which are not
	 * initially sorted, otherwise we will not generate all desired
	 * permutations (see below)
	 */
	std::sort(v.begin(), v.end(), compare);

	do
	{
		for (const Person& p : v)
		{
			std::cout << '{' << p.name << ',' << p.age << '}' << " ";
		}
		std::cout << "\n";
	}
	while (std::next_permutation(v.begin(), v.end(), compare) == true);

	return 0;
}

The output of this program now shows all permutations of the three Persons:

{Bob,22} {John,35} {Mary,27}
{Bob,22} {Mary,27} {John,35}
{John,35} {Bob,22} {Mary,27}
{John,35} {Mary,27} {Bob,22}
{Mary,27} {Bob,22} {John,35}
{Mary,27} {John,35} {Bob,22}

Notice that before generating all permutations of the sequence of Persons v, we sorted it. This step is necessary; without it, we would not generate all possible permutations of v because of the way std::next_permutation works: your initial sequence must be the "smallest one" in the lexicographical order, i.e., the one which is sorted in ascending order.

The iterators required by std::next_permutation must be at least bidirectional. Additionally, std::next_permutation uses std::swap to change the order of the objects in the sequence in order to produce the next permutation. If a swap is too costly for the type you are working with, consider assigning indices (0, 1, ..., n-1) or pointers to the objects and computing the permutations of these indices/pointers: the desired permutations of the original sequence of objects can then be expressed in terms of the permutations of indices/pointers instead of directly in terms of the objects themselves.

Comments

No comments posted yet.

Leave a reply

NOTE: A name and a comment (max. 1024 characters) must be provided; all other fields are optional. Equations will be processed if surrounded with dollar signs (as in LaTeX). You can post up to 5 comments per day.