Generating random permutation with forced change of order (Secret Santa)

Question

I wrote this function to generate random permutation of input vector, while making sure every element has switched place (for a Secret Santa like purpose).

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

You can run code here. Note that's still work in progress, I'm mostly concerned about the function above.

participants is guaranteed to contain no duplicate elements.

I'm not really concerned with speed - it's supposed to be executed by humans, they are unlikely to notice any performance improvement. Of course, you are welcome to point any obvious performance issues.
However, I'm concerned with the readability of the function, particularly with the use of std::mismatch to find actually matching elements. It feels too clever, but maybe it's just good use of functional programming and I'm overthinking? It also seems too long for a good function (22 lines), but I can't think of how it could be splitted/shortened logically.

Answer 1

I would suggest breaking the actual permutation algorithm out into its own function, since it’s useful on its own. That would pretty much solve the readability problem.

And then I would suggest doing the permutation with indices, rather than copying the whole input vector. (Indices would also work for other range types, especially if you limit the input range type to random-access, which is not unreasonable for a sorting algorithm.) Once you’re dealing with indices, detecting positions that are unchanged is trivial, and quick:

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

Once you have that, your main function is trivial:

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

I would also suggest moving the creation of the RNG out of the function, and passing the RNG in as an argument:

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

This goes with the doctrine of “one function, one job”, and allows both reusing the RNG, and testing the function with a known RNG.

If you want to go even further, an “is-fully-permuted-indices” algorithm, to remove that for loop in get_fully_permuted_indices(), also seems useful:

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