def _preprocess_for_efficient_roulette_selection(discretized_probabilities):
    """Prepares data for performing efficient roulette selection.

    The output is a tuple (alternates, keep_weights). The output is guaranteed
    to satisfy a sampling-equivalence property. Specifically, the following
    sampling process is guaranteed to be equivalent to simply picking index i
    with probability weights[i] / sum(weights):

        1. Pick a number i in [0, len(weights) - 1] uniformly at random.
        2. Return i With probability keep_weights[i]*len(weights)/sum(weights).
        3. Otherwise return alternates[i].

    In other words, the output makes it possible to perform roulette selection
    while generating only two random numbers, doing a single lookup of the
    relevant (keep_chance, alternate) pair, and doing one comparison. This is
    not so useful classically, but in the context of a quantum computation
    where all those things are expensive the second sampling process is far
    superior.

    Args:
        discretized_probabilities: A list of probabilities approximated by
            integer numerators (with an implied common denominator). In order
            to operate without floating point error, it is required that the
            sum of this list is a multiple of the number of items in the list.

    Returns:
        alternates (list[int]): An alternate index for each index from 0 to
            len(weights) - 1
        keep_weight (list[int]): Indicates how often one should stay at index i
            instead of switching to alternates[i]. To get the actual keep
            probability of the i'th element, multiply keep_weight[i] by
            len(discretized_probabilities) then divide by
            sum(discretized_probabilities).
    """
    weights = list(discretized_probabilities)  # Need a copy we can mutate.
    if not weights:
        raise ValueError('Empty input.')

    n = len(weights)
    target_weight = sum(weights) // n
    if sum(weights) != n * target_weight:
        raise ValueError('sum(weights) must be a multiple of len(weights).')

    # Initially, every item's alternative is itself.
    alternates = list(range(n))
    keep_weights = [0] * n

    # Scan for needy items and donors. First pass will handle all
    # initially-needy items. Second pass will handle any remaining items that
    # started as donors but become needy due to over-donation (though some may
    # also be handled during the first pass).
    donor_position = 0
    for _ in range(2):
        for i in range(n):
            # Is this a needy item?
            if weights[i] >= target_weight:
                continue  # Nope.

            # Find a donor.
            while weights[donor_position] <= target_weight:
                donor_position += 1

            # Donate.
            donated = target_weight - weights[i]
            weights[donor_position] -= donated
            alternates[i] = donor_position
            keep_weights[i] = weights[i]

            # Needy item has been paired. Remove it from consideration.
            weights[i] = target_weight

    return alternates, keep_weights