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 | 

Одно существенное преимущество этого библиотека за std::next_permutation состоит в том, что элементы, которые переставляются, не нужно сортировать и даже не быть менее сопоставимыми. Например:

#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'; 
} 

синий красный голубой | синий голубой красный | красный синий голубой | красный синий синий | голубой синий красный | синий красный синий | синий красный зеленый | синий зеленый красный | красный синий зеленый | красный зеленый синий | зеленый синий красный | зеленый красный синий | синий голубой зеленый | синий зеленый голубой | сине-зеленый | сине-зеленый синий | зеленый синий голубой | зеленый голубой голубой | красный сине-зеленый | красный зеленый голубой | голубой красный зеленый | голубой зеленый красный | зеленый красный голубой | зеленый голубой красный |