Find the missing permutation: Difference between revisions

}</lang>

=={{header|C++}}==

<lang Cpp>#include <algorithm>

#include <vector>

#include <iostream>

#include <string>

// These are lexicographically ordered

static const std::string GivenPermutations[] = {

"ABCD", "ABDC", "ACBD", "ACDB",

"ADBC", "ADCB", "BACD", "BADC",

"BCAD", "BCDA", "BDAC", "BDCA",

"CABD", "CADB", "CBAD", "CBDA",

"CDAB", "CDBA", "DABC", "DACB",

"DBCA", "DCAB", "DCBA"

};

static const size_t NumGivenPermutations = sizeof(GivenPermutations) / sizeof(std::string);

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.begin() + 4);

if(p == permutations.front())

break;

permutations.push_back(p);

}

std::vector<std::string> missing;

std::set_difference(permutations.begin(), permutations.end(), GivenPermutations,

GivenPermutations + NumGivenPermutations, std::back_insert_iterator< std::vector<std::string> >(missing));

std::copy(missing.begin(), missing.end(), std::ostream_iterator<std::string>(std::cout, "\n"));