Перестановки в pari/gp (или где-нибудь еще)

[kthxbye]

Думаю вопрос достаточно простой, однако мне самому с ним справиться не удалось, почему и обращаюсь к уважаемым участникам.

Изначально задаются некие $n,k$, такие, что $0<k\leqslant n$. На их основе задаем $T(i,j)$, значения которой ограничены на интервалах $0<i\leqslant f(n,k)$ и $0<j\leqslant k$. Здесь никаких проблем нет.

Далее, вероятно, необходимо слепить их в строки $a(i)$ с компонентами $T(i,j)$ где $j$ последовательно принимает значения от $1$ до $k$. Для каждой такой строки мы создаем $k!$ строк со всеми возможными перестановками длины $k$. Они нужны нам, чтобы сформировать два типа строк:

• $b(q)$ для исходной $a(i)$ ($i$ фиксировано) пересортированной с помощью $q$-ой перестановки
• $c(q)$ для обратной $q$-ой перестановки

Далее каждый компонент строк обоих типов проверяется на некоторые условия, в результате чего каждому компоненту присваивается новое значение и мы получаем два новых типа строк $b_1(q)$ и $c_1(q)$. Компоненты этих строк проверяются на полное соответствие, все что не совпадает - отбрасываем. На основе оставшихся мы вычисляем значения двух новых параметров:

• $R(i,j)$ для количества перестановок $b(q)$ с $1$ на $j$-ой позиции
• $S(i,j)$ для количества перестановок $b(q)$ с $k$ на $j$-ой позиции

Все, собственно, ради них. Вывод отсеянных перестановок не представляет особого интереса (разве что для примеров, но это не обязательно). Буду очень признателен за любую помощь.

[wrest]

Надо как-то есть слона по частям.
Какую часть вы уже съели?

[kthxbye]

wrest в сообщении #1401515 писал(а):

Надо как-то есть слона по частям.
Какую часть вы уже съели?

Определенные подвижки есть, но они, конечно, незначительны. Просматривая ваш пост в теме Знакочередование a(n)=a(22+n), где вы мне тогда очень помогли, я заметил, что следующую часть

kthxbye в сообщении #1401486 писал(а):

необходимо слепить их в строки $a(i)$ с компонентами $T(i,j)$ где $j$ последовательно принимает значения от $1$ до $k$

без труда можно задать, как a(i)=vector(k,j,T(i,j)). Ну и сами перестановки вместе с $c(q)$ можно генерировать через p(q)=numtoperm(k,q-1) и c(q)=numtoperm(k,q-1)^(-1) соответственно. Сдвиг на единицу просто для удобства (странно, что они выводятся с нуля). Пересортировать одну строку одной перестановкой тоже не составляет труда. А вот как сразу всеми (ну т.е. последовательно) - не понятно.

[wrest]

kthxbye в сообщении #1401647 писал(а):

А вот как сразу всеми (ну т.е. последовательно) - не понятно.

Я не понял.
Надо чтобы вы сформулировали вопрос четко.
Что есть (исходные данные), что надо получить (результат).
"Сразу всеми" обычно делают циклом for, перебирая последовательно "все".

[kthxbye]

wrest в сообщении #1401660 писал(а):

kthxbye в сообщении #1401647 писал(а):

А вот как сразу всеми (ну т.е. последовательно) - не понятно.

Надо чтобы вы сформулировали вопрос четко.
Что есть (исходные данные), что надо получить (результат).

Постараюсь, если что уточняйте и поправляйте.

• Есть заданное количество (пусть будет m) массивов a(i) из k элементов, напр. a(1)=[1,2,3,4,5], a(2)=[2,4,6,8,10] и т.д. Есть также k! перестановок p(q).
• Первым важным промежуточным результатом будет получение m*k! массивов b1(q), b2(q), ..., bm(q).
• Массив b1(1) - это пересортированный a(1) (его копия) с помощью p(1).
• Массив b1(2) - это пересортированный a(1) (его копия) с помощью p(2) и т.д. до b1(k!).
• Массив b2(1) - это пересортированный a(2) (его копия) с помощью p(1) и т.д. до bm(k!).

Остановимся пока на этом. Тут мог быть огромный пост, который куда больше стартового и куда запутаннее. Поэтому наверное лучше разбить на этапы.

[wrest]

kthxbye в сообщении #1401684 писал(а):

Массив b1(1) - это пересортированный a(1) (его копия) с помощью p(1).

1. Индексы в pari/gp заключаются в квадратные скобки, т.е. $a_i$ элемент адресуется как a[i]
2. Напишите функцию resort(v1,v2) в которую передаются два вектора v1 и v2, а возвращается "пересортированный" вектор. То есть вызываться функция должна так:
v_sorted=resort(v1,v2)

Для справки: длина вектора (количество элементов) определяется оператором "решетка", то есть например есть вектор v=[8,7,5,3] в котором 4 элемента. Тогда
? v=[8,7,5,3];
? n=#v;
? print(n)
4

[kthxbye]

wrest в сообщении #1401691 писал(а):

