Combinatorics Algorithms
Implementations to solve various combinatorial aspects for strings of objects.
Functions

unsigned int **vrna_enumerate_necklaces(const unsigned int *type_counts)
 #include <ViennaRNA/combinatorics.h>
Enumerate all necklaces with fixed content.
This function implements A fast algorithm to generate necklaces with fixed content as published by Sawada [2003] .
The function receives a list of counts (the elements on the necklace) for each type of object within a necklace. The list starts at index 0 and ends with an entry that has a count of 0. The algorithm then enumerates all noncyclic permutations of the content, returned as a list of necklaces. This list, again, is zeroterminated, i.e. the last entry of the list is a
NULL
pointer. SWIG Wrapper Notes:
This function is available as global function
enumerate_necklaces()
which accepts lists input, an produces list of lists output. See, e.g.RNA.enumerate_necklaces()
in the Python API .
 Parameters:
type_counts – A 0terminated list of entity counts
 Returns:
A list of all noncyclic permutations of the entities

unsigned int vrna_rotational_symmetry_num(const unsigned int *string, size_t string_length)
 #include <ViennaRNA/combinatorics.h>
Determine the order of rotational symmetry for a string of objects represented by natural numbers.
The algorithm applies a fast search of the provided string within itself, assuming the end of the string wraps around to connect with it’s start. For example, a string of the form
011011
has rotational symmetry of order2
This is a simplified version of vrna_rotational_symmetry_pos_num() that may be useful if one is only interested in the degree of rotational symmetry but not the actual set of rotational symmetric strings.
 SWIG Wrapper Notes:
This function is available as global function
rotational_symmetry()
. See vrna_rotational_symmetry_pos() for details. Note, that in the target language the length of the liststring
is always known apriori, so the parameterstring_length
must be omitted. See, e.g.RNA.rotational_symmetry()
in the Python API .
See also
vrna_rotational_symmetry_pos_num(), vrna_rotationa_symmetry()
 Parameters:
string – The string of elements encoded as natural numbers
string_length – The length of the string
 Returns:
The order of rotational symmetry

unsigned int vrna_rotational_symmetry_pos_num(const unsigned int *string, size_t string_length, unsigned int **positions)
 #include <ViennaRNA/combinatorics.h>
Determine the order of rotational symmetry for a string of objects represented by natural numbers.
The algorithm applies a fast search of the provided string within itself, assuming the end of the string wraps around to connect with it’s start. For example, a string of the form
011011
has rotational symmetry of order2
If the argument
positions
is notNULL
, the function stores an array of string start positions for rotational shifts that map the string back onto itself. This array has length of order of rotational symmetry, i.e. the number returned by this function. The first elementpositions
[0] always contains a shift value of0
representing the trivial rotation. SWIG Wrapper Notes:
This function is available as global function
rotational_symmetry()
. See vrna_rotational_symmetry_pos() for details. Note, that in the target language the length of the liststring
is always known apriori, so the parameterstring_length
must be omitted. See, e.g.RNA.rotational_symmetry()
in the Python API .
Note
Do not forget to release the memory occupied by
positions
after a successful execution of this function. Parameters:
string – The string of elements encoded as natural numbers
string_length – The length of the string
positions – A pointer to an (undefined) list of alternative string start positions that lead to an identity mapping (may be NULL)
 Returns:
The order of rotational symmetry

unsigned int vrna_rotational_symmetry(const char *string)
 #include <ViennaRNA/combinatorics.h>
Determine the order of rotational symmetry for a NULLterminated string of ASCII characters.
The algorithm applies a fast search of the provided string within itself, assuming the end of the string wraps around to connect with it’s start. For example, a string of the form
AABAAB
has rotational symmetry of order2
This is a simplified version of vrna_rotational_symmetry_pos() that may be useful if one is only interested in the degree of rotational symmetry but not the actual set of rotational symmetric strings.
 SWIG Wrapper Notes:
