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

[wrest]

Ну и ещё, в качестве пособия, генератор массива всех перестановок всех сочетаний из n элементов по k
Возвращет вектор, состоящий из $k!C_n^k$ элементов, являющихся векторами, состоящими из $k$ чисел.

v_perm(n,k)={
my(C_nk=binomial(n,k),k_fac=k!,v=vector(C_nk*k_fac,i,vector(k)),v_p=vector(k_fac,i,numtoperm(k,i)),p=0);
for(j=1,k,v[1][j]=j); \\ генерируем первое сочетание 1,2,...k

for(i=2,k_fac,for(j=1,k,v[i][j]=v[1][v_p[i-1][j]])); \\ генерируем перестановки первого сочетания

p=k;
for(i=2,C_nk,
   v[(i-1)*k_fac+1]=v[(i-2)*k_fac+1]; \\ копируем предыдущее сочетание в текущее
   if(v[(i-1)*k_fac+1][k]==n,p=p-1,p=k); 
   for(j=p,k,v[(i-1)*k_fac+1][j]=v[(i-2)*k_fac+1][p]+1+j-p); \\ генерируем текущее сочетание
   for(m=2,k_fac,for(j=1,k,v[(i-1)*k_fac+m][j]=v[(i-1)*k_fac+1][v_p[m-1][j]]))); \\ генерируем все перестановки к текущему сочетанию
return(vecsort(v))} \\сортируем в лексикографическом порядке и возвращаем результат

Работает так:

? a=v_perm(4,3);print(a)
[[1, 2, 3], [1, 2, 4], [1, 3, 2], [1, 3, 4], [1, 4, 2], [1, 4, 3], [2, 1, 3], [2, 1, 4], [2, 3, 1], [2, 3, 4], [2, 4, 1], [2, 4,
3], [3, 1, 2], [3, 1, 4], [3, 2, 1], [3, 2, 4], [3, 4, 1], [3, 4, 2], [4, 1, 2], [4, 1, 3], [4, 2, 1], [4, 2, 3], [4, 3, 1], [4
, 3, 2]]

[Aritaborian]

(О прикреплении документа к сообщению)

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

Что-то я не вижу где можно прикрепить файл Excel'а

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

[kthxbye]

Aritaborian, благодарю за пояснения!

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

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

Замечательная вещь! В Excel такое не реализуешь, разве что через VBA.

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

У вас, кажись, элементы нумеруются от нуля, если это принципиально, можно вычесть единицу отовсюду.

От нуля и до n-1 (это тоже важно), так что вычесть достаточно всего в двух местах:

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-1);
p=k;
for(i=2,C_nk,
v[i]=v[i-1];
if(v[i][k]==n-1,p=p-1,p=k);
for(j=p,k,v[i][j]=v[i-1][p]+1+j-p));
return(v)}

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

Ну и ещё, в качестве пособия, генератор массива всех перестановок всех сочетаний из n элементов по k
Возвращет вектор, состоящий из $k!C_n^k$ элементов, являющихся векторами, состоящими из $k$ чисел.

За это тоже спасибо, но надобности в них пока что нет, так что только как пособие, да.

Раз мы разобрались с удобной генерацией основных исходных данных, можно наверное уже идти дальше (если, опять-таки, есть время и желание).

У нас есть вектор из векторов v_comb(n,k). Создаем вектор из векторов p всех возможных перестановок длины k. Далее создаем пустой вектор из векторов a (в которых тоже по k элементов). Берем 1-ый вектор из v_comb(n,k), 1-ую перестановку, переставляем, и помещаем результат в 1-ый вектор a. Далее берем все тот же 1-ый вектор из v_comb(n,k), но уже 2-ую перестановку, переставляем, результат во 2-ой вектор a. Продолжаем операции с 1-ым вектором из v_comb(n,k) для всех k! перестановок, результаты помещаем в a.

[kthxbye]

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

Буду экспериментировать.

[wrest]

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

От нуля и до n-1 (это тоже важно), так что вычесть достаточно всего в двух местах:

Да, в этих местах, верно. Но вы гляньте, может не так уж и нужно именно от 0 до n-1 а не от 1 до n.
Вот генератор всех сочетаний из n по k который работает примерно в три раза быстрее чем v_comb за счет использования встроенного генератора подмножеств:

v_comb2(n,k)={
    my(v=vector(binomial(n,k),i,vector(k)),i=1);
   forsubset([n,k],s,v[i]=s;i++);
   return(v)}

Работает так:
?v_comb2(4,3)
%1 = [Vecsmall([1, 2, 3]), Vecsmall([1, 2, 4]), Vecsmall([1, 3, 4]), Vecsmall([2, 3, 4])]

Векторы с сочетаниями получаются типа Vecsmall, если это мешает, то можно преобразовать в "обычные" векторы (тогда будет не в три а примерно в два раза быстрее чем v_comb):

