Алгоритм разбиения числа

Question

Учитывая положительное целое число X, как можно разделить его на N части, каждая из которых находится между A и B, где A <= B также являются положительными целыми числами?То есть напишите

X = X_1 + X_2 + ... + X_N

, где A <= X_i <= B, а порядок X_i s не имеет значения?

Answer 1

Если вы хотите знать количество способов , чтобы сделать это, тогда вы можете использовать генерирующие функции.

По сути, вы заинтересованы в целочисленных разбиениях .Целочисленное разбиение X - это способ записать X в виде суммы натуральных чисел.Пусть p(n) будет числом целочисленных разбиений n.Например, если n=5, то p(n)=7 соответствует разделам:

5
4,1
3,2
3,1,1
2,2,1
2,1,1,1
1,1,1,1,1

Функция генерации для p(n) равна

sum_{n >= 0} p(n) z^n = Prod_{i >= 1} ( 1 / (1 - z^i) )

Чтоэто вам подходит? Расширив правую сторону и взяв коэффициент z^n, вы можете восстановить p(n).Не беспокойтесь, что продукт бесконечен, поскольку для вычисления p(n) вам понадобится только конечное число терминов.На самом деле, если это все, что вам нужно, просто обрежьте продукт и остановитесь на i=n.

Почему это работает? Помните, что

1 / (1 - z^i) = 1 + z^i + z^{2i} + z^{3i} + ...

Итак, коэффициент z^n - это количество способов записи

n = 1 * a_1 + 2 * a_2 + 3 * a_3 + ...

где сейчасЯ имею в виду a_i как число раз, которое i появляется в разделе n.

Как это обобщается? Легко,как выясняется.Из приведенного выше описания, если вы хотите, чтобы только части раздела были в заданном наборе A, то вместо того, чтобы брать продукт за все i >= 1, принимайте продукт только за i in A.Пусть p_A(n) будет числом целочисленных разделов n, чьи части взяты из набора A.Тогда

sum_{n >= 0} p_A(n) z^n = Prod_{i in A} ( 1 / (1 - z^i) )

Опять же, взяв коэффициент z^n в этом расширении, вы решите вашу проблему.Но мы можем пойти дальше и отследить количество частей раздела.Для этого добавьте еще один заполнитель q, чтобы отслеживать, сколько деталей мы используем.Пусть p_A(n,k) будет числом целочисленных разбиений n на k частей, где части происходят из набора A.Затем

sum_{n >= 0} sum_{k >= 0} p_A(n,k) q^k z^n = Prod_{i in A} ( 1 / (1 - q*z^i) )

, поэтому, принимая коэффициент q^k z^n, мы получим количество целочисленных разбиений n на k частей, откуда эти элементы поступают из набора A.

Как вы можете закодировать это? Подход с использованием функции генерации фактически дает вам алгоритм для генерации всех решений проблемы, а также способ единообразной выборки из набора решений.После выбора n и k произведение справа будет конечным.

Answer 2

Вот решение Python для этой проблемы. Это довольно неоптимизировано, но я постарался сделать его как можно более простым, чтобы продемонстрировать итерационный метод решения этой проблемы.

Результаты этогоМетод обычно представляет собой список максимальных и минимальных значений, возможно, между 1 или 2 значениями.Из-за этого там есть небольшая оптимизация (с использованием abs), которая не позволит итератору постоянно пытаться найти минимальные значения, считая в обратном порядке от max и наоборот.

Существуют рекурсивные способы сделать этоэто выглядит намного более элегантно, но это поможет выполнить работу и, надеюсь, даст вам представление о лучшем решении.

---

СЦЕНАРИЙ:

# iterative approach in-case the number of partitians is particularly large
def splitter(value, partitians, min_range, max_range, part_values):
    # lower bound used to determine if the solution is within reach
    lower_bound = 0
    # upper bound used to determine if the solution is within reach
    upper_bound = 0
    # upper_range used as upper limit for the iterator
    upper_range = 0
    # lower range used as lower limit for the iterator
    lower_range = 0
    # interval will be + or -
    interval = 0

    while value > 0:
        partitians -= 1
        lower_bound = min_range*(partitians)
        upper_bound = max_range*(partitians)
        # if the value is more likely at the upper bound start from there
        if abs(lower_bound - value) < abs(upper_bound - value):
            upper_range = max_range
            lower_range = min_range-1
            interval = -1
        # if the value is more likely at the lower bound start from there
        else:
            upper_range = min_range
            lower_range = max_range+1
            interval = 1

        for i in range(upper_range, lower_range, interval):
            # make sure what we are doing won't break solution
            if lower_bound <= value-i and upper_bound >= value-i:
                part_values.append(i)
                value -= i
                break

    return part_values


def partitioner(value, partitians, min_range, max_range):
    if min_range*partitians <= value and max_range*partitians >= value:
        return splitter(value, partitians, min_range, max_range, [])
    else:
        print ("this is impossible to solve")

def main():
    print(partitioner(9800, 1000, 2, 100))

---

Основная идеяза этим сценарием понимается, что значение должно находиться в пределах от min*parts до max*parts, для каждого шага решения, если мы всегда достигнем этой цели, в конечном итоге мы получим min < value < max для parts == 1, поэтому, если мыпостоянно убирая из значения и удерживая его в этом min < value < max диапазоне, мы всегда найдем результат, если это возможно.

Для примера этого кода он в основном всегда уберет либо max, либо min в зависимости от того, к какой границе ближе value, до тех пор, пока какое-либо не min или max значение останется в качестве остатка.

Answer 3

Простая реализация, которую вы можете сделать, заключается в том, что среднее значение X_i должно быть между A и B, поэтому мы можем просто разделить X на N и затем сделать небольшие корректировки, чтобы распределитьостаток равномерно, чтобы получить правильный раздел.

Вот один из способов сделать это:

X_i = ceil  (X / N)  if i <= X mod N,
      floor (X / N)  otherwise.

Это дает правильное решение, если A <= floor (X / N) и ceil (X / N) <= B.В противном случае, нет решения.См. Доказательства ниже.

---

sum(X_i) == X

Доказательство:

Используйте алгоритм деления для записи X = q*N + r с 0 <= r < N.

• Если r == 0, то ceil (X / N) == floor (X / N) == q, поэтому алгоритм устанавливает все X_i = q.Их сумма составляет q*N == X.

• Если r > 0, то floor (X / N) == q и ceil (X / N) == q+1.Алгоритм устанавливает X_i = q+1 для 1 <= i <= r (т.е. r копий) и X_i = q для оставшихся N - r штук.Таким образом, сумма составляет (q+1)*r + (N-r)*q == q*r + r + N*q - r*q == q*N + r == X.

---

Если floor (X / N) < A или ceil (X / N) > B, то решения не существует.

Доказательство:

• Если floor (X / N) < A, то floor (X / N) * N < A * N, а с floor(X / N) * N <= X, это означает, что X < A*N, поэтому, даже используя только самые маленькие куски, сумма будетбольше чем X.

• Аналогично, если ceil (X / N) > B, то ceil (X / N) * N > B * N, а с ceil(X / N) * N >= X, это означает, что X > B*N, поэтому даже используются только самые большие кускивозможно, сумма будет меньше, чем X.