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;
}

SOURCE

Content is available under GNU Free Documentation License 1.2.

*Related*