Генерация случайной перестановки с принудительной сменой порядка (Секретный Санта)

Я написал эту функцию для генерации случайной перестановки входного вектора, при этом убедившись, что каждый элемент поменялся местами (для целей, подобных Тайному Санту).

std::map<std::string, std::string> getPermutation(const std::vector<std::string>& participants)
{
  auto permuted = participants;
  std::random_device rd;
  std::mt19937 g(rd());
  bool correctlyPermuted = false;
  while(!correctlyPermuted)
  {
    std::shuffle(permuted.begin(), permuted.end(), g);
    auto res = std::mismatch(participants.begin(), participants.end(), permuted.begin(), std::not_equal_to{});
    if(res.first == participants.end())
    {
      correctlyPermuted = true;
    }
  }
  
  std::map<std::string, std::string> result;
  for(int i = 0; i < participants.size(); ++i)
  {
    result[participants[i]] = permuted[i];
  }
  return result;
}

Вы можете запустить код Вот. Обратите внимание, что работа еще продолжается, меня больше всего беспокоит функция выше.

participants гарантированно не содержит повторяющихся элементов.

Меня не особо интересует скорость — она ​​должна выполняться людьми, они вряд ли заметят улучшение производительности. Конечно, вы можете указать на любые очевидные проблемы с производительностью.
Однако меня беспокоит читабельность функции, особенно с использованием std::mismatch чтобы найти действительно совпадающие элементы. Ощущается слишком умный, но, может быть, это просто хорошее использование функционального программирования, и я слишком много думаю? Он также кажется слишком длинным для хорошей функции (22 строки), но я не могу придумать, как его можно логически разделить / сократить.

Я бы предложил разбить реальный алгоритм перестановки на отдельную функцию, поскольку он полезен сам по себе. Это в значительной степени решило бы проблему удобочитаемости.

И тогда я бы предложил сделать перестановку с индексы, а не копировать весь входной вектор. (Индексы также будут работать для других типов диапазонов, особенно если вы ограничите тип входного диапазона произвольным доступом, что не является необоснованным для алгоритма сортировки.) Когда вы имеете дело с индексами, обнаружение неизменных позиций тривиально, и быстрый:

template <std::sized_range Rng, typename Gen>
requires std::uniform_random_bit_generator<std::remove_reference_t<Gen>>
auto get_fully_permuted_indices(Rng const& rng, Gen&& gen)
{
    auto idxs = std::vector<std::size_t>(std::ranges::size(rng));
    std::iota(idxs.begin(), idxs.end(), std::size_t(0));

    auto permuted = false;
    do
    {
        std::ranges::shuffle(idxs, gen);

        permuted = true; // hope for the best!
        for (auto i = std::size_t(0); i < res.size(); ++i)
        {
            // if the value at i is the same as i, then this is not properly permuted
            if (i == idxs[i])
            {
                permuted = false;
                break;
            }
        }
    } while (not permuted);

    return idxs;
}

Как только вы это сделаете, ваша основная функция станет тривиальной:

std::map<std::string, std::string> getPermutation(const std::vector<std::string>& participants)
{
    auto const idxs = get_fully_permuted_indices(participants, std::mt19937{std::random_device(){}});

    auto res = std::map<std::string, std::string>{};
    for (auto i = std::size_t(0); i < std::ranges::size(participants); ++i)
        res.emplace(participants[i], participants[idxs[i]]);

    return res;
}

Я также предлагаю вынести создание ГСЧ из функции и передать ГСЧ в качестве аргумента:

template <typename Gen>
requires std::uniform_random_bit_generator<std::remove_reference_t<Gen>>
auto getPermutation(const std::vector<std::string>& participants, Gen&& gen)
{
    auto const idxs = get_fully_permuted_indices(participants, std::forward<Gen>(gen));

    auto res = std::map<std::string, std::string>{};
    for (auto i = std::size_t(0); i < std::ranges::size(participants); ++i)
        res.emplace(participants[i], participants[idxs[i]]);

    return res;
}

Это соответствует доктрине «одна функция, одна работа» и позволяет как повторно использовать ГСЧ, так и тестировать функцию с известным ГСЧ.

Если вы хотите пойти еще дальше, используйте алгоритм «полностью переставленные индексы», чтобы удалить это for зациклиться get_fully_permuted_indices(), тоже кажется полезным:

template <std::input_range Rng>
requires std::equality_comparable_with<std::ranges::range_value_t<Rng>, std::size_t>
constexpr auto is_fully_permuted_indices(Rng const& rng)
{
    auto idx = std::size_t(0);
    for (auto&& item : rng)
    {
        if (item == idx++)
            return false;
    }

    return true;
}

template <std::sized_range Rng, typename Gen>
requires std::uniform_random_bit_generator<std::remove_reference_t<Gen>>
auto get_fully_permuted_indices(Rng const& rng, Gen&& gen)
{
    auto idxs = std::vector<std::size_t>(std::ranges::size(rng));
    std::iota(idxs.begin(), idxs.end(), std::size_t(0));

    do
    {
        std::ranges::shuffle(idxs, gen);
    } while (not is_fully_permuted_indices(idxs));

    return idxs;
}