C++: Find the Missing Permutation

These are all of the permutations of the symbols A, B, C and D, except for one that’s not listed. Find that missing permutation.

(cf. Permutations)

There is an obvious method : enumerating all permutations of A, B, C, D, and looking for the missing one.

There is an alternate method. Hint : if all permutations were here, how many times would A appear in each position ? What is the parity of this number ?

ABCD
CABD
ACDB
DACB
BCDA
ACBD
ADCB
CDAB
DABC
BCAD
CADB
CDBA
CBAD
ABDC
ADBC
BDCA
DCBA
BACD
BADC
BDAC
CBDA
DBCA
DCAB

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

static const std::string GivenPermutations[] = {
	"ABCD","CABD","ACDB","DACB",
	"BCDA","ACBD","ADCB","CDAB",
	"DABC","BCAD","CADB","CDBA",
	"CBAD","ABDC","ADBC","BDCA",
	"DCBA","BACD","BADC","BDAC",
	"CBDA","DBCA","DCAB"
};
static const size_t NumGivenPermutations = sizeof(GivenPermutations) / sizeof(*GivenPermutations);

int main()
{
	std::vector<std::string> permutations;
	std::string initial = "ABCD";
	permutations.push_back(initial);

	while(true)
	{
		std::string p = permutations.back();
		std::next_permutation(p.begin(), p.end());
		if(p == permutations.front())
		break;
		permutations.push_back(p);
	}

	std::vector<std::string> missing;
	std::set<std::string> given_permutations(GivenPermutations, GivenPermutations + NumGivenPermutations);
	std::set_difference(permutations.begin(), permutations.end(), given_permutations.begin(),
	given_permutations.end(), std::back_inserter(missing));
	std::copy(missing.begin(), missing.end(), std::ostream_iterator<std::string>(std::cout, "\n"));
	return 0;
}