def normalize(next_grams_counter):
    """
    For a given n-gram, divide the frequency of each next gram with
    the sum of the frequencies of all the possible next grams.
    :param next_grams_counter: A collections.Counter object about an n-gram
    :return: A list of (gram, probability) tuples.
    """
    s = float(sum(next_grams_counter.values()))
    return [(c, cnt / s) for c, cnt in next_grams_counter.items()]