1. Индексы в pari/gp заключаются в квадратные скобки, т.е. $a_i$ элемент адресуется как a[i]

Возможно тут опять возникла какая-то двусмысленность. Есть массивы, их m штук, в каждом по k компонентов (т.е. элементов?). Мы их нумеруем как a(i), i=1..m. Т.е. задаются они допустим как for(i=1,m,a(i)=vector(k,j,T(i,j))), а компоненты для конкретного массива мы можем обратно извлечь через for(j=1,k,print1(a(3)[j],", ")).

wrest в сообщении #1401691 писал(а):

Напишите функцию resort(v1,v2)

Не распознает. Вы случайно не используете какие-нибудь специальные библиотеки?

Возможно я также некорректно использовал слово "пересортировка". Вспомните пример из лс:

wrest писал(а):

vc=vs -- инициализируем выходной массив, в котором в итоге будет наша перестановка
vp=numtoperm(5,4) -- генерируем перестановку
for(i=1,5,vс[i]=vs[vp[i]]) -- переставляем

Мне нужно сделать то же самое, но много раз, т.е.

• for(i=1,m,b(i,q)=a(i))
• p(q)=numtoperm(k,q-1)
• for(i=1,m,for(q=1,k!,for(j=1,k,b(i,q)[j]=a(i)[p(q)[j]])))

Последнюю строку программа считает некорректной.

[wrest]

kthxbye в сообщении #1401771 писал(а):

Возможно тут опять возникла какая-то двусмысленность. Есть массивы, их m штук, в каждом по k компонентов (т.е. элементов?). Мы их нумеруем как a(i), i=1..m.

Индексы заключаются в квадратные скобки! В вашей записи a(i) является функцией, которая берет на вход аргумент i, т.е. где-то раньше должно быть описание этой функции, a(i)=.... В круглых скобках передаются аргументы в функции.
Смотрите:
? m=matrix(2,3); - делаем матрицу из двух строк и трех столбцов, заполненной нулями
? m[1,3]=1;присваиваем единицу элементу матрицы
? m
%1 =
[0 0 3]

[0 0 0]
Видите?

Давайте разбираться с самого начала -- задания структуры данных и исходных данных.

kthxbye в сообщении #1401771 писал(а):

Возможно я также некорректно использовал слово "пересортировка". Вспомните пример из лс:

Вот и посмотрите на него -- как там используются круглые скобки и как квадратные.

-- 27.06.2019, 12:54 --

С другой стороны, вы можете создать вектор, компоненты которого будут векторами.
Например:
? v=vector(3,i,vector(2,k,0));
Тогда обращения к элемента можно делать так:
Печатаем наш v
? v
%1 = [[0, 0], [0, 0], [0, 0]]
меняем элемент на единицу:
? v[2][2]=1;
? v
%1 = [[0, 0], [0, 1], [0, 0]]

-- 27.06.2019, 13:09 --

kthxbye в сообщении #1401771 писал(а):

Есть массивы, их m штук, в каждом по k компонентов (т.е. элементов?). Мы их нумеруем как a(i), i=1..m. Т.е. задаются они допустим как for(i=1,m,a(i)=vector(k,j,T(i,j))),

Тогда давайте так.
Пусть a у нас будет вектором, состоящим из векторов.
? m=10 пусть будет 10 векторов
? k=5 каждый из которых состоит из 5 чисел.
инициализируем так
a=vector(m,i,vector(k))
теперь a[1] - это вектор, состоящий из 5 чисел
a[2][3] - это 3-е число во 2-м векторе.

Что у вас за T(i,j) - что делает эта функция, что возвращает?

[kthxbye]

Индексы в квадратных и вектор из векторов, хорошо. Чем последнее может нам помочь?

wrest в сообщении #1401781 писал(а):

Что у вас за T(i,j) - что делает эта функция, что возвращает?

В идеале она должна возвращать j-ый элемент из i-того сочетания без повторений из n элементов {0..n-1} по k, где все элементы расположены в порядке возрастания. Задается все это очень простой логической схемой, к которой у Excel претензий нет, а вот pari ругается.

[wrest]

kthxbye в сообщении #1401824 писал(а):

Задается все это очень простой логической схемой
,

Ok, можете дать несколько значений T?

Или попробуйте:
T(i,j,n,k)={
if(i>binomial(n,k), return(0));
if(j>k, return(0));
if(i<=1,return(j-1));
if(j==k,if(T(i-1,j,n,k)==n-k+j+1,return(T(i,j-1,n,k)+1),return(T(i-1,j,n,k)+1),return(T(i-1,j,n,k))))}

[kthxbye]

wrest в сообщении #1401838 писал(а):

Ok, можете дать несколько значений T?

Что-то я не вижу где можно прикрепить файл Excel'а, так что вот вам раз и два, ну и формулы для первой строки и остальных:

D6=ЕСЛИ(D$5<=$C$3;D$5-1;"")
D7=ЕСЛИ($B7<=$C$4;ЕСЛИ(D$5<=$C$3;ЕСЛИ(D$5=$C$3;ЕСЛИ(D6=$C$2-1-$C$3+D$5;C7+1;D6+1);ЕСЛИ(E6=$C$2-1-$C$3+E$5;ЕСЛИ(D6=$C$2-1-$C$3+D$5;C7+1;D6+1);D6));"");"")

