Распределить сумму целое с помощью набора слотов настолько равномерно, насколько это возможно

Вопрос задан: 1 год назад Последняя активность: 1 год назад
up 23 down

Я пытаюсь понять элегантный способ реализации распределения количества в заданном набор слотов в питоне.

Например:

7 апельсинов распределены на 4 пластины вернутся:

[2, 2, 2, 1]

10 апельсинов через 4 пластин будут:

[3, 3, 2, 2]

5 ответов

Возможно, для Вашего проекта будут необходимы бесплатные векторные карты. На нашем сайте представлены карты для всех стран.

Реклама

up 40 down accepted

Концептуально, что вы хотите сделать, это вычислить 7 // 4 = 1 а также 7 % 4 = 3. Это означает, что все пластины получают 1 целый апельсин. Остальная часть 3 говорит о том, что три из пластин получить дополнительный оранжевый.

divmod встроенный ярлык для получения обоих количеств одновременно:

def distribute(oranges, plates):
    base, extra = divmod(oranges, plates)
    return [base + (i < extra) for i in range(plates)]

С вашим примером:

>>> distribute(oranges=7, plates=4)
[2, 2, 2, 1]

Для полноты картины, то вы, вероятно, хотите, чтобы проверить, что oranges неотрицательна и plates положительно. Учитывая эти условия, вот некоторые дополнительные тестовые случаи:

>>> distribute(oranges=7, plates=1)
[7]

>>> distribute(oranges=0, plates=4)
[0, 0, 0, 0]

>>> distribute(oranges=20, plates=2)
[10, 10]

>>> distribute(oranges=19, plates=4)
[5, 5, 5, 4]

>>> distribute(oranges=10, plates=4)
[3, 3, 2, 2]
up 15 down

Вы хотите посмотреть на Алгоритм Bresenham в для рисования линий (т.е. распределения X пикселов по ряду Y, как «прямолинейно», насколько это возможно, применение этого к проблеме распределения проста).

Это реализация я нашел вот:

def get_line(start, end):
    """Bresenham's Line Algorithm
    Produces a list of tuples from start and end

    >>> points1 = get_line((0, 0), (3, 4))
    >>> points2 = get_line((3, 4), (0, 0))
    >>> assert(set(points1) == set(points2))
    >>> print points1
    [(0, 0), (1, 1), (1, 2), (2, 3), (3, 4)]
    >>> print points2
    [(3, 4), (2, 3), (1, 2), (1, 1), (0, 0)]
    """
    # Setup initial conditions
    x1, y1 = start
    x2, y2 = end
    dx = x2 - x1
    dy = y2 - y1

    # Determine how steep the line is
    is_steep = abs(dy) > abs(dx)

    # Rotate line
    if is_steep:
        x1, y1 = y1, x1
        x2, y2 = y2, x2

    # Swap start and end points if necessary and store swap state
    swapped = False
    if x1 > x2:
        x1, x2 = x2, x1
        y1, y2 = y2, y1
        swapped = True

    # Recalculate differentials
    dx = x2 - x1
    dy = y2 - y1

    # Calculate error
    error = int(dx / 2.0)
    ystep = 1 if y1 < y2 else -1

    # Iterate over bounding box generating points between start and end
    y = y1
    points = []
    for x in range(x1, x2 + 1):
        coord = (y, x) if is_steep else (x, y)
        points.append(coord)
        error -= abs(dy)
        if error < 0:
            y += ystep
            error += dx

    # Reverse the list if the coordinates were swapped
    if swapped:
        points.reverse()
    return points
up 3 down

Смотрите также more_itertools.distribute, Инструмент третьей стороной и ее исходный код.

Код

Здесь мы распространяем m элементы в n бункеров, один за другим, и каждый бункер кол.

import more_itertools as mit


def sum_distrib(m, n):
    """Return an iterable of m items distributed across n spaces."""
    return [sum(x) for x in mit.distribute(n, [1]*m)]

демонстрация

sum_distrib(10, 4)
# [3, 3, 2, 2]

sum_distrib(7, 4)
# [2, 2, 2, 1]

sum_distrib(23, 17)
# [2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

пример

Эта идея сродни распространение колоды карт среди игроков. Вот начальная игра Блин

import random
import itertools as it


players = 8
suits = list("♠♡♢♣")
ranks = list(range(2, 11)) + list("JQKA")
deck = list(it.product(ranks, suits))
random.shuffle(deck)

