2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Мультивектора в PARI/GP
Сообщение01.11.2023, 09:15 


20/02/20
83
Здравствуйте.Полгода не садился за PARI,а сейчас понадобилась одна задачка и оказалось,кое-что основательно подзабыл.Пусть задан мультивектор из векторов произвольной длины
$\mathbf{v=[[a_1,a_2,...a_n],[b_1,b_2,...b_m],...[c_1,c_2,...c_k]]}$. Требуется составить другой мультивектор из векторов равной длины,состоящих из элементов векторов первого мультивектора,взятых из каждого вектора ровно по одному разу,т.е.
$\mathbf{v_1=[[a_1,b_1,...c_1],[a_1,b_1,...c_2],...[a_1,b_1,...c_k],...[a_2,b_1,...c_1],...[a_n,b_m,...c_k]]}$.
Возможно это сделать на PARI ?

 Профиль  
                  
 
 Re: Мультивектора в PARI/GP
Сообщение01.11.2023, 12:10 


05/09/16
12108
genk
А можно пример? Пусть дан такой вектор
? v=[[1],[2,3,4],[5,6],[7,8,9,10]];
?

Какой должен получиться в итоге?
Для вспоможения:
1. Количество субвекторов в мультивекторе
? vc=#v
%2 = 4

Количество элементов в субвекторах:
? v1=vector(#v,i,#v[i])
%3 = [1, 3, 2, 4]
?


А... я кажется начинаю понимать. Тут комбинаторная задача (перечислительной комбинаторики) на генерацию хитрых размещений.
То есть если "в лоб" то нужен вложенный цикл с глубиной вложенности равной количеству субвекторов, но код должен быть универсальным и генерировать размещения для разного количества субвекторов. Так? Если количество субвекторов фиксировано, то всё тривиально.

 Профиль  
                  
 
 Re: Мультивектора в PARI/GP
Сообщение01.11.2023, 16:07 


05/09/16
12108
genk
Кажись, можно так:
Код:
genk(v)=my(v1=vector(#v,i,#v[i]),vc=#v1,vp=vecprod(v1),vres=vector(vp,i,vector(vc)));for(i=1,vp,for(j=1,vc,vres[i][j]=v[j][(i-1)\prod(k=j+1,vc,v1[k])%v1[j]+1]));return(vres)
Функция genk(v) берет на вход мультивектор и возвращает то, что вы хотите.
Пример:
? genk([[1,2],[3],[4,5,6]])
%1 = [[1, 3, 4], [1, 3, 5], [1, 3, 6], [2, 3, 4], [2, 3, 5], [2, 3, 6]]
?


Там сперва вычисляется какой длины и сколько всего будет подвекторов в возвращаемом мультиветоре, затем по номеру подвектора выходного мультивектора вычисляются индексы элементов из исходных подвекторов исходного мультиветора, и одновременно заменется одно на другое. Таким образом, входной мультиветор может состоять из чего угодно (столов, стульев и кружек, например).
? genk([["стул1","стул2"],["стол"],["кружка1","кружка2","кружка3"]])
%1 = [["стул1", "стол", "кружка1"], ["стул1", "стол", "кружка2"], ["стул1", "стол", "кружка3"], ["стул2", "стол", "кружка1"], ["стул2", "стол", "кружка2"], ["стул2", "стол", "кружка3"]]
?


Проверок на корректность исходных данных (что на входе действительно непустой мультиветор непустых подвекторов, а не что-то ещё) не производится.

 Профиль  
                  
 
 Re: Мультивектора в PARI/GP
Сообщение02.11.2023, 10:44 


20/02/20
83
wrest
Да,все работает как надо,спасибо.Хорош трюк с заменой индексов,буду иметь ввиду.Только выходной мультивектор я бы назвал не vres,а wrest :D

 Профиль  
                  
 
 Re: Мультивектора в PARI/GP
Сообщение02.11.2023, 11:33 


05/09/16
12108
genk в сообщении #1615737 писал(а):
Хорош трюк с заменой индексов,буду иметь ввиду.

Он бывает весьма удобен когда надо что-то переставлять местами, подбирать, размещать, перечислять и т.п.
Я сначала написал два прохода - на первом формируется мультивектор из индексов, а потом по индексам наполняются значения в другом мультивекторе. Но затем решил совместить, для компактности кода и расхода памяти.
Но "трюк" тут скорее в другом - в пересчёте порядкового номера подвектора в конкретное размещение. В перечислительных задачах как раз основная сложность в том, как всё перечислить и ничего не забыть. Часто мы знаем сколько у нас должно получиться комбинаций, т.к. вычислительные комбинаторные задачи как правило проще перечилительных - или есть замкнутая формула или на худой конец рекуррентная. Здесь формула замкнутая - это произведение количеств элементов подвекторов исходного вектора. А вот придумать соответствие номера комбинации (в нашем случае - размещения) его составу - это как раз "трюк".

 Профиль  
                  
 
 Re: Мультивектора в PARI/GP
Сообщение03.11.2023, 20:46 


20/02/20
83
wrest в сообщении #1615741 писал(а):
А вот придумать соответствие номера комбинации (в нашем случае - размещения) его составу - это как раз "трюк".

Я тут подумал,можно обойтись и без "трюка" с помощью функции forvec. Вот код
Код:
g(v)=my(n=#v,p=prod(k=1,n,#v[k]),u=vector(n,i,[1,#v[i]]),l=[],v1=[]);
forvec(x=u,l=concat(l,x));for(i=0,p-1,v1=concat(v1,[vector(n,j,l[n*i+j])]));
w=vector(p,i,vector(n,j,v[j][v1[i][j]]));return(w)

Пример
Код:
g([[0,1],[1,0],[0,1,2]])
              [[0,1,0],[0,1,1],[0,1,2],[0,0,0],[0,0,1],[0,0,2],[1,1,0],[1,1,1],[1,1,2],[1,0,0],[1,0,1],[1,0,2]]

 Профиль  
                  
 
 Re: Мультивектора в PARI/GP
Сообщение03.11.2023, 21:12 


05/09/16
12108
genk в сообщении #1615989 писал(а):
Я тут подумал,можно обойтись и без "трюка" с помощью функции forvec.

Круто! Действительно, один forvec тут заменяет
wrest в сообщении #1615566 писал(а):
вложенный цикл с глубиной вложенности равной количеству субвекторов,
, мне такое в голову не приходило, надо запомнить.
Ну и w там лишний, можно вроде сразу фориморовать v1 как выходной. Я тоже
wrest в сообщении #1615741 писал(а):
сначала написал два прохода - на первом формируется мультивектор из индексов, а потом по индексам наполняются значения в другом мультивекторе. Но затем решил совместить, для компактности кода и расхода памяти.

Вот у вас как раз два (даже три) прохода - сперва вычисляются индекcы сперва в l, они нарезаются в вектор v1, а потом наполняются значениями уже в w.
А... то есть кажется что и второй проход возможно лишний, а не только третий. Надо подумать 8-)

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



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

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


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

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