This function is available as global function
rotational_symmetry()
. See vrna_rotational_symmetry_pos() for details. See, e.g.RNA.rotational_symmetry()
in the Python API .
See also
vrna_rotational_symmetry_pos(), vrna_rotationa_symmetry_num()
 Parameters:
string – A NULLterminated string of characters
 Returns:
The order of rotational symmetry

unsigned int vrna_rotational_symmetry_pos(const char *string, unsigned int **positions)
 #include <ViennaRNA/combinatorics.h>
Determine the order of rotational symmetry for a NULLterminated string of ASCII characters.
The algorithm applies a fast search of the provided string within itself, assuming the end of the string wraps around to connect with it’s start. For example, a string of the form
AABAAB
has rotational symmetry of order2
If the argument
positions
is notNULL
, the function stores an array of string start positions for rotational shifts that map the string back onto itself. This array has length of order of rotational symmetry, i.e. the number returned by this function. The first elementpositions
[0] always contains a shift value of0
representing the trivial rotation. SWIG Wrapper Notes:
This function is available as overloaded global function
rotational_symmetry()
. It merges the functionalities of vrna_rotational_symmetry(), vrna_rotational_symmetry_pos(), vrna_rotational_symmetry_num(), and vrna_rotational_symmetry_pos_num(). In contrast to our Cimplementation, this function doesn’t return the order of rotational symmetry as a single value, but returns a list of cyclic permutation shifts that result in a rotationally symmetric string. The length of the list then determines the order of rotational symmetry. See, e.g.RNA.rotational_symmetry()
in the Python API .
See also
vrna_rotational_symmetry(), vrna_rotational_symmetry_num(), vrna_rotational_symmetry_num_pos()
Note
Do not forget to release the memory occupied by
positions
after a successful execution of this function. Parameters:
string – A NULLterminated string of characters
positions – A pointer to an (undefined) list of alternative string start positions that lead to an identity mapping (may be NULL)
 Returns:
The order of rotational symmetry

unsigned int vrna_rotational_symmetry_db(vrna_fold_compound_t *fc, const char *structure)
 #include <ViennaRNA/combinatorics.h>
Determine the order of rotational symmetry for a dotbracket structure.
Given a (permutation of multiple) RNA strand(s) and a particular secondary structure in dotbracket notation, compute the degree of rotational symmetry. In case there is only a single linear RNA strand, the structure always has degree 1, as there are no rotational symmetries due to the direction of the nucleic acid sequence and the fixed positions of 5’ and 3’ ends. However, for circular RNAs, rotational symmetries might arise if the sequence consists of a concatenation of \(k\) identical subsequences.
This is a simplified version of vrna_rotational_symmetry_db_pos() that may be useful if one is only interested in the degree of rotational symmetry but not the actual set of rotational symmetric strings.
 SWIG Wrapper Notes:
This function is attached as method
rotational_symmetry_db()
to objects of typefold_compound
(i.e. vrna_fold_compound_t). See vrna_rotational_symmetry_db_pos() for details. See, e.g.RNA.fold_compound.rotational_symmetry_db()
in the Python API .
See also
vrna_rotational_symmetry_db_pos(), vrna_rotational_symmetry(), vrna_rotational_symmetry_num()
 Parameters:
fc – A fold_compound data structure containing the nucleic acid sequence(s), their order, and model settings
structure – The dotbracket structure the degree of rotational symmetry is checked for
 Returns:
The degree of rotational symmetry of the
structure
(0 in case of any errors)

unsigned int vrna_rotational_symmetry_db_pos(vrna_fold_compound_t *fc, const char *structure, unsigned int **positions)
 #include <ViennaRNA/combinatorics.h>
