/* 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.
Permutations with repetition in lexicographic order
Based on Algorithm L (Lexicographic permutation generation) in: Knuth, Donald E.: The Art of Computer Programming, Vol. 4: Fascicle 2. Generating All Tuples and Permutations. Upper Saddle River, NJ 2005.
Functions:
int gen_perm_rep_lex_init(const unsigned char n)
Test for special cases
Possible return values are: GEN_EMPTY, GEN_NEXT
int gen_perm_rep_lex_next(unsigned char *vector, const unsigned char n)
Transforms current figure in vector into its successor
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
vector must be initialized by the calling process. At that point elements in vector must be arranged in increasing order to obtain all possible permutations
Cardinality:
n! / ((s(1)! * ... * s(x)!)) with s(1) + ... + s(x) == n where s(x) is the number of occurrences of the xth disitinct element
*/
#include "_generate.h"
int gen_perm_rep_lex_init(const unsigned char n)
{
//test for special cases
if(n == 0)
return(GEN_EMPTY);
//initialize: vector must be initialized by the calling process
return(GEN_NEXT);
}
int gen_perm_rep_lex_next(unsigned char *vector, const unsigned char n)
{
int j = n - 2; //index
int i = n - 1; //help index
int temp; //auxiliary element
//find rightmost element to increase
while(j >= 0)
{
if(vector[j] < vector[j + 1])
break;
j--;
}
//terminate if all elements are in decreasing order
if(j < 0)
return(GEN_TERM);
//find i
while(vector[i] <= vector[j])
i--;
//increase (swap)
temp = vector[j];
vector[j] = vector[i];
vector[i] = temp;
//reverse right-hand elements
for(j += 1, i = n - 1; j < i; j++, i--)
{
temp = vector[j];
vector[j] = vector[i];
vector[i] = temp;
}
return(GEN_NEXT);
}