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

Content is available under GNU Free Documentation License 1.2.