Перманент матрицы : Олимпиадные задачи (М) - Страница 2 fixfix
2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4  След.
 
 Re: Перманент матрицы
Сообщение04.07.2023, 19:28 
Заслуженный участник


12/08/10
1681
$f_{4,0}=24x^4$
$f_{4,1}=6x^3+18x^2$
$f_{4,2}=6x^2+40x+16$
$f_{4,3}=19x+133$
$f_{4,4}=209$
Похоже работает.

 Профиль  
                  
 
 Re: Перманент матрицы
Сообщение04.07.2023, 21:07 
Аватара пользователя


22/11/13
02/04/25
549
Кое-как слепил программку на PARI/GP:
Код:
f1(n,l,x)=if(l==0,n!*x^n,f2(n,l,x)+f1(n,l-1,l)-f2(n,l,l))
f2(n,l,m)=if(n>0,my(A=intformal((n-l)^2*f1(n-1,l,x))); sum(j=1,n-l,m^j*polcoeff(A,j)))
f3(n,l,x)=if(l==0,n!*x^n,f1(n,l,x)+f3(n,l-1,l)-f1(n,l,l))
b(n)=f1(n,n,n)

Считает медленно, но значения согласуются. Завтра напишу реализацию с использованием векторов и сравню скорость со своим алгоритмом.

 Профиль  
                  
 
 Re: Перманент матрицы
Сообщение04.07.2023, 21:10 
Модератор
Аватара пользователя


11/01/06
5710
Вот реализация на Sage
Для примера вычисляет несколько первых членов и значение для $n=100$. В онлайне $n=500$ осилить не может, но локально оно тем же кодом вычисляется за 40 секунд.

-- Tue Jul 04, 2023 13:11:43 --

kthxbye в сообщении #1599902 писал(а):
Считает медленно, но значения согласуются.

Это из-за рекурсии. Либо разверните ее в цикл, либо используйте мемоизацию.

-- Tue Jul 04, 2023 13:22:21 --

Null в сообщении #1599836 писал(а):
maxal, нужно чтобы кто-нибудь проверил хотя-бы.

Проверка прошла успешно.

 Профиль  
                  
 
 Re: Перманент матрицы
Сообщение04.07.2023, 21:34 


05/09/16
12152
maxal в сообщении #1599904 писал(а):
Вот реализация на Sage

Вам, как зачинателю темы «интерактивный курс: введение в программирование на PARI/GP» самое то написать на pari :)

 Профиль  
                  
 
 Re: Перманент матрицы
Сообщение04.07.2023, 21:46 
Модератор
Аватара пользователя


11/01/06
5710
wrest, именно это kthxbye пообещал сделать.

 Профиль  
                  
 
 Re: Перманент матрицы
Сообщение05.07.2023, 11:38 
Аватара пользователя


22/11/13
02/04/25
549
Вот реализация с использованием массивов:
Код:
f1(n,l,m,A)=sum(j=0,n-l,m^j*polcoeff(A,j))
f2(n,l,m,A)=my(B=(n-l)^2*intformal(A)); sum(j=1,n-l,m^j*polcoeff(B,j))
b(n)=my(v1, v2); v1=vector(n+1,i,i--; i!*x^i); v2=v1; for(i=1,n,for(j=i,n,v2[j+1]=f2(j,i,x,v2[j])+f1(j,i-1,i,v1[j+1])-f2(j,i,i,v2[j])); v1=v2); v1

К сожалению она проигрывает моему алгоритму, поскольку считает гораздо медленнее.

А можно ли на PARI/GP переменной многочлена внутри элемента массива присваивать значение? Причем так, чтобы рядом был (ну т.е. суммировался) многочлен внутри элемента массива, где она остается переменной. Или даже просто не внутри элемента, а скажем внутри какой-нибудь буквы A, которой мы присвоили элемент массива.

 Профиль  
                  
 
 Re: Перманент матрицы