На pari выдача неправильная, не уверен почему, возможно это как-то связано с "нулевым" столбцом.

Приятно видеть вашу оперативную помощь. Мой основной вопрос до сих пор вызывает у вас сомнения?

[wrest]

kthxbye
Дайте несколько ненулевых значений, типа T(1,2,3,4)=5

kthxbye в сообщении #1401876 писал(а):

На pari выдача неправильная, не уверен почему, возможно это как-то связано с "нулевым" столбцом.

Да, там в одном месте скобка неправильно стоит, вот так вроде правильно:
T(i,j,n,k)={
if(i>binomial(n,k), return(0));
if(j>k, return(0));
if(i<=1,return(j-1));
if(j==k,if(T(i-1,j,n,k)==n-k+j+1,return(T(i,j-1,n,k)+1),return(T(i-1,j,n,k)+1)),return(T(i-1,j,n,k)))}

-- 27.06.2019, 18:37 --

kthxbye в сообщении #1401876 писал(а):

ну и формулы для первой строки и остальных:

Не, я в этом копаться несогласный
Кстати, вопрос вам: вы хотите сделать T() функцией (т.е. вычислять значения по надобности), или сделать его массивом и предзаполнить?

kthxbye в сообщении #1401876 писал(а):

Мой основной вопрос до сих пор вызывает у вас сомнения?

Да, я пока не понял чего вы хотите, поэтому идём последовательно.

-- 27.06.2019, 18:50 --

kthxbye в сообщении #1401876 писал(а):

возможно это как-то связано с "нулевым" столбцом.

Пока, как написана функция T(i,j,n,k), там нет никаких столбцов. Функция берет на вход четыре числа и возвращает число-значение функции.

[kthxbye]

wrest в сообщении #1401877 писал(а):

Да, там в одном месте скобка неправильно стоит, вот так вроде правильно:

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

Окончательный вариант вот такой:

T(i,j,n,k)={
if(i>binomial(n,k), return(0));
if(j>k, return(0));
if(i==1,return(j-1));
if(i>1,if(j==k,if(T(i-1,j,n,k)==n-k+j-1,return(T(i,j-1,n,k)+1),return(T(i-1,j,n,k)+1)),if(T(i-1,j+1,n,k)==n-k+j,if(T(i-1,j,n,k)==n-k+j-1,return(T(i,j-1,n,k)+1),return(T(i-1,j,n,k)+1)),return(T(i-1,j,n,k)))),return(0))}

Проверил через

a=vector(binomial(n,k),i,vector(k,j,T(i,j,n,k)))
print(a)

выдает абсолютно правильно.

wrest в сообщении #1401877 писал(а):

Не, я в этом копаться несогласный

Я когда сегодня отыскал этот файл, тоже сначала испугался, но достаточно 5-10 минут (по крайней мере мне) и все страхи рассеиваются.

wrest в сообщении #1401877 писал(а):

Кстати, вопрос вам: вы хотите сделать T() функцией (т.е. вычислять значения по надобности), или сделать его массивом и предзаполнить?

Вот это очень хороший вопрос, поскольку при выводе a=vector(binomial(n,k),i,vector(k,j,T(i,j,n,k))) уже для n=6 и k=3 программа впадает в долговременный ступор.

[wrest]

kthxbye в сообщении #1401908 писал(а):

программа впадает в долговременный ступор.

Слишком много рекурсий и повторных вычислений, надо упрощать расчет T(i,j,n,k)

Upd А, ну так конечно! Не надо рекурсий, просто вычисляйте построчно/постолбцово, все будет быстро.
Т.е. делаете заполненный нулями массив, а потом циклом for идите по нему.

-- 27.06.2019, 21:22 --

kthxbye в сообщении #1401908 писал(а):

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

Я потом заметил. Но исправить не смог...

[wrest]

kthxbye
Если вам нужен генератор всех сочетаний (без учета порядка) из $n$ по $k$, то вот он:

v_comb(n,k)={
my(C_nk=binomial(n,k),v=vector(C_nk,i,vector(k)),p=0);
for(j=1,k,v[1][j]=j);
p=k;
for(i=2,C_nk,
   v[i]=v[i-1];
   if(v[i][k]==n,p=p-1,p=k);
   for(j=p,k,v[i][j]=v[i-1][p]+1+j-p));
return(v)}

Работает так:
? a=v_comb(6,3);print(a)
[[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 2, 6], [1, 3, 4], [1, 3, 5], [1, 3, 6], [1, 4, 5], [1, 4, 6], [1, 5, 6], [2, 3, 4], [2, 3,
5], [2, 3, 6], [2, 4, 5], [2, 4, 6], [2, 5, 6], [3, 4, 5], [3, 4, 6], [3, 5, 6], [4, 5, 6]]
У вас, кажись, элементы нумеруются от нуля, если это принципиально, можно вычесть единицу отовсюду.