Конференция "Прочее" » Количество разбиений на слагаемые?
 
  • xayam © (22.06.18 05:24) [0]
    Допустим, есть какое-то число m=260,
    которое нужно разложить на n=8 разных слагаемых
    (одинаковые слагаемые не допускаются), каждое
    из которых не превосходит s=n^2=64 (лежат в диапазоне от 1 до 64).

    Как найти количество разбиений числа m на n таких слагаемых в общем виде?
  • xayam © (22.06.18 05:31) [1]
    m=n*(n^2+1)/2=260 при n=8
  • xayam © (23.06.18 05:19) [2]
    конечно брутфорс есть алгоритм (и не один),
    но хотелось бы что-нибудь получше
    поскольку на таких числах временные затраты велики
  • KilkennyCat © (23.06.18 09:33) [3]

    >  временные затраты велики

    ну и что? просчитай заранее, занеси в таблицу. исходя из "лежат в диапазоне от 1 до 64"
    это ряд чисел m от 36 до 484, что не так уж много.
  • картман © (23.06.18 11:29) [4]
    Я только за деньги готов - вспоминать надо
  • xayam © (23.06.18 11:34) [5]

    > Я только за деньги готов - вспоминать надо

    да брутфорс там вообще примитивный
    например,

    function min(k,x:Integer):Integer;
    begin
         if k<x then min:=k
         else min:=x;
    end;

    procedure F(x: integer; k: integer; s:string);
    var
     i : integer;
    begin
     if (x = 0) then begin
        //здесь фильтрация вывода - if ...
        Form1.MemoOutput.Lines.Add(s);
     end
     else
        for i := 1 to min(k, x) do
           F(x - i, i, s + ' ' + IntToStr(i));
    end;

    procedure TForm1.Button1Click(Sender: TObject);
    begin
    F(7,7,'');
    ShowMessage(IntToStr(Form1.MemoOutput.Lines.Count));

  • xayam © (23.06.18 11:43) [6]

    > исходя из "лежат в диапазоне от 1 до 64"

    n тоже переменная и n^2 может быть значительно больше 64, поэтому
    я думаю нет смысл заранее рассчитывать - ресурсов не хватит...
  • Sha © (23.06.18 16:31) [7]
    //xayam ©   (22.06.18 05:24)
    //Число m=260 нужно разложить на n=8 разных слагаемых (одинаковые не допускаются),
    //каждое из которых не превосходит s=n^2=64 (лежат в диапазоне от 1 до 64).

    //Количество кортежей (слагаемые упорядочены по величине)
    function xayam(Max, Sum, Count: integer): integer;
    var
     i: integer;
    begin;
     Result:=0;
     if Max>Sum then Max:=Sum;
     if Count>0 then for i:=Max downto 1 do Result:=Result + xayam(i-1, Sum-i, Count-1)
     else if Sum=0 then Result:=1;
     end;

    procedure TForm1.Button1Click(Sender: TObject);
    begin;
     ShowMessage(IntToStr(xayam(64,260,8))); //35154340
     end;
  • xayam © (23.06.18 17:07) [8]

    > Sha ©   (23.06.18 16:31) [7]

    а как вывести получившееся суммы?
    чего-то больно много получается
  • Sha © (23.06.18 17:30) [9]
    Как вывести, не знаю.
    Не думаю, что получится простая формула.

    Так считает немного быстрее за счет исключения последнего цикла:
    function xayam2(Max, Sum, Count: integer): integer;
    var
     i: integer;
    begin;
     Result:=0;
     if Count>1 then begin;
       if Max>Sum then Max:=Sum;
       for i:=Max downto 1 do Result:=Result + xayam2(i-1, Sum-i, Count-1);
       end
     else if (Count=1) and (0<Sum) and (Sum<=Max) then Result:=1;
     end;
  • xayam © (23.06.18 17:36) [10]

    > Sha ©   (23.06.18 17:30) [9]
    > Как вывести, не знаю.
    > Не думаю, что получится простая формула.

    самое интересное что эта задача прямо соотносится с задачей о расстановки ферзей.
    И связано с магической константой квадрата.
    Вот накатал пример
    https://ic.pics.livejournal.com/xayam/26173943/38977/38977_900.png
  • xayam © (23.06.18 17:56) [11]
    там опечатка в координатах, но смысл тот же - сумма координат ферзей дает магическую константу (что легко выводится формульно), однако наоборот неверно - если разложить магическую константу на n слагаемых - это не значит что получившиеся координаты будут координатами не угрожающих друг другу ферзей - необходимо еще вычесть количество диагональных коллизий...
  • xayam © (23.06.18 18:06) [12]

    > Sha ©   (23.06.18 17:30) [9]

    причем основная проблема этих чертовых ферзей - это как раз диагональные коллизии
    Как думаешь их кол-во реально посчитать без генерации самих координат?
  • Sha © (23.06.18 18:07) [13]
    Все давно посчитано.
    Перебором )
  • xayam © (23.06.18 18:09) [14]

    > Sha ©   (23.06.18 18:07) [13]
    > Все давно посчитано.
    > Перебором )

    до n=27 а дальше тупик
    https://oeis.org/search?q=A000170
  • Sha © (24.06.18 16:09) [15]
    Еще немного быстрее (1.25 сек на i7-7700)
    function xayam3(Max, Sum, Count: integer): integer;
    begin;
     Result:=0;
     if Count<=1 then begin;
       if (0<Sum) and (Sum<=Max) then Result:=1;
       end
     else begin;
       if Max>Sum then Max:=Sum;
       while Max>=Count do begin;
         Result:=Result + xayam3(Max-1, Sum-Max, Count-1);
         dec(Max);
         end;
       end;
     end;
  • xayam © (01.07.18 06:50) [16]
    чего-то больно большие числа выдает алгоритм.
    Мне кажется он не учитывает что числа разложения должны быть разными.
    Может переформулировать задачу.
    Например, сколько определителей равных единице существует для матрицы размером n x n.
    Сами элементы матрицы равны или 0 или 1.
    Местоположение 1 определяет координаты ферзя на доске.
    Соответственно единиц ровно n штук в матрице.
    И судя по определению, неединичные определители могут возникать только если в столбце и/или в строке более одной единицы.
  • xayam © (01.07.18 06:57) [17]
    вообще по идее таких определителей должно быть n! (n факториал).

    > Sha

    или нет?
  • xayam © (01.07.18 06:59) [18]

    > И судя по определению, неединичные определители могут возникать
    > только если в столбце и/или в строке более одной единицы.

    а так как количество единиц ограничено то получается
    тогда существует строка или столбец где все элементы нулевые -
    значит и определитель равен нулю
  • xayam © (01.07.18 07:08) [19]
    хотя возможно определитель еще может быть равен -1
    тогда всех определителей равных -1 и 1 ровно n! а сколько равных только единице непонятно.

    ???
  • xayam © (01.07.18 07:16) [20]

    > а сколько равных только единице непонятно

    хотя по идее почти все симметрично и их ровно n!/2-1
    минус один так как единичная матрица (все единицы на диагоналях) не имеет симметричного представления
  • xayam © (01.07.18 07:22) [21]

    > хотя по идее почти все симметрично и их ровно n!/2-1

    опс точнее (n!-1)/2
    но это только если n нечетно.
    Если же n четно то непонятно.
  • Sha © (01.07.18 11:06) [22]
    >xayam ©   (01.07.18 06:50) [16]
    >чего-то больно большие числа выдает алгоритм.

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

    Можно выполнить компьютерную имитацию,
    составить таблицы значений и потом сравнить.

    Можно все это проделать намного быстрее, если отказаться от рекурсии:
    function xayam5(Max, Sum, Count: integer): integer;
    var
     a, b: array of array of integer;
     p: pointer;
     m, s, k, i, v: integer;
    begin;
     Result:=0;
     if (Count<=0) or (Sum<=0) or (Max<=0) then exit;

     if Max>Sum then Max:=Sum;
     SetLength(a,1+Sum,1+Max);
     SetLength(b,1+Sum,1+Max);
     for s:=0 to Sum do for m:=0 to Max do b[s,m]:=0;
     for m:=1 to Max do b[m, m]:=1;
     for k:=2 to Count do begin;
       p:=pointer(a); pointer(a):=pointer(b); pointer(b):=p;
       for s:=0 to Sum do for m:=0 to Max do b[s,m]:=0;
       for s:=k to Sum do begin;
         i:=s; if i>Max then i:=Max;
         for m:=1 to i do begin;
           v:=0;
           for i:=1 to m-1 do v:=v+a[s-m,i];
           b[s,m]:=v;
           end;
         end;
       end;

     for i:=1 to Max do Result:=Result+b[Sum, i];
     end;


    Можно все это проделать до запредельных значений,
    если поменять тип результата на int64.

    Было бы желание.
  • Mystic © (03.07.18 09:20) [23]
    Кешировать надо, у вас много повторений (ИМХО). Например, если рассмотреть 64, 61, а потом 63, 62, то при Max <= 60 у нас будут абсолютно идентичное количество, которое вы честно будете считать два раза. Так что лучше иметь массив 260x64x8, куда записывать уже вычисленные результаты (133k элементов).

    Вообще, такой массив хочется заполнять снизу а не сверху, чтобы избежать проверок, а вычислено ли.
  • Sha © (03.07.18 10:20) [24]
    > Mystic ©   (03.07.18 09:20) [23]

    ... а вот это попробуйте )
  • Mystic © (03.07.18 13:07) [25]
    Попробовал сильно не вникая в оптимизацию

    #include <stdint.h>
    #include <stdio.h>
    #include <string.h>

    #define N 8
    #define SUM 260
    #define MAX 64

    uint64_t cache[N][SUM+1][MAX+1];

    uint64_t phi(void)
    {
       /* No variants if MAX = 0 */
       for (uint64_t n=0; n<N; ++n)
       for (uint64_t sum=0; sum <= SUM; ++sum) {
           cache[n][sum][0] = 0;
       }
     
       
       /* Fill data for N = 1 */
       for (uint64_t max = 1; max <= MAX; ++max)
       for (uint64_t sum = 1; sum <= SUM; ++sum) {
           cache[0][sum][max] = sum <= max;
       }
     
       
       /* Calculate everything */
       for (uint64_t n=1; n<N; ++n)
       for (uint64_t max=1; max <= MAX; ++max)
       for (uint64_t sum=1; sum <= SUM; ++sum) {
           const uint64_t qinclude = sum > max ? cache[n-1][sum-max][max-1] : 0;
           const uint64_t qmiss = cache[n][sum][max-1];
           cache[n][sum][max] = qinclude + qmiss;
       }
     
       
       return cache[N-1][SUM][MAX];
    }

    int main()
    {
       printf("phi(%d, %d, %d) = %lu\n", N, SUM, MAX, phi());
       return 0;
    }




    $ gcc xayam.c -o xayam && time ./xayam
    phi(8, 260, 64) = 35154340

    real 0m0.001s
    user 0m0.001s
    sys 0m0.000s

  • Mystic © (03.07.18 13:08) [26]
    Угадал с ответом?
  • Mystic © (03.07.18 14:03) [27]
  • Sha © (03.07.18 14:27) [28]
    > Mystic ©   (03.07.18 13:08) [26]
    > Угадал с ответом?

    Да, ответ верный и время совпадает.

    Чтобы заметить разницу в скорости потребуется увеличить размерность задачи,
    но тогда упремся в оперативную память и ограничения компилятора.
  • Mystic © (03.07.18 16:37) [29]
    А почему время совпадает?


    > Еще немного быстрее (1.25 сек на i7-7700)


    У меня же получилось 0.001 секунды, при том, что

    $ cat /proc/cpuinfo | grep 'model name' | head -1
    model name : Intel(R) Core(TM) i3-4160 CPU @ 3.60GHz

  • Mystic © (03.07.18 16:50) [30]
    У меня такое чувство, что мы скорее упрёмся в производительность процессора, чем в память.

    У моём примере используется 1085760 byte памяти (мегабайт).

    Если увеличить все параметры в пять раз, а max в 50, мы получим

    $ gcc xayam.c -o xayam && time ./xayam
    sz = 1 332 640 320
    phi(40, 1300, 3200) = 6 182 872 580 981 006 930

    real 0m2.192s
    user 0m1.903s
    sys 0m0.288s



    Т. е. надо около гигабайта памяти и почти переполнение типа uint64_t (30% от MAX_UINT64).
  • Sha © (03.07.18 17:02) [31]
    > Mystic ©   (03.07.18 16:37) [29]
    > А почему время совпадает?

    Это [15], которая с рекурсией, работает больше секунды.
    А время [22], которая без рекурсии, тоже 0 ms.

    Все слагаемые в самом внутреннем цикле суммируются быстро,
    т.к. расположены в памяти последовательно,
    поэтому кеширование сумм может не давать ощутимого выигрыша.
  • Sha © (03.07.18 17:48) [32]
    > Mystic ©   (03.07.18 16:50) [30]
    > Если увеличить все параметры в пять раз, а max в 50, мы получим

    При таких размерах кеш сумм будет очень полезен.

    Кроме того, сам алгоритм вычисления сумм можно
    оптимизировать с учетом длинных циклов,
    т.к. там тоже есть дублирование вычислений.
 
Конференция "Прочее" » Количество разбиений на слагаемые?
Есть новые Нет новых   [118233   +44][b:0][p:0.003]