hands = [list(hand) for hand in mit.distribute(players, deck)]
hands
# [[('A', '♣'), (9, '♠'), ('K', '♣'), (7, '♢'), ('A', '♠'), (5, '♠'), (2, '♠')],
#  [(6, '♣'), ('Q', '♠'), (5, '♢'), (5, '♡'), (3, '♡'), (8, '♡'), (7, '♣')],
#  [(7, '♡'), (9, '♢'), (2, '♢'), (9, '♡'), (7, '♠'), ('K', '♠')],
#   ...]

где карты распределяются «как можно более равномерно между всеми [8] игроками»:

[len(hand) for hand in hands]
# [7, 7, 7, 7, 6, 6, 6, 6]
up 2 down

Mad Физик ответ совершенен. Но если вы хотите распространять апельсины uniformley на пластинах (например. 2 3 2 3 против 2 2 3 3 в 7 апельсинов и 4 пластины, например), вот простая идея.

Легкий случай

Возьмем пример с 31 апельсинов и 7 пластин, например.

Шаг 1: Вы начинаете как Mad Физики с евклидовым делением: 31 = 4*7 + 3. Поместите 4 апельсинов в каждой пластине и сохранить оставшиеся 3.

[4, 4, 4, 4, 4, 4, 4]

Шаг 2: Теперь у вас есть больше пластин, чем апельсины, и это совсем другое: вы должны распространять тарелки среди апельсинов. У вас есть 7 тарелки и 3 апельсинов осталось: 7 = 2*3 + 1. Вы будете иметь 2 пластин в оранжевый (у вас есть плита слева, но это не имеет значения). Давайте назовем это 2 leap. Начало в leap/2 будет довольно:

[4, 5, 4, 5, 4, 5, 4]

Не так просто дело

Это было легко случай. Что происходит с 34 апельсинов и 7 пластин?

Шаг 1: Вы по-прежнему начинаются как Mad Физик с евклидовой деления: 34 = 4*7 + 6. Поместите 4 апельсинов в каждой пластине и держать остальные 6.

[4, 4, 4, 4, 4, 4, 4]

Шаг 2: Теперь у вас есть 7 тарелки и 6 апельсинов остались: 7 = 1*6 + 1. Вы будете иметь одну пластинку за апельсин. Но ждать .. У меня нет 7 апельсинов! Не бойся, я одолжу тебе яблоко:

[5, 5, 5, 5, 5, 5, 4+apple]

Но если вы хотите некоторое единообразие, вы должны поместить это яблоко в другом месте! Почему бы не попробовать распределить яблоки как апельсины в первом случае? 7 пластин, 1 яблоко: 7 = 1*7 + 0. leap 7, начинаются leap/2, То есть 3:

[5, 5, 5, 4+apple, 5, 5, 5]

Шаг 3. Вы должны мне яблоко. Пожалуйста, дайте мне мое яблоко:

[5, 5, 5, 4, 5, 5, 5]

Подводя итог: если у вас есть несколько апельсинов слева, вы распространяете вершины, иначе вы распространяете долины. (Отказ от ответственности: Я автор этого «алгоритм», и я надеюсь, что это правильно, но, пожалуйста, поправьте меня, если я ошибаюсь!)

Код

Хватит говорить, код:

def distribute(oranges, plates):
    base, extra = divmod(oranges, plates) # extra < plates
    if extra == 0:
        L = [base for _ in range(plates)]
    elif extra <= plates//2:
        leap = plates // extra
        L = [base + (i%leap == leap//2) for i in range(plates)]
    else: # plates/2 < extra < plates
        leap = plates // (plates-extra) # plates - extra is the number of apples I lent you
        L = [base + (1 - (i%leap == leap//2)) for i in range(plates)]
    return L

Некоторые тесты:

>>> distribute(oranges=28, plates=7)
[4, 4, 4, 4, 4, 4, 4]
>>> distribute(oranges=29, plates=7)
[4, 4, 4, 5, 4, 4, 4]
>>> distribute(oranges=30, plates=7)
[4, 5, 4, 4, 5, 4, 4]
>>> distribute(oranges=31, plates=7)
[4, 5, 4, 5, 4, 5, 4]
>>> distribute(oranges=32, plates=7)
[5, 4, 5, 4, 5, 4, 5]
>>> distribute(oranges=33, plates=7)
[5, 4, 5, 5, 4, 5, 5]
>>> distribute(oranges=34, plates=7)
[5, 5, 5, 4, 5, 5, 5]
>>> distribute(oranges=35, plates=7)
[5, 5, 5, 5, 5, 5, 5]
up 0 down

Не знаю, как это работает. Но она возвращает те же результаты

a = 23
b = 17
s = pd.Series(pd.cut(mylist, b), index=mylist)
s.groupby(s).size().values

Ошибка 505

Что-то пошло не так

Попробуйте воспользоваться поиском