c++ - 创建集合成员的每个排列和符号变化的集合 (C++)

Question

假设我得到一个未知大小的 vector 。例如，它可以是

std::vector<int> myset1({1, 2, 3});

或者它可以是任何其他东西。那只是一个例子。现在，假设我想编写一个返回 vector vector 的函数。但是，此 vector 中的每个 vector 必须是原始 vector 的不同排列。所以在这种情况下，我希望该函数返回一个包含集合 {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, { 3, 1, 2} 和​​ {3, 2, 1}(不注意顺序)。

通过某种递归，这可能很简单。但是，如果我还想考虑每个元素的符号怎么办？例如:

std::vector<int> myset2({1, 2});

我希望函数返回 {1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1} , {-2, 1}, {-2, -1}(我不关心顺序)。

我正在努力想出一种优雅地设计它的方法。正如您可以想象的那样，对于更大的集合，使用这样的函数而不是手动列出每个集合变得很有必要，但目前我没有想到任何想法。你将如何实现这一目标？

Answer 1

第一次尝试:

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

std::vector<std::vector<int>> all_permutations(std::vector<int> input)
{
    std::vector<std::vector<int>> result;

    std::sort(begin(input), end(input));
    input.erase(std::unique(begin(input), end(input)), end(input));
    do {
        result.push_back(input);
    } while(std::next_permutation(begin(input), end(input)));

    return result;
}

template<class T>
void emit(std::ostream& os, std::vector<T> const& v)
{
    os << "  [";
    const char* sep = " ";
    for (auto&& x : v) {
        os << sep << x;
        sep = ", ";
    }
    os << "]\n";
}

template<class T>
void emit(std::ostream& os, std::vector<std::vector<T>> const& v)
{
    os << "[\n";
    for (auto&& x : v) {
        emit(os, x);
    }
    os << "]\n";
}

int main()
{
    emit(std::cout, all_permutations({ 1, 2, 3 }));
}

预期输出；

[
  [ 1, 2, 3]
  [ 1, 3, 2]
  [ 2, 1, 3]
  [ 2, 3, 1]
  [ 3, 1, 2]
  [ 3, 2, 1]
]

现在添加加号和减号的代码:

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

std::vector<std::vector<int>> all_permutations(std::vector<int> input)
{
    std::vector<std::vector<int>> result;

    std::sort(begin(input), end(input));
    input.erase(std::unique(begin(input), end(input)), end(input));
    do {
        result.push_back(input);
    } while(std::next_permutation(begin(input), end(input)));

    return result;
}

template<class T>
void emit(std::ostream& os, std::vector<T> const& v)
{
    os << "  [";
    const char* sep = " ";
    for (auto&& x : v) {
        os << sep << x;
        sep = ", ";
    }
    os << "]\n";
}

template<class T>
void emit(std::ostream& os, std::vector<std::vector<T>> const& v)
{
    os << "[\n";
    for (auto&& x : v) {
        emit(os, x);
    }
    os << "]\n";
}

std::vector<int> plus_and_minus(std::vector<int> v)
{
    std::vector<int> inverse;
    inverse.reserve(v.size());
    std::transform(begin(v), end(v), back_inserter(inverse), [](auto&& x) { return -x; });
    v.insert(end(v), begin(inverse), end(inverse));
    sort(begin(v), end(v));
    inverse.erase(unique(begin(v), end(v)), end(v));
    return v;
}

int main()
{
    emit(std::cout, all_permutations(plus_and_minus({ 1, 2, 3 })));
}

预期:

[
  [ -3, -2, -1, 1, 2, 3]
  [ -3, -2, -1, 1, 3, 2]
  [ -3, -2, -1, 2, 1, 3]
  [ -3, -2, -1, 2, 3, 1]
  [ -3, -2, -1, 3, 1, 2]
  [ -3, -2, -1, 3, 2, 1]
  [ -3, -2, 1, -1, 2, 3]
  [ -3, -2, 1, -1, 3, 2]
  [ -3, -2, 1, 2, -1, 3]
  [ -3, -2, 1, 2, 3, -1]
  [ -3, -2, 1, 3, -1, 2]
  [ -3, -2, 1, 3, 2, -1]
  [ -3, -2, 2, -1, 1, 3]
  [ -3, -2, 2, -1, 3, 1]
  [ -3, -2, 2, 1, -1, 3]
  [ -3, -2, 2, 1, 3, -1]
  [ -3, -2, 2, 3, -1, 1]
  [ -3, -2, 2, 3, 1, -1]
  [ -3, -2, 3, -1, 1, 2]
  [ -3, -2, 3, -1, 2, 1]
  [ -3, -2, 3, 1, -1, 2]
  [ -3, -2, 3, 1, 2, -1]
  [ -3, -2, 3, 2, -1, 1]
  [ -3, -2, 3, 2, 1, -1]
  [ -3, -1, -2, 1, 2, 3]
  [ -3, -1, -2, 1, 3, 2]
  [ -3, -1, -2, 2, 1, 3]
  [ -3, -1, -2, 2, 3, 1]
  [ -3, -1, -2, 3, 1, 2]
  [ -3, -1, -2, 3, 2, 1]
  [ -3, -1, 1, -2, 2, 3]
  [ -3, -1, 1, -2, 3, 2]
  [ -3, -1, 1, 2, -2, 3]
  [ -3, -1, 1, 2, 3, -2]
  [ -3, -1, 1, 3, -2, 2]
  [ -3, -1, 1, 3, 2, -2]
  [ -3, -1, 2, -2, 1, 3]
  [ -3, -1, 2, -2, 3, 1]
  [ -3, -1, 2, 1, -2, 3]
  [ -3, -1, 2, 1, 3, -2]
  [ -3, -1, 2, 3, -2, 1]
  [ -3, -1, 2, 3, 1, -2]
  [ -3, -1, 3, -2, 1, 2]
  [ -3, -1, 3, -2, 2, 1]
  [ -3, -1, 3, 1, -2, 2]
  [ -3, -1, 3, 1, 2, -2]
  [ -3, -1, 3, 2, -2, 1]
  [ -3, -1, 3, 2, 1, -2]
  [ -3, 1, -2, -1, 2, 3]
  [ -3, 1, -2, -1, 3, 2]
  [ -3, 1, -2, 2, -1, 3]
  [ -3, 1, -2, 2, 3, -1]
  [ -3, 1, -2, 3, -1, 2]
  [ -3, 1, -2, 3, 2, -1]
  [ -3, 1, -1, -2, 2, 3]
  [ -3, 1, -1, -2, 3, 2]
  [ -3, 1, -1, 2, -2, 3]
  [ -3, 1, -1, 2, 3, -2]
  [ -3, 1, -1, 3, -2, 2]
  [ -3, 1, -1, 3, 2, -2]
  [ -3, 1, 2, -2, -1, 3]
  [ -3, 1, 2, -2, 3, -1]
  [ -3, 1, 2, -1, -2, 3]
  [ -3, 1, 2, -1, 3, -2]
  [ -3, 1, 2, 3, -2, -1]
  [ -3, 1, 2, 3, -1, -2]
  [ -3, 1, 3, -2, -1, 2]
  [ -3, 1, 3, -2, 2, -1]
  [ -3, 1, 3, -1, -2, 2]
  [ -3, 1, 3, -1, 2, -2]
  [ -3, 1, 3, 2, -2, -1]
  [ -3, 1, 3, 2, -1, -2]
  [ -3, 2, -2, -1, 1, 3]
  [ -3, 2, -2, -1, 3, 1]
  [ -3, 2, -2, 1, -1, 3]
  [ -3, 2, -2, 1, 3, -1]
  [ -3, 2, -2, 3, -1, 1]
  [ -3, 2, -2, 3, 1, -1]
  [ -3, 2, -1, -2, 1, 3]
  [ -3, 2, -1, -2, 3, 1]
  [ -3, 2, -1, 1, -2, 3]
  ...etc

http://coliru.stacked-crooked.com/a/82a4c5784dc0070d