SYMMETRICA-MANUAL -- Advanced routines

Advanced routines

Advanced routines

Generation of partitions: Very often you want to loop over all partitions, of a given weight. Look at the following lines:

Example:
#include "def.h"
#include "macro.h"
main()
{
OP a,b;
anfang();
a = callocobject();
b = callocobject();
scan(INTEGER,a);
first_partition(a,b);
do
{
println(b);
}
 while (next(b,b));
freeall(a);
freeall(b);
ende();
}
which is a program which first asks the weight, and then prints a list of all partitions of that weight.

Here is the description:

NAME: first_partition
SYNOPSIS: INT first_partition(OP n, result)
DESCRIPTION: n must be an INTEGERobject, and result becomes the PARTITIONobject of VECTOR kind, which is the first one according to many orders of partitions, namely the partition [n].

An analogous routine is

NAME: last_partition
SYNOPSIS: INT last_partition(OP n, result)
DESCRIPTION: n must be an INTEGERobject, and result becomes the PARTITIONobject of VECTORkind, which is the last one according to many orders of partitions, namely the partition [1ⁿ].

And if you want to specify the kind of representation of the partition, there is also

first_part_VECTOR, first_part_EXPONENT

and

last_part_VECTOR, last_part_EXPONENT

which have the same parameters and produce the specified PARTITIONobjects.

In order to generate the next partition you should use the standardroutine

next(),

which allows you to use the same object for input and output. Note that this is not allowed if you use the low level routine

next_partition().

For the output of a PARTITIONobject using the standard routines print, println or fprint and fprintln, you have to know the followiing convention:

The parts of size 10£size£15 are printed as A,B,C,D,E,F and the parts bigger than 15 are printed with a ''|`` between the parts.

There is a routine for the generation of a vector of all partitions, look at the following example:

Example:
...
scan(INTEGER,a);
makevectorofpart(a,b);
println(b);
println(s_v_i(b,s_v_li(b)-1L));
...
which prints a vector with all partitions of given weight, and then in the next line it will print the last partition of the specified weight.

The complete description is:

NAME: makevectorofpart gives a vector of partitions
SYNOPSIS: INT makevectorofpart(OP n, result)
DESCRIPTION: n must be an INTEGERobject, and result becomes a VECTORobject of PARTITIONobjects. The order is according to the order of next(). The PARTITIONobjects are of the kind VECTOR.

If you are interested in the number of partitions, then look at the following example:

Example:

#include "def.h"
#include "macro.h"
main()
{
INT i;
OP  a,b;
anfang();
a = callocobject();
b = callocobject();
for (i=1L;i<200L;i++)
{
  	freeself(a); freeself(b);
  	M_I_I(i,a);
  	numberofpart(a,b);	
  	print (a) ; println(b);
}
freeall(a);
freeall(b);
ende();
}

This program prints the number of partitions of weight up to 199. As you know this is quite a big number, and the result for e.g. a=150 will be no longer an INTEGERobject as for a=10, but a LONGINTobject.

NAME: numberofpart means number_of_partitions, while the name numberofpart_i abbreviates
number_of_partitions_as_an_INTvalue
SYNOPSIS:
INT numberofpart(OP n, result)

INT numberofpart_i(OP n)
DESCRIPTION: numberofpart computes the number of partitions of the given weight n, which must be an INTEGERobject. The result is an INTEGERobject, or a LONGINTobject, depending on the size of n. numberofpart_i gives the number of partitions as the return_value, and so it works only for small sizes of n only.
RETURN: numberofpart_i returns the number of partitions or ERROR numberofpart returns OK or ERROR.

The next routine uses a recursive method described by Gupta:

NAME: gupta_nm
SYNOPSIS: INT gupta_nm(OP n,m,erg)
DESCRIPTION: this routine computes the number of partitions of n with maximal part m. The result is erg. The input n,m must be INTEGERobjects. The result is freed first to an empty object. The result must be different from m and n.
RETURN: OK

There is also a routine, which computes a table of these values:

NAME: gupta_tafel
SYNOPSIS: INT gupta_tafel(OP max, result)
DESCRIPTION: it computes the table of the above values. The entry n,m is the result of gupta_nm. result is freed first. max must be an INTEGERobject, it is the maximum weight for the partitions. max must be different from result.
RETURN: OK

Very often we have to work with vectors or matrices labeled by partitions. So we need the index of a partition:

NAME: indexofpart
SYNOPSIS: INT indexofpart(OP part)
DESCRIPTION: computes the index of a partition. The algorithm used is the same as in next_partition. So the partition given by first_partition has the index 0.
RETURN: The index of the partition, or ERROR

harald.fripertinger@kfunigraz.ac.at,
last changed: November 19, 2001

Advanced routines