Determine the order of rotational symmetry for a dotbracket structure.
Given a (permutation of multiple) RNA strand(s) and a particular secondary structure in dotbracket notation, compute the degree of rotational symmetry. In case there is only a single linear RNA strand, the structure always has degree 1, as there are no rotational symmetries due to the direction of the nucleic acid sequence and the fixed positions of 5’ and 3’ ends. However, for circular RNAs, rotational symmetries might arise if the sequence consists of a concatenation of \(k\) identical subsequences.
If the argument
positions
is notNULL
, the function stores an array of string start positions for rotational shifts that map the string back onto itself. This array has length of order of rotational symmetry, i.e. the number returned by this function. The first elementpositions
[0] always contains a shift value of0
representing the trivial rotation. SWIG Wrapper Notes:
This function is attached as method
rotational_symmetry_db()
to objects of typefold_compound
(i.e. vrna_fold_compound_t). Thus, the first argument must be omitted. In contrast to our Cimplementation, this function doesn’t simply return the order of rotational symmetry of the secondary structure, but returns the listposition
of cyclic permutation shifts that result in a rotationally symmetric structure. The length of the list then determines the order of rotational symmetry. See, e.g.RNA.fold_compound.rotational_symmetry_db()
in the Python API .
See also
vrna_rotational_symmetry_db(), vrna_rotational_symmetry_pos(), vrna_rotational_symmetry_pos_num()
Note
Do not forget to release the memory occupied by
positions
after a successful execution of this function. Parameters:
fc – A fold_compound data structure containing the nucleic acid sequence(s), their order, and model settings
structure – The dotbracket structure the degree of rotational symmetry is checked for
positions – A pointer to an (undefined) list of alternative string start positions that lead to an identity mapping (may be NULL)
 Returns:
The degree of rotational symmetry of the
structure
(0 in case of any errors)

unsigned int **vrna_n_multichoose_k(size_t n, size_t k)
 #include <ViennaRNA/combinatorics.h>
Obtain a list of kcombinations with repetition (n multichoose k)
This function compiles a list of kcombinations, or kmulticombination, i.e. a list of multisubsets of size k from a set of integer values from 0 to n  1. For that purpose, we enumerate n + k  1 choose k and decrease each index position i by i to obtain n multichoose k.
 Parameters:
n – Maximum number to choose from (interval of integers from 0 to
n
 1)k – Number of elements to choose, i.e. size of each multisubset
 Returns:
A list of lists of elements of combinations (last entry is terminated by NULL

unsigned int *vrna_boustrophedon(size_t start, size_t end)
 #include <ViennaRNA/combinatorics.h>
Generate a sequence of Boustrophedon distributed numbers.
This function generates a sequence of positive natural numbers within the interval \( [start, end] \) in a Boustrophedon fashion. That is, the numbers \( start, \ldots, end \) in the resulting list are alternating between left and right ends of the interval while progressing to the inside, i.e. the list consists of a sequence of natural numbers of the form:
\[ start, end, start + 1, end  1, start + 2, end  2, \ldots \]The resulting list is 1based and contains the length of the sequence of numbers at it’s 0th position.
Upon failure, the function returns NULL
 SWIG Wrapper Notes:
This function is available as overloaded global function
boustrophedon()
. See, e.g.RNA.boustrophedon()
in the Python API .
See also
 Parameters:
start – The first number of the list (left side of the interval)
end – The last number of the list (right side of the interval)
 Returns:
A list of alternating numbers from the interval \( [start, end] \) (or NULL on error)

unsigned int vrna_boustrophedon_pos(size_t start, size_t end, size_t pos)
 #include <ViennaRNA/combinatorics.h>
Obtain the ith element in a Boustrophedon distributed interval of natural numbers.
 SWIG Wrapper Notes:
This function is available as overloaded global function
boustrophedon()
. Omitting thepos
argument yields the entire sequence fromstart
toend
. See, e.g.RNA.boustrophedon()
in the Python API .
See also
 Parameters:
start – The first number of the list (left side of the interval)
end – The last number of the list (right side of the interval)
pos – The index of the number within the Boustrophedon distributed sequence (1based)
 Returns:
The
posth
element in the Boustrophedon distributed sequence of natural numbers of the interval

unsigned int **vrna_enumerate_necklaces(const unsigned int *type_counts)