Как сделать перестановку с повторением в C++?

В C++ есть несколько способов реализовать перестановку с повторением. Один из таких способов - использовать стандартный алгоритм std::next_permutation из библиотеки <algorithm>.

Перестановки с повторениями - это комбинации элементов, в которых один и тот же элемент может быть использован несколько раз. Например, для набора {1, 2, 2}, мы можем получить следующие перестановки: {1, 2, 2}, {2, 1, 2}, {2, 2, 1}.

Для начала, нам нужно убедиться, что элементы в массиве отсортированы в порядке возрастания. Затем мы можем использовать std::next_permutation для генерации всех возможных перестановок. Этот алгоритм будет менять порядок элементов в массиве на следующую лексикографическую перестановку, пока они не будут перебраны все возможные варианты.

Вот пример кода:

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

int main() {
  std::vector<int> nums = {1, 2, 2};

  // Сортируем массив в порядке возрастания
  std::sort(nums.begin(), nums.end());

  do {
    // Выводим текущую перестановку
    for (int num : nums) {
      std::cout << num << " ";
    }
    std::cout << std::endl;
  } while (std::next_permutation(nums.begin(), nums.end()));

  return 0;
}

В этом примере мы сначала сортируем массив nums в порядке возрастания, чтобы гарантировать правильный порядок элементов в перестановках. Затем мы используем do-while цикл для перебора всех перестановок. Внутри цикла мы выводим текущую перестановку на экран.

Когда все перестановки будут сгенерированы, std::next_permutation вернет false, и цикл завершится.

Выходные данные для этого примера будут:

1 2 2
2 1 2
2 2 1

Таким образом, мы получили все возможные перестановки элементов массива с повторениями.