C++ 벡터의 모든 조합

Question

0 to n의 일부 숫자가 있다고 가정 해 봅시다. 크기가 s 인 경우 가능한 모든 조합을보고 싶습니다.

따라서 순열의 수는 s! * n!/(s!*(n-s)!)과 같습니다. n = 3 및 s = 3와

예 :

0 1 2 | 0 1 3 | 0 2 1 | 0 2 3 | 0 3 1 | 0 3 2 | 1 0 2 | 1 0 3 | 1 3 2 
1 2 3 | 1 2 0 | 1 3 0 | 2 0 1 | 2 1 0 | 2 0 3 | 2 3 0 | 2 3 1 | 2 1 3 
      3 0 1 | 3 1 0 | 3 0 2 | 3 2 0 | 3 1 2 | 3 2 1 

이를 달성하기 위해 부스트/STL을 사용하여 부드러운 방법이 있나요?

Answer 1

LIVE DEMO

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

void dfs(int depth, int s, int i, std::vector<int>& c, const std::vector<int>& v) 
{ 
    if (depth == s) 
    { 
     do 
     { 
      std::copy(c.begin(), c.end(), std::ostream_iterator<int>(std::cout, " ")); 
      std::cout << "| "; 
     } 
     while (std::next_permutation(c.begin(), c.end())); 
    } 
    else 
    { 
     for (int j = i + 1; j < (int)v.size(); ++j) 
     { 
      c.push_back(v[j]); 
      dfs(depth + 1, s, j, c, v); 
      c.pop_back(); 
     } 
    } 
} 

int main() 
{ 
    std::vector<int> v{ 0, 1, 2, 3 }; 
    std::sort(v.begin(), v.end()); 
    v.erase(std::unique(v.begin(), v.end()), v.end());  
    std::vector<int> c; 
    const int length = 3; 
    dfs(0, length, -1, c, v); 
} 

출력 :

여기

0 1 2 | 0 2 1 | 1 0 2 | 1 2 0 | 2 0 1 | 2 1 0 | 0 1 3 | 0 3 1 | 1 0 3 | 
1 3 0 | 3 0 1 | 3 1 0 | 0 2 3 | 0 3 2 | 2 0 3 | 2 3 0 | 3 0 2 | 3 2 0 | 
1 2 3 | 1 3 2 | 2 1 3 | 2 3 1 | 3 1 2 | 3 2 1 

Answer 2

인 T.C.이 코멘트에서 언급 한 링크 (http://howardhinnant.github.io/combinations.html)를 사용하여 코드이의

#include "../combinations/combinations" 
#include <iostream> 
#include <vector> 

int 
main() 
{ 
    std::vector<int> v{0, 1, 2, 3}; 
    typedef std::vector<int>::iterator Iter; 
    for_each_permutation(v.begin(), v.begin()+3, v.end(), 
     [](Iter f, Iter l) 
     { 
      for (; f != l; ++f) 
       std::cout << *f << ' '; 
      std::cout << "| "; 
      return false; 
     } 
    ); 
    std::cout << '\n'; 
} 

0 1 2 | 0 2 1 | 1 0 2 | 1 2 0 | 2 0 1 | 2 1 0 | 0 1 3 | 0 3 1 | 1 0 3 | 1 3 0 | 3 0 1 | 3 1 0 | 0 2 3 | 0 3 2 | 2 0 3 | 2 3 0 | 3 0 2 | 3 2 0 | 1 2 3 | 1 3 2 | 2 1 3 | 2 3 1 | 3 1 2 | 3 2 1 | 

한 가지 중요한 이점을 도서관이상은 정렬 될 요소를 정렬 할 필요가 없으며 비교할 필요도 없습니다. 예를 들면 :

#include "../combinations/combinations" 
#include <iostream> 
#include <vector> 

enum class color 
{ 
    red, 
    green, 
    blue, 
    cyan 
}; 

std::ostream& 
operator<< (std::ostream& os, color c) 
{ 
    switch (c) 
    { 
    case color::red: 
     os << "red"; 
     break; 
    case color::green: 
     os << "green"; 
     break; 
    case color::blue: 
     os << "blue"; 
     break; 
    case color::cyan: 
     os << "cyan"; 
     break; 
    } 
    return os; 
} 

int 
main() 
{ 
    std::vector<color> v{color::blue, color::red, color::cyan, color::green}; 
    typedef std::vector<color>::iterator Iter; 
    for_each_permutation(v.begin(), v.begin()+3, v.end(), 
     [](Iter f, Iter l) 
     { 
      for (; f != l; ++f) 
       std::cout << *f << ' '; 
      std::cout << "| "; 
      return false; 
     } 
    ); 
    std::cout << '\n'; 
} 

파란색, 빨간색 시안 | 푸른 시안 색 빨강 | 빨간 푸른 시안 | 붉은 시안 색 블루 | 시안 파랑 빨강 | 녹청 빨강 | 파란색 빨간색 녹색 | 푸른 녹색 빨강 | 빨강 파랑 녹색 | 빨간색 녹색 파란색 | 녹색 파랑 빨강 | 녹색 빨간색 파란색 | 블루 시안 색 녹색 | 푸른 녹색 시안 | 시안 블루 그린 | 녹청 녹색 파랑 | 녹색 푸른 시안 | 녹색 시안 색 블루 | 붉은 시안 색 녹색 | 빨간 녹색 시안 | 시안 색 빨강 녹색 | 녹청 녹색 빨강 | 녹색 붉은 시안 | 녹색 시안 색 빨강 |