/* 24.12.2008 last modification: 26.06.2013
Copyright (c) 2008-2013 by Siegfried Koepf
This file is distributed under the terms of the GNU General Public License
version 3 as published by the Free Software Foundation.
For information on usage and redistribution and for a disclaimer of all
warranties, see the file COPYING in this distribution.
Partitions in reverse lexicographic order
Based on Algorithm ZS1 in: Zoghbi, Antoine and Stojmenovic, Ivan: Fast Algorithms for Generating Integer Partitions. International Journal of Computer Mathematics, 70, 1998, 319-332.
Functions:
int gen_part_revlex_init(unsigned char *vector, const unsigned char n, unsigned char *k)
Test for special cases
Initialization of vector
Initialization of k
Possible return values are: GEN_EMPTY, GEN_NEXT
int gen_part_revlex_next(unsigned char *vector, unsigned char *k)
Transforms current figure in vector into its successor
Sets k to the appropriate value
Possible return values are: GEN_NEXT, GEN_TERM
Arguments:
unsigned char *vector; //pointer to the array where the current figure is stored
const unsigned char n; //length of alphabet
const unsigned char k; //length of figures
Usage and restrictions:
Arguments and elements in vector are restricted to the interval (0, 255)
Memory allocation for vector must be provided by the calling process
Cardinality see:
Sloane, N.J.A. et al.: The On-Line Encyclopedia of Integer Sequences, 2008.
http://oeis.org/A000041
see also:
http://mathworld.wolfram.com/Partition.html
*/
#include "_generate.h"
int gen_part_revlex_init(unsigned char *vector, const unsigned char n, unsigned char *k)
{
int j; //index
//test for special cases
if(n == 0)
{
(*k) = 0;
return(GEN_EMPTY);
}
//initialize: vector[0] = n, vector[1, ..., n - 1] are 1
vector[0] = n;
for(j = 1; j < n; j++)
vector[j] = 1;
(*k) = 1;
return(GEN_NEXT);
}
int gen_part_revlex_next(unsigned char *vector, unsigned char *k)
{
static int j = 0; //remember index of the rightmost part which is greater than 1
int r; //temporary remainder
int temp; //auxiliary element
//easy case
if(vector[j] == 2)
{
vector[j] = 1;
j--;
(*k)++;
return(GEN_NEXT);
}
//terminate if all parts are 1
if(vector[0] == 1)
{
j = 0;
return(GEN_TERM);
}
//decrease
vector[j]--;
temp = vector[j];
r = *k - j;
//set right-hand elements
while(r > temp)
{
j++;
vector[j] = temp;
r -= temp;
}
*k = j + 2;
//set rightmost element
if(r > 1)
{
j++;
vector[j] = r;
}
return(GEN_NEXT);
}