집합의 모든 순열 집합 및 사인 변형 집합 만들기 (C++)

Question

크기가 알려지지 않은 벡터가 있다고 가정합니다. 예를 들어,

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

수 아니면 아무것도 될 수 있습니다. 그것은 단지 하나의 예입니다. 이제 벡터 벡터를 반환하는 함수를 작성한다고 가정 해 보겠습니다. 그러나이 벡터의 각 벡터는 원본의 고유 한 순열이어야합니다. 그래서이 경우 함수는 {1, 2, 3}, {1,3}, {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

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