1

Задача посчитать число возможных комбинаций для массива байт заданной длины, если известна сумма элементов массива:

int GetMutationsCount(int arrLength, int sum);    

к примеру L =2, S =8, count = 9, возможные комбинации:

0  8  
1  7
2  6
3  5
4  4
5  3
6  2
7  1
8  0

к примеру L =3, S = 8, count = 9 + 8 + 7 +6 + 5 + 4 + 2 + 1 = 45

0 0 8              
0 1 7     1 0 7    
0 2 6     ... 6    2 0 6
0 3 5         5    2 1 5    3 0 5
0 4 4         4    ... 4    ...    4 0 4  
0 5 3         3        3           ...    5 0 3 
0 6 2         2        2                          6 0 2 
0 7 1    1  6 1    2 5 1                          ...     7 0 1
0 8 0    1  8 0    2 6 0                                  ...    8 0 0
 

как вывести общую формулу?
в идеале нужно оценить число комбинаций для массивов длиной 64 и 256

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

за алгоритм на С# / java отдельное спасибо

3
  • См. раздел 7.2.1.4 "Искусства программирования" Кнута, том 4А.
    – Harry
    28 мая 2022 в 12:27
  • Да, у вас как, порядок членов играет роль? и допускаются нулевые члены? Допускается, например, 8 = 0+0+0+0+0+0+8 как разбиение из 7 членов? Тогда это не совсем по Кнуту, но Кнут может навести на мысли :)
    – Harry
    28 мая 2022 в 12:34
  • нули допускаются инпут может быть массив из произвольных байт если L=7 то 0+0+0+0+0+0+8 подходит 28 мая 2022 в 12:53

2 ответа 2

4

Можно посчитать.

Обозначим в вашем случае это число представлений как R(n,m) — представлений числа n из m частей.

Очевидно, что R(n,1) = 1 — само число n.

Не менее очевидно (если подумать), что

R(n,m) = R(n,m-1) + R(n-1,m-1) + R(n-2,m-1) + ... + R(0,m-1)

(Количество представлений, начинающихся с 0, с 1, с ..., с n).

Остается только считать...

unsigned long long R(int n, int m)
{
    if (m == 1) return 1;
    unsigned long long s = 0;
    for(int i = 0; i <= n; ++i) s += R(n-i,m-1);
    return s;
}

Правда, в таком виде считать будет ну очень долго... Но если применить мемоизацию - то весьма быстро :)

Я использовал boost для длинной арифметики и посчитал

R(64,32) = 9900582591005555469968805

R(256,128) = 203602220919700916657542151465697367795896339716832636330737569006349813543209142455967648120505774630309

Это просто чтоб было понятно, что без длинной арифметики не обойтись...

А можно и просто формулу записать:

введите сюда описание изображения

С учетом исправления от Stanislav Volodarskiy код выглядит как

unsigned long long R(int n, int m)
{
    if (m == 1) return 1;
    unsigned long long s = 0;
    for(int i = 0; i <= min(n,255); ++i) s += R(n-i,m-1);
    return s;
}

