Ещё две версии функции
v_permv_perm2(n,k) - генерирует все перестаовки всех сочетаний из
n по
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]]
А товарищ который крутит сочетаниями свои условия зажал (я думаю не насовсем, а, скорее всего, до публикации), но нужны они ему непременно от 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.
Эти функции создают массивы больших размеров (
элементов), что замедляет работу. И если можно сразу, по месту, обрабатывать получающиеся перестановки, то будет немного (процентов на 30) быстрее.