v_comb3(n,k)={
    my(v=vector(binomial(n,k),i,vector(k)),i=1);
   forsubset([n,k],s,v[i]=Vec(s);i++);
   return(v)}

Работает так:
? v_comb3(4,3)
%1 = [[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]

[kthxbye]

wrest, ещё раз спасибо! Я не проверял до конца, но, скорее всего, мой основной вопрос уже исчерпан.

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

Но вы гляньте, может не так уж и нужно именно от 0 до n-1 а не от 1 до n.

Вообще идея со всеми этими манипуляциями совместная и я работаю с другими исходными данными (и соот.-но условия проверки на соответствие тоже другие). А товарищ который крутит сочетаниями свои условия зажал (я думаю не насовсем, а, скорее всего, до публикации), но нужны они ему непременно от 0 до n-1.

[wrest]

Ещё две версии функции v_perm

v_perm2(n,k) - генерирует все перестаовки всех сочетаний из n по k то есть возвращает вектор, состоящий из $k!C_n^k$ элементов-векторов по $k$ элементов-чисел каждый.

(Оффтоп)

v_perm2(n,k)={
my(C_nk=binomial(n,k),k_fac=k!,v=vector(C_nk*k_fac,i,vector(k)),v_p=vector(k_fac,i,numtoperm(k,i)),i=1);
forsubset([n,k],s,v[i]=Vec(s);for(m=1,k_fac-1,for(j=1,k,v[i+m][j]=v[i][v_p[m][j]]));i=i+k_fac);
return(vecsort(v))}

(Работа:)

? v_perm2(4,3)
%1 = [[1, 2, 3], [1, 2, 4], [1, 3, 2], [1, 3, 4], [1, 4, 2], [1, 4, 3], [2, 1, 3], [2, 1, 4], [2, 3, 1], [2, 3, 4], [2, 4, 1], [2, 4, 3], [3, 1, 2], [3, 1, 4], [3, 2, 1], [3, 2, 4], [3, 4, 1], [3, 4, 2], [4, 1, 2], [4, 1, 3], [4, 2, 1], [4, 2, 3], [4, 3, 1], [4, 3, 2]]

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

А товарищ который крутит сочетаниями свои условия зажал (я думаю не насовсем, а, скорее всего, до публикации), но нужны они ему непременно от 0 до n-1.

v_perm3(n,k) - то же самое, но элементы нумеруются не от 1 до n, а от 0 до n-1

(Оффтоп)

v_perm3(n,k)={
my(C_nk=binomial(n,k),k_fac=k!,v=vector(C_nk*k_fac,i,vector(k)),v_p=vector(k_fac,i,numtoperm(k,i)),i=1);
forsubset([n,k],s,v[i]=Vec(s);for(j=1,k,v[i][j]--);for(m=1,k_fac-1,for(j=1,k,v[i+m][j]=v[i][v_p[m][j]]));i=i+k_fac);
return(vecsort(v))}

(Работа:)

? v_perm3(4,3)
%1 = [[0, 1, 2], [0, 1, 3], [0, 2, 1], [0, 2, 3], [0, 3, 1], [0, 3, 2], [1, 0, 2], [1, 0, 3], [1, 2, 0], [1, 2, 3], [1, 3, 0], [1, 3, 2], [2, 0, 1], [2, 0, 3], [2, 1, 0], [2, 1, 3], [2, 3, 0], [2, 3, 1], [3, 0, 1], [3, 0, 2], [3, 1, 0], [3, 1, 2], [3, 2, 0], [3, 2, 1]]

Если лексикографическая сортировка не нужна, то вместо return(vecsort(v)) надо писать return(v) -- будет быстрее на больших объемах.

По скорости работы.
С сортировкой (return(vecsort(v)) в конце)

(Оффтоп)

? n=#v_perm(10,8)
%1 = 1814400
? ##
*** last result computed in 20,658 ms.
? n=#v_perm2(10,8)
%2 = 1814400
? ##
*** last result computed in 14,177 ms.
? n=#v_perm3(10,8)
%3 = 1814400
? ##
*** last result computed in 14,823 ms.

Без сортировки (просто return(v) конце):

(Оффтоп)

? n=#v_perm(10,8)
%1 = 1814400
? ##
*** last result computed in 16,266 ms.
? n=#v_perm2(10,8)
%2 = 1814400
? ##
*** last result computed in 10,844 ms.
? n=#v_perm3(10,8)
%3 = 1814400
? ##
*** last result computed in 11,388 ms.

Эти функции создают массивы больших размеров ($k!C_n^k \times k$ элементов), что замедляет работу. И если можно сразу, по месту, обрабатывать получающиеся перестановки, то будет немного (процентов на 30) быстрее.