Как генерировать различные перестановки вектора в C ++? - PullRequest
Новая
       22

Как генерировать различные перестановки вектора в C ++?

0 голосов
/ 21 марта 2020

Предположим, что существует вектор только с двоичными элементами, подобными этому: 

X = [0, 0, 1, 1]

Единственные различные перестановки: 

X = [0, 0, 1, 1]
X = [0, 1, 0, 1]
X = [0, 1, 1, 0]
X = [1, 0, 0, 1]
X = [1, 0, 1, 0]
X = [1, 1, 0, 0]

Существует ли эффективный способ сделать это в C ++

1 Ответ

2 голосов
/ 21 марта 2020

Использование std::next_permutation: 

#include <algorithm>
#include <array>
#include <cstdio>

int
main()
{
  std::array<int, 4> arr{ 0, 0, 1, 1 };

  /* Sort the array if necessary */
  std::sort(arr.begin(), arr.end());

  do {
    for (auto const e : arr)
      std::printf("%d ", e);
    std::putchar('\n');
  } while (std::next_permutation(arr.begin(), arr.end()));
}

Выход: 

0 0 1 1 
0 1 0 1 
0 1 1 0 
1 0 0 1 
1 0 1 0 
1 1 0 0

Демо

...