Сообщение05.07.2023, 12:42 
Заслуженный участник


12/08/10
1681
Не знаю точных алгоритмов PARI/GP но сразу 2 вопроса:
1.У вас подсчет многочлена в точке не оптимальный(Надо по схеме Горнера за $O(n)$).
2. При интегрировании будут нецелые коэффициенты(Это замедляет?), надо в начале умножить на $(n-l)^2$ а потом интегрировать.
3. $f2(j,i,x,v2[j])$ -оно что строит сам многочлен по его коэффициентам после интегрирования? $O(n^2)$?
Наверное так быстрее? Ни когда не прогал на PARI/GP. Как сделать for по убыванию?
Код:
f1(n,l,m,A)={s=0;for(j=0,n-l,s=s*m+polcoeff(A,n-l-j));s}
f2(n,l,m,A)=my(B=intformal((n-l)^2*A)); s=0;for(j=0,n-l,s=s*m+polcoeff(B,n-l-j));B-s
b(n)=my(v1, v2); v1=vector(n+1,i,i--; i!*x^i); v2=v1; for(i=1,n,for(j=i,n,v2[j+1]=f1(j,i-1,i,v1[j+1])+f2(j,i,i,v2[j])); v1=v2); v1
b(200)

 Профиль  
                  
 
 Re: Перманент матрицы
Сообщение05.07.2023, 13:30 
Аватара пользователя


22/11/13
02/04/25
549
Null в сообщении #1599961 писал(а):
1.У вас подсчет многочлена в точке не оптимальный(Надо по схеме Горнера за $O(n)$).

Я не математик, а только экспериментатор. Можно то же самое, но более простыми словами? Вы имеете ввиду что надо использовать s?

Null в сообщении #1599961 писал(а):
2. При интегрировании будут нецелые коэффициенты(Это замедляет?), надо в начале умножить на $(n-l)^2$ а потом интегрировать.

Я вынес $(n-l)^2$ за интеграл и проверил. Скорость та же.

Null в сообщении #1599961 писал(а):
3. f2(j,i,x,v2[j]) -оно что строит сам многочлен по его коэффициентам после интегрирования? $O(n^2)$?

Да, тут я чуть-чуть не доглядел. Ваша f3(n,l,A)=intformal((n-l)^2*A) здесь очень кстати.

Null в сообщении #1599961 писал(а):
Наверное так быстрее? Ни когда не прогал на PARI/GP. Как сделать for по убыванию?

Да, использование f3 (и если я правильно понял, то еще и схемы Горнера) ускоряет процесс. Но все равно $500$ первых значений за минуту на моем ноуте прога не считает. Кажется for по убыванию нет, но можно просто вычислять вот так:
Код:
for(j=0,n,v[n-j+1]=A+B)


А зачем вы поправили код? Он же вычислял все правильно:
Код:
f1(n,l,m,A)={s=0;for(j=0,n-l,s=s*m+polcoeff(A,n-l-j));s}
f2(n,l,m,A)=my(B=intformal((n-l)^2*A)); s=0;for(j=0,n-l,s=s*m+polcoeff(B,n-l-j));s
f3(n,l,A)=intformal((n-l)^2*A)
b(n)=my(v1, v2); v1=vector(n+1,i,i--; i!*x^i); v2=v1; for(i=1,n,for(j=i,n,v2[j+1]=f3(j,i,v2[j])+f1(j,i-1,i,v1[j+1])-f2(j,i,i,v2[j])); v1=v2); v1

А вот ваша конечная версия уже дает ошибочные значения.

P.S. Ой, не заметил что вы поменяли f2. Тогда все считается правильно, да.

 Профиль  
                  
 
 Re: Перманент матрицы
Сообщение05.07.2023, 13:34 


