интерактивный курс: введение в программирование на PARI/GP

[Avdij]

Dmitriy40

Цитата:

9-я страница, короткий пример вложенных циклов

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

Цитата:

Подумать что такое range и чем оно отличается от 1,10 в Вашем же цикле

Да, понимаете - обидно. В оригинале - есть, в PARI/GP - тоже есть, а воспользоваться не получается.

[Dmitriy40]

Avdij в сообщении #1574558 писал(а):

Да, понимаете - обидно. В оригинале - есть, в PARI/GP - тоже есть, а воспользоваться не получается.

Нет, не понимаю: я не знаю питон, но даже мне без подглядывания в документацию по питону очевидно что в range(x,y) эти два числа x,y указывают начало и конец какого-то интервала, в данном случае вместе с for интервала перебора, т.е. start и stop для цикла for. Очевидно просто по смыслу происходящего в программе - ну перебор же каких-то значений. Очевидно настолько что это просто первое что приходит в голову проверить. И если я прав, то цикл из питона

for a in range(1, m+1):
  ...

преобразуется в цикл в PARI

for(a=1,m+1,
  ...
);

Если Вам это не очевидно даже после прочтения справки по for и примеров в начале темы, то ... может программирование это просто не ваше?

[wrest]

Dmitriy40 в сообщении #1574561 писал(а):

преобразуется в цикл в PARIКод:

for(a=1,m+1,

А я глянул, кстати. Преобразуется в for(a=1,m,...) почему то в питоне правая граница диапазона не входит в диапазон.

[Yadryara]

Dmitriy40 в сообщении #1574548 писал(а):

Avdij в сообщении #1574538 писал(а):

В этой теме нельзя консультироваться по Python?

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

Avdij в сообщении #1574551 писал(а):

Не настолько мне это нужно, чтоб аж тему заводить.

Да и не надо новую: «Курс по Python»

Дмитрий-то давно на форуме, неужто не знал.

Характерный случай. ВТФ занимается человек, так и не освоивший даже простой базовый приём: вложенные циклы.

[Avdij]

Yadryara

Цитата:

Характерный случай. ВТФ занимается человек, так и не освоивший даже простой базовый приём: вложенные циклы.

Зависть?

[Ende]

Что ж, я предупреждал.

Ende в сообщении #1570570 писал(а):

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

Avdij, постоянный бан.

[gris]

Понадобилось быстренько накидать натуральных массивов фиксированной длины (именно 9) с заданной суммой всех элементов (до 600).

{   p=vector(9);
    k=0; n=10; m=n-8; 
    for(i1=1, m,     j2=i1; 
    for(i2=1, m+1-j2, j3=j2+i2;  
    for(i3=1, m+2-j3, j4=j3+i3;
    for(i4=1, m+3-j4, j5=j4+i4; 
    for(i5=1, m+4-j5, j6=j5+i5;
    for(i6=1, m+5-j6, j7=j6+i6;
    for(i7=1, m+6-j7, j8=j7+i7;
    for(i8=1, m+7-j8, j9=j8+i8;
    for(i9=1, m+8-j9, 
       if(i1+i2+i3+i4+i5+i6+i7+i8+i9==n, k++;
         print(i1," ",i2," ",i3," "i4," ",i5," ",i6," ",i7," ",i8," ",i9);
      );
)))))))));
print("for sum=",n,"   number of vectors=",k)
}

1 1 1 1 1 1 1 1 2
...
2 1 1 1 1 1 1 1 1
for sum=9   number of vectors=10

А ведь есть готовые штуки? Совсем растерялся
И ещё вопрос: Предположим, я делаю вывод результатов принтом на консоль с одновременным выводом в текстовый файл указанием его через \l. Не лучше ли выводить в файл специальной командой?

[wrest]

gris в сообщении #1577729 писал(а):

А ведь есть готовые штуки? Совсем растерялся

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

Цитата:

partitions(k,{a=k},{n=k}): vector of partitions of the integer k. You can restrict the length of the partitions with
parameter n (n=nmax or n=[nmin,nmax]), or the range of the parts with parameter a (a=amax or a=[amin,amax]). By default
remove zeros, but one can set amin=0 to get X of fixed length nmax (=k by default).

Но при росте n и число разбиений растёт.
Для вашей задачи (разбить число 600 в сумму ровно из 9 слагаемых) и все их вывести команда будет
? partitions(600,,[9,9])
Но это очень много!
Если просто посчитать сколько их, то
? #partitions(600,,[9,9])
Но там все равно генерятся все разбиения, так что не дождётесь. Без генерации разбиений "за кадром", а только подсчет, будет делать такой хитрый код:

pnkv_5(n,k) = {my(k1=k+1,k2=k+2,t=vector(k2,i,vector(k1)), kx=k1, ky=0,
   ix=vector(1+2*k1-1,i,1+(k2-i)%k1), offset=k1);
     t[k1][2]=1;
     for(i=1, n-k-1,
        for(j=2,k1,
           ky=ix[j+offset];
           t[k2][j]=t[kx][j-1]+t[ky][j]);
        if(offset, offset--, offset=k);
        kx=1+(k+i)%(k1);
        t[kx]=t[k2]);
 return(vecsum(t[k2]))}

Соотвественно, при подсчёте разбиений числа 600 ровно на 9 ненулевых слагаемых, их общее количество получается равным 1 369 195 210 284 (т.е. порядка $1,4 \cdot 10^{12}$)
P.S. Это подсчет без учета порядка следования слагаемых (т.е. наборы слагаемых рассматриваются как мультимножества).

[wrest]

P.S. Код выше не мой, взят отсюда http://pari.math.u-bordeaux.fr/archives ... 00015.html
Я там поменял немного, исходя из того факта, что количество разбиений числа $n$ ровно на $k$ слагаемых равно количеству разбиений числа $n-k$ не более чем на $k$ слагаемых.

[gris]

Спасибо. Да, число большое, но предполагается обработка на ходу и пропуск только подходящих. В конкретном случае для $n=21$ из 125970 разбиений отсеялись все, кроме одного; для $n=25$ из 735471 разбиений осталось 11.
Я немножко ошибся: привел суммы, увеличенные в 12 раз. Но всё равно, для суммы $n=39$ слишком много вариантов.
Кстати, для забавы из соседней темы чирканул

{n=10; k=8; \\ from [1,n] take k randoms
p=vector(k,i,random(n)+1);
m=vector(k);

for( i=1,k-1, a=1; \\count repetitions
   if(p[i]>0, for (j=i+1,k, if(p[i]==p[j], a++; p[j]=0  ));
      m[a]++) ;
); 
if( p[k]>0, m[1]++ ); \\case in the end

\\cut zero tail
mk=k; for( i=0,k-1, if( m[k-i]==0, mk--,break));
print ("for ", k, " numbers look at: 1 times, 2 times, etc");
for( i=1,mk, print1(m[i]," ") ); print (" "); 
}
for 8 numbers look at: 1 times, 2 times, etc
5 0 1  
for 20 numbers look at: 1 times, 2 times, etc
4 5 2  

Ну в натуральном массиве выводится количество элементов, встречающихся 1,2,4 ... раза. Надо угадать диапазон равномерного распределения Тоже, наверное, PARI умеет проще-с
Вот тоже: вывести массив без хвоста из нулей. Как-то нудно получилось

[wrest]

gris в сообщении #1577765 писал(а):

Да, число большое, но предполагается обработка на ходу и пропуск только подходящих.

Я в своё время просто смотрел код partitions() в исходном коде PARI/GP - как именно генерируются разбиения там.

gris в сообщении #1577765 писал(а):

для суммы $n=39$ слишком много вариантов.

С учетом перестановок каждого разбиения - наверное много, но так-то уникальных разбиений числа $39$ ровно на $9$ слагаемых всего $3060$ - это немного, с учетом перетановок очень тупая оценка сверху будет $9!\cdot 3060 \approx 10^9$ - всего миллиард, но думаю на самом деле на пару-тройку порядков меньше. В принципе, можно сделать (или даже кажись где-то был -- не помню) и генератор неповторяющихся перестановок для мультимножеств

[gris]

Вот идея
{\\unsorted vectors a of n numbers from [1,max] with the sum=s
n=5; s=10;
p=vector(n);
d=vector(s-1,i,i); print("d ", d);
dex=vector(n-1);
a=vector(n);
k=0;

dex=[2,5,6,9]; print("dex ",dex); \\need to generate extractions

p=concat(dex,[s]); print("p ",p);
a=vector(n); a[1]=p[1];for(i=2,n,a[i]=p[i]-p[i-1]); print("a ",a);
}


d [1, 2, 3, 4, 5, 6, 7, 8, 9] Числа от 1 до s-1
dex [2, 5, 6, 9] подвектор длины n Нужны все
p [2, 5, 6, 9, 10] вектор расстояний
a [2, 3, 1, 3, 1] итоговый вектор с суммой s
Не могу найти, как готовой командой из исходного вектора последовательно экстрактировать подвекторы меньшей длины без изменения порядка

[wrest]

gris в сообщении #1578030 писал(а):

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

Лучше если бы вы написали исходный (в вашей терминологии -- "данный") вектор и результаты экстракции (другие векторы?). Словами непонятно что вы хотите.
Допустим, дан вектор [4,1,3,2] и надо "последовательно экстрактировать подвекторы меньшей длины без изменения порядка" - что получится?

[gris]

Ну вот из вектора [1,2,3,4,5] у меня они именно такого вида, уже упорядоченные, надо вынуть все порядка три:
123 124 125 134 135 145 234 245 345
Их будет $C_5^3=10$

[wrest]

gris в сообщении #1578034 писал(а):

Ну вот из вектора [1,2,3,4,5] надо вынуть все длиной 3:
123 124 125 134 135 145 234 245 345
Их будет $C_5^3=10$

Можно так:

subsets(v, k) = {
   my (lst = List());
   forvec(v1 = vector(k, i, [1, #v]), listput(lst, vecextract(v, v1)), 2);

   Vec(lst)
};

Функция subsets(v,k) приведённая выше, возвращает вектор из всех подвекторов длины k данного вектора v "без изменения порядка"
Например
? v=[4,1,3,2];subsets(v,3)
%1 = [[4, 1, 3], [4, 1, 2], [4, 3, 2], [1, 3, 2]]
?

Но если вам удобней что-то с ними делать и сразу забыть, то есть итератор forsubset() который проходит по всем подмножествам размера k множества [1,...,n] -- вы получаете подмножества индексов, и затем при помощи vecextract() получаете подмножества из вашего "данного" вектора.
forsubset([#v,3], s, print(vecextract(v,s)))

Работает так
? v=[4,1,3,2];forsubset([#v,3], s, print(vecextract(v,s)))
[4, 1, 3]
[4, 1, 2]
[4, 3, 2]
[1, 3, 2]
?

Вместо print() вы можете вставить (или вызвать) обработчик подвектора, например напечатать индексы подвектора, сам подвектор и сумму элементов:
? v=[4,1,3,2];forsubset([#v,3], s, v1=vecextract(v,s); s1=vecsum(v1);print("indexes of subvector ",s," subvector ",v1,"
sum is ",s1))
indexes of subvector Vecsmall([1, 2, 3]) subvector [4, 1, 3] sum is 8
indexes of subvector Vecsmall([1, 2, 4]) subvector [4, 1, 2] sum is 7
indexes of subvector Vecsmall([1, 3, 4]) subvector [4, 3, 2] sum is 9
indexes of subvector Vecsmall([2, 3, 4]) subvector [1, 3, 2] sum is 6
?

То есть в принципе, задача тут распадается на две. Первое -- генерация всех сочетаний из $n$ по $k$ -- это будут индексы для выборки подвектора из исходного вектора. Ну и затем, имея индексы ($k$ индексов), собственно выбирать подвекторы.

Можно в обоих случаях вместо чисел использовать столы, стулья и пивные кружки:
? v=["table","chair","beer mug"];forsubset([#v,2], s, print(vecextract(v,s)))
["table", "chair"]
["table", "beer mug"]
["chair", "beer mug"]
?
и так же
? v=["table","chair","beer mug"];print(subsets(v,2))
[["table", "chair"], ["table", "beer mug"], ["chair", "beer mug"]]
?

Идеи взяты отсюда https://stackoverflow.com/questions/334 ... in-pari-gp