Во избежание переполнения стека можно использовать восходящее ДП, примерно так (с Boost'ом):

#include <vector>
#include <iostream>
#include <boost/multiprecision/cpp_int.hpp>
using large = boost::multiprecision::cpp_int;
//using large = long long int;

using namespace std;

large R(unsigned int n, unsigned int m)
{
    vector<vector<large>> R(2, vector<large>(n+1));
    for(unsigned int i = 0; i <= n; ++i)
        R[0][i] = 0;
    R[0][0] = 1;

    for(unsigned int k = 1; k <= m; ++k)
    {
        for(unsigned int l = 0; l <= n; ++l)
        {
            R[k%2][l] = 0;
            for(unsigned int j = 0; j <= min(l,255u); ++j)
                R[k%2][l] += R[(k-1)%2][l-j];
        }
    }
    return R[m%2][n];
}

int main(int argc, char * argv[])
{
    cout << R(8,2) << endl;
    cout << R(8,3) << endl;
    cout << R(8192,64) << endl;
    cout << R(32768,256) << endl;
}

Те же результаты, что и у Stanislav Volodarskiy, получились суммарно за примерно 41с.

4
  • Вы забыли ограничения на слагаемые - [0, 255]. Это ограничение снижает общее количество. 29 мая 2022 в 21:40
  • @StanislavVolodarskiy Согласен. Но поскольку ему все равно надо считать до 256, то... :)
    – Harry
    30 мая 2022 в 4:15
  • Стократное ускорение если заметить что мы ищем суммы подмассивов и перейти на накопительные суммы. 30 мая 2022 в 16:31
  • @StanislavVolodarskiy Это да, я видел, но... не захотелось ковыряться... :(
    – Harry
    30 мая 2022 в 16:45
2

f(n, s) - число комбинаций n байт с суммой s.

f(n = 0, s =  0) = 1 # ровно один пустой массив с нулевой суммой
f(n = 0, s != 0) = 0 # нет пустых массивов с ненулевой суммой
f(n    , s <  0) = 0 # нет массивов с отрицательными суммами

# перебираем значения первого байта [0, 255] 
f(n, s) = f(n - 1, s) + f(n - 1, s - 1) + ... + f(n - 1, s - 255)

Последняя функция позволяет вычислить комбинации из n байт если известны комбинации для массивов без одного байта.

import java.math.BigInteger;

public class ByteArrayCounter {
    public static void main(String[] args) {
        int n = Integer.parseInt(args[0]);
        int s = Integer.parseInt(args[1]);
        System.out.println(count(n, s));
    }

    private static class Slice {
        private final int min_s;
        private final int max_s;
        private final BigInteger[] values;

        public Slice(int min_s, int max_s) {
            this.min_s = min_s;
            this.max_s = max_s;
            values = new BigInteger[max_s - min_s + 1];
        }

        public void put(int s, BigInteger value) {
            values[s - min_s] = value;
        }

        public BigInteger get(int s) {
            return values[Math.min(Math.max(s, min_s), max_s) - min_s];
        }
    }

    public static BigInteger count(int n, int target) {
        Slice prev = new Slice(0, 1);
        prev.put(0, BigInteger.ZERO); 
        prev.put(1, BigInteger.ONE); 

        for (int k = 1; k <= n; ++k) {
            int min_s = Math.max(0, target - (n - k) * 255);
            int max_s = Math.min(target, 255 * k);
            Slice curr = new Slice(min_s, max_s + 1);

            BigInteger sum = BigInteger.ZERO;
            for (int s = min_s; s <= max_s; ++s) {
                curr.put(s, sum);
                sum = sum.add(prev.get(s + 1).subtract(prev.get(s - 255)));
            }
            curr.put(max_s + 1, sum);
            prev = curr;
        }
        return prev.get(target + 1).subtract(prev.get(target));
    }
}
$ javac ByteArrayCounter.java

$ java ByteArrayCounter 2 8
9

$ java ByteArrayCounter 3 8
45

$ time java ByteArrayCounter 64 8160
9026336239045655001244965373296023105444920683088436131635804094077226110833295302707931885726706613257712644527244047907893777368834358449320418590464

real  0m0.111s
user  0m0.184s
sys   0m0.024s

$ time java ByteArrayCounter 256 32640
10897341114494371171102390425834798313841110593688859167594391356773737286992667718077704666558643734411890674253371174888965746439841827767400663712320877526614540552636601516778532517789699888302122831088753711642851681086577235455694712347258199556937123993807637939401303229753741602912013795360270232412995260890580055145445625454765347778704296531450402318403895128351074924613544802496131603672001322229357896828953535411931321247887018779521144847634566656530685152627684892824858975836784160381128622874905657615087142114702175103656568693367179095144577756562635961430518965203949176730432548612295032576

real  0m0.900s
user  0m0.940s
sys   0m0.168s

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.