セットのメンバーのすべての順列とサインのバリエーションのセットを作成する（C++）

Question

未知のサイズのベクトルが与えられたとします。例えば、それは

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

かもしれそれとも何か他のものである可能性があります。これは単なる例です。今、ベクトルのベクトルを返す関数を記述したいとします。しかし、このベクトルの各ベクトルは、オリジナルの別個の順列でなければならない。この場合、関数は{1,2,3}、{1,3}、{2,3,1}、{2,3}、{1,2,3} 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

Answer 2

だけ博覧会のために、別の方法を。今回は、イテレータベースのアプローチを提供するジェネレータオブジェクトを使用します。

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

template<class Vector> struct permutation_engine; 

template<class T> 
struct permutation_engine<std::vector<T>> 
{ 
    using perm_vector = std::vector<T>; 

    template<class VectorArg> 
    permutation_engine(VectorArg&& arg) : current_permutation(std::forward<VectorArg>(arg)) {} 

    struct iterator 
    { 
     using value_type = const perm_vector; 
     using reference = perm_vector&; 
     using pointer = perm_vector*; 
     using difference_type = int; 
     using iterator_category = std::input_iterator_tag; 

     reference operator*() const { return parent->current_permutation; } 
     auto operator != (iterator const& r) const -> bool { 
      return parent != r.parent; 
     } 

     auto operator++() { 
      if(not parent->advance()) { 
       parent = nullptr; 
      } 
      return *this; 
     } 

     permutation_engine* parent; 
    }; 

    iterator begin() 
    { 
     reset(); 
     return iterator { this }; 
    } 
    iterator end() { return iterator { nullptr }; }  

    bool advance() { 
     return next_permutation(Begin(), End()); 
    } 

    void reset() { 
     sort(Begin(), End()); 
     current_permutation.erase(unique(Begin(), End()), End()); 
    } 

    private: 
     auto Begin() { return std::begin(current_permutation); } 
     auto End() { return std::end(current_permutation); } 


    std::vector<T> current_permutation; 
}; 

template<class Vector> 
auto make_permutation_engine(Vector&& vector) 
{ 
    return permutation_engine<std::decay_t<Vector>>(std::forward<Vector>(vector)); 
} 

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

std::vector<int> append_negatives(std::vector<int> v) 
{ 
    using negateElement = std::negate<>; 

    v.reserve(v.size() * 2); 
    std::transform(begin(v), end(v), 
        back_inserter(v), 
        negateElement()); 

    return v; 
} 

int main() 
{ 
    std::cout << "[\n"; 
    for(auto&& vec : make_permutation_engine(append_negatives({ 1, 2, 3 }))) 
    { 
     emit(std::cout, vec); 
    } 
    std::cout << "]\n"; 
}