Разделить число на суммарные компоненты

Ответ 1

Здесь алгоритм:

• Разделите N на m, где N - ваш номер, а m - количество подразделов.
• Завершите результат до его ближайшего значения и присвойте это значение всем подразделам.
• Добавьте один в каждый подраздел, пока значения не будут добавлены к N. В этот момент, если N было 50, а m равно 7, у вас было бы 8, 7, 7, 7, 7, 7, 7
• Перейдите от 1 до N, сделав шаг 2 и добавьте случайное число между -(N-base) и N-base. Добавьте инверсию этого числа в соседний ведро. Если у вас есть нечетное количество ведер, то в последнем ковше вместо добавления инверсии этого числа в соседний ведро добавьте его ко всем другим ковшим распределенным образом, аналогичным шагам 2 и 3. выше.

Производительность: Шаг 1 равен O(1), шаги 2, 3 и 4 составляют O(m), поэтому в целом это O(m).

Ответ 2

Вы можете легко удалить требование минимума, вычитая минимальное время N из числа, создавая N подразделов и добавляя минимум. В вашем примере проблема сводится к разбиению 36 на 7 целых чисел, и вы дали разделить 8,3,6,0,1,3,15.

Остальная часть решения зависит от характера "относительно случайного" требования. Для некоторой минимальной случайности рассмотрите выбор чисел последовательно между 0 и незарасчетной частью (например, между 0 и 36 сначала, набрав 8, затем между 0 и 28, получив 3 и так далее 7 раз). Если этого недостаточно, сначала вам нужно определить случайность.

Ответ 3

вот псевдослучайное решение [обратите внимание, что решение может быть предвзятым, но будет относительно случайным).

input:
n - the number we should sum up to
k - the number of 'parts'
m - minimum

(1) split n into k numbers: x1,x2,...,xk such that x1+...+xk = n, and the numbers 
    are closest possible to each other [in other words, x1 = x2 = ... = n/k where 
    possible, the end might vary at atmost +-1.]
(2) for each number xi from i=1 to k-1:
       temp <- rand(m,xi)
       spread x - temp evenly among xi+1,...,xk
       xi <- temp
(3) shuffle the resulting list.

относительно части 1, например: для n=50, k = 7 вы установите: x1=x2=...=x6=7,x7=8, нет проблем для вычисления и заполнения такого списка линейным временем.

Производительность:

Как сказано, step1 равен O (k).

Шаг 2 с наивной реализацией - O (k ^ 2), но поскольку вы равномерно распределяете результат temp-xi, существует реализация O (k) с простое хранение и изменение delta.

Шаг 3 - просто простая перетасовка, O (k)

Общая производительность: O (k) с дельта-выполнением шага 2

Ответ 4

Ну, я придумал что-то "просто для удовольствия".

Он идет постепенно от minimum до number и заполняет массив секциями N, используя по модулю и случайным образом.

Смотрите здесь jsFiddle.

Он не будет работать, как ожидалось, если для этого числа слишком много разделов. (т.е. number < N(N+1)/2)

Ответ 5

Вот пример Java-кода, создающий запрошенный передел чисел. Это рекурсивный подход, мы разлагаем задачу на две подзадачи: если мы хотим разложить число в сумму компонентов среди n корзин, то мы попытаемся рассмотреть поднабор за раз, и для каждого из них делегировать обнаружение оставшегося разложения до рекурсивного вызова для перераспределения среди (n-1) корзин. Запрашиваемый порог считается при обработке определенного поднабора (в цикле for).

import java.util.ArrayList;
import java.util.List;

public class TestFigures {

    public static List<List<Integer>> computeRepartitionNumber(int number_to_decompose, int number_of_subnumbers, int threshold_number) {
        List<List<Integer>> resultRec = new ArrayList<>();

        if (number_of_subnumbers == 1) {
            List<List<Integer>> resultEnd = new ArrayList<>();
            ArrayList<Integer> unitary = new ArrayList<>();
            resultEnd.add(unitary);
            unitary.add(number_to_decompose);
            return resultEnd;
        }

        for (int i = threshold_number; i <= number_to_decompose-threshold_number; i++) {
            int remain = number_to_decompose - i;
            List<List<Integer>> partialRec = computeRepartitionNumber(remain, number_of_subnumbers - 1, threshold_number);
            for(List<Integer> subList : partialRec){
                subList.add(i);             
            }
            resultRec.addAll(partialRec);
        }
        return resultRec;

    }

    public static void main(String[] args) {
        List<List<Integer>> superlist = computeRepartitionNumber(5, 2, 1);
        System.out.println(superlist.size());
        System.out.println(superlist);

    }

}

Ответ 6

import random

def split_given_number_into_n_random_numbers(number, number_of_subsections, min_random_number_desired = 0):
    cumulative_sum_of_random_numbers = 0
    current_subsection = 1
    max_random_number = int(number/number_of_subsections)
    if min_random_number_desired > max_random_number:
        print("ERROR: Cannot have min number as {} and split {} in {} subsections".format(min_random_number_desired,
                                                                                          number, number_of_subsections))
        return False

    while (True):
        random_number = random.randint(min_random_number_desired, max_random_number)
        print("Random number {} = {}".format(current_subsection, random_number))
        cumulative_sum_of_random_numbers += random_number
        # print("Cumulative sum {}".format(sum_of_num))
        number -= random_number
        current_subsection += 1
        if current_subsection == number_of_subsections:
            random_number = number
            print("Random number {} = {}".format(current_subsection, random_number))
            cumulative_sum_of_random_numbers += random_number
            break

    print("Final cumulative sum of random numbers = {}".format(cumulative_sum_of_random_numbers))
    return True

if __name__ == '__main__':
    split_given_number_into_n_random_numbers(50, 7, 2)

Теперь, если вы хотите, чтобы минимальное число было чем-то другим, кроме 2, измените его на любое значение, указанное number_of_subsections * min_random_number_desired <= number.