05/09/16
12152
kthxbye в сообщении #1599951 писал(а):
А можно ли на PARI/GP переменной многочлена внутри элемента массива присваивать значение? Причем так, чтобы рядом был (ну т.е. суммировался) многочлен внутри элемента массива, где она остается переменной. Или даже просто не внутри элемента, а скажем внутри какой-нибудь буквы A, которой мы присвоили элемент массива.

Допустим у нас в векторе есть коэффициенты полинома $3x^2+2x+10$ и мы хотим вычислить его значение при $x=3$, равное $43$. Это можно сделать так:
? v=[3,2,10];x=3;eval(Pol(v,'x))
%1 = 43
?


-- 05.07.2023, 13:37 --

kthxbye в сообщении #1599965 писал(а):
Кажется for по убыванию нет,

Есть forstep().
? forstep(i=10,1,-1,print1(i," "))
10 9 8 7 6 5 4 3 2 1
?

 Профиль  
                  
 
 Re: Перманент матрицы
Сообщение05.07.2023, 13:45 
Аватара пользователя


22/11/13
02/04/25
549
wrest, благодарю! Оказывается можно даже без вектора с коэффициентами:
Код:
b(n)=my(v1, v2); v1=vector(n+1,i,i--; i!*x^i); v2=v1; for(i=1,n,for(j=i,n,v2[j+1]=my(A=intformal((j-i)^2*v2[j]), f(x)=eval(A), g(x)=eval(v1[j+1])); v2[j+1]=A+g(i)-f(i)); v1=v2); v1

Считает, правда, крайне долго.

 Профиль  
                  
 
 Re: Перманент матрицы
Сообщение05.07.2023, 13:57 
Заслуженный участник


12/08/10
1681
kthxbye в сообщении #1599968 писал(а):
Считает, правда, крайне долго.
Дольше чем было до этого. Оптимизировали.

 Профиль  
                  
 
 Re: Перманент матрицы
Сообщение05.07.2023, 14:41 


05/09/16
12152
kthxbye в сообщении #1599968 писал(а):
Считает, правда, крайне долго.

И крайне неправильно :mrgreen:

 Профиль  
                  
 
 Re: Перманент матрицы
Сообщение05.07.2023, 14:45 
Заслуженный участник


12/08/10
1681
wrest в сообщении #1599975 писал(а):
И крайне неправильно :mrgreen:

Проверяю на сайте https://pari.math.u-bordeaux.fr/gp.html - начало правильное как A204262

 Профиль  
                  
 
 Re: Перманент матрицы
Сообщение05.07.2023, 14:53 


05/09/16
12152
Null в сообщении #1599977 писал(а):
Проверяю на сайте https://pari.math.u-bordeaux.fr/gp.html
- начало правильное как A204262

Повезло просто. ТС использует необъявленный x который неизвестно что. У вас он оказался неинициализированным. А мог бы и не оказаться, как у меня. Например попробуйте
x=5;
b(n)=my(v1, v2); v1=vector(n+1,i,i--; i!*x^i); v2=v1; for(i=1,n,for(j=i,n,v2[j+1]=my(A=intformal((j-i)^2*v2[j]), f(x)=eval(A), g(x)=eval(v1[j+1])); v2[j+1]=A+g(i)-f(i)); v1=v2); v1


Впрочем, замена v1=vector(n+1,i,i--; i!*x^i); на v1=vector(n+1,i,(i-1)!); должна помочь с лишним иксом.

Дальше там вообще "непереводимый фольклор", удивительно что оно вообще работает.

 Профиль  
                  
 
 Re: Перманент матрицы
Сообщение05.07.2023, 15:13 
Аватара пользователя


22/11/13
02/04/25
549
wrest в сообщении #1599978 писал(а):
Дальше там вообще "непереводимый фольклор", удивительно что оно вообще работает.

:mrgreen: :mrgreen: :mrgreen:

wrest в сообщении #1599978 писал(а):
ТС использует необъявленный x который неизвестно что.

Он нужен для вычисления интегралов.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 60 ]  На страницу Пред.  1, 2, 3, 4  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group