Разбить число на составляющие суммы - PullRequest
Новая
       29

Разбить число на составляющие суммы

15 голосов
/ 17 октября 2011

Существует ли эффективный алгоритм для разбиения числа на подразделы N, чтобы сумма чисел складывалась в исходное с базовым минимумом? Например, если я хочу разделить 50 на 7 подразделов и иметь базовый минимум 2, я могу сделать 10,5,8,2,3,5,17 (как и любое другое количество комбинаций). Я хотел бы, чтобы числа были целыми и относительно случайными, но я не уверен, как эффективно генерировать числа, которые суммируют до оригинала и не включают числа ниже заданного минимума. Есть предложения?

РЕДАКТИРОВАТЬ - просто чтобы скопировать / вставить мой комментарий, целые числа не обязательно должны быть уникальными, но я хочу избегать одинакового размера для всех из них (например, 50, разделенных на 10 одинаковых размеров) каждый раз.

Ответы [ 9 ]

14 голосов
/ 17 октября 2011

Вот алгоритм:

  1. Разделите N на m, где N - ваше число, а m - количество подразделов.
  2. Округление результатадо его ближайшего значения и присвойте это значение всем подразделам.
  3. Добавляйте по одному в каждый подраздел, пока значения не составят N.На этом этапе, если N было 50, а m было 7, у вас было бы 8, 7, 7, 7, 7, 7, 7
  4. Итерация от 0 до m-1 с шагом 2и добавьте случайное число от -(currentValue-base) до currentValue-base.Добавьте обратное число к соседнему ведру.Если у вас есть нечетное количество сегментов, то в последнем блоке вместо добавления инверсии этого числа к соседнему сегменту добавьте его ко всем другим сегментам распределенным образом, аналогично шагам 2 и 3 выше.

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

5 голосов
/ 17 октября 2011

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

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

4 голосов
/ 17 октября 2011

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

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, нет проблем для вычисления и заполнения такого списка с линейным временем.

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

Как уже было сказано, шаг1 - это O (k).

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

Step3 - это просто случайное перемешивание, O (k)

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

2 голосов
/ 25 сентября 2017

Вот пример кода Java, создающего запрошенное перераспределение чисел. Это рекурсивный подход, мы разбиваем задачу на 2 подзадачи: если мы хотим разложить число на сумму компонентов в 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);

    }

}
2 голосов
/ 17 октября 2011

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

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

См. JsFiddle здесь.

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

1 голос
/ 24 февраля 2018 
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. </p>

0 голосов
/ 11 июля 2018

Я работал над чем-то похожим, и вот что я придумал.

Вы можете сделать это в O (N-1) , используя некоторые вычисления на каждом шаге. Вы начинаете с выбора случайного числа между минимальным и максимальным числом для каждого места. Для каждого пятна максимальное число рассчитывается путем вычитания (Min_Number * Remaining_Spots) из Остаточного баланса.

Например: для первого места вы выбираете число от 2 до 38. Вы получаете это, вычитая (7-1) * 2 из 50. То есть 50 - 12 = 38.

Как только вы выберете число, скажем, 19, то для следующего места диапазон будет 2-21. то есть 50-19- (5 * 2) = 21 ..

.. и т. Д.

Вот фрагмент кода: 

function splitNumIntoXRandomComponents(num, x, min_num) {

var components = [];    

var count = 1;
var cumulative = 0;
var balance = num;

for (var i = 0; i<x-1; i++) {

    //max num for this spot
    var max_num = balance - ((x-count)*min_num);

    //to avoid big numbers in the beginning and min numbers at the end
    if (Math.random() > 0.5){ //0.5 can be tuned to your liking 
        max_num = Math.floor(max_num / 2) + min_num;
    }

    //generate the number for the spot at 'count'
    var c = Math.floor(Math.random()*(max_num-min_num+1)+min_num);

    //adjust balances
    cumulative += c;
    balance -= c;       
    count++;    

    //store this number
    components.push(c);                     

}

//push remaining balance into the last spot
components.push(balance);

//print numbers
console.log(components);

}

for (var i=0; i<10; i++) {
    splitNumIntoXRandomComponents(50, 7, 2);
}

Вот пример вывода: 

[34, 2, 4, 3, 3, 2, 2]
[14, 12, 8, 8, 4, 2, 2]
[7, 4, 26, 5, 2, 3, 3]
[8, 2, 16, 4, 4, 9, 7]
[20, 8, 4, 4, 7, 4, 3]
[3, 34, 4, 2, 2, 2, 3]
[10, 5, 15, 2, 7, 5, 6]
[6, 3, 10, 4, 10, 3, 14]
[31, 4, 2, 3, 5, 2, 3]
[7, 5, 2, 9, 9, 2, 16]

Вот jsFiddle: http://jsfiddle.net/wj81kvsc/6/

0 голосов
/ 30 мая 2018

Позвольте мне написать это на Python.

Допустим, у вас есть 50 элементов, которые нужно разбить на 7 блоков, и вы хотите по крайней мере два элемента внутри каждого из них. 

N_init = 50
s = 2
m = 7

Мы помещаем s элементов по умолчанию в каждый блок, чтобы у нас осталось N элементов. 

N = N_init - s*m

Мы рисуем m случайных чисел, сортируем их, добавляем N на обороте. Это похоже на случайную вставку m закладок в книгу из N страниц. Количество страниц между последовательными закладками является случайным. (У нас было s, поэтому мы уверены, что в каждом боксе есть хотя бы s элементов) 

a = sorted([random.randint(0,N+1) for i in range(m)])
a.append(N)
result = [j-i+s for(i,j) in zip(a[0:m],a[1:m+1])]

Готово!

0 голосов
/ 01 марта 2018

Я знаю, что прошло много времени, но я хотел бы добавить свой ответ, чтобы помочь кому-то, вот мой код, использующий рекурсию 

#include <stdio.h>
#include <stdlib.h>

void print(int n, int * a) {
int i ; 
for (i = 0; i <= n; i++) {
    printf("%d", a[i]); 
   i < n ? printf(" + ") : printf("");
}
printf("\n"); 
}

void integerPartition(int n, int * a, int level){
int first; 
int i; 
if (n < 1) return ;    
    a[level] = n;
print(level, a);
first = (level == 0) ? 1 : a[level-1];
for(i = first; i <= n / 2; i++){
    a[level] = i; 
    integerPartition(n - i, a, level + 1);
}
}
int main(int argc, char ** argv){
int n = 10;     
int * a = (int * ) malloc(sizeof(int) * n); 
integerPartition (n, a, 0); 
return(0);
}

Здесь n равно 10, но вы можете сделать его следующим образомспрашивая пользователя, объявите размер с помощью оператора new!

...