cc.redberry.core.groups.permutations

Class RandomPermutation

java.lang.Object

cc.redberry.core.groups.permutations.RandomPermutation

public final class RandomPermutation
extends java.lang.Object

Algorithms for generating uniform distributed random elements of permutation group.

Example:

In the following example we use a two generators, which generates a group of order 5616 and choose 5616 random elements of this group with uniform distribution

 //primitive permutation group with 5616 elements
 Permutation perm1 = new PermutationOneLineInt(9, 1, 2, 0, 4, 8, 5, 11, 6, 3, 10, 12, 7);
 Permutation perm2 = new PermutationOneLineInt(2, 0, 1, 8, 3, 5, 7, 11, 4, 12, 9, 6, 10);
 ArrayList<Permutation> generators = new ArrayList<>(Arrays.asList(perm1, perm2));
 //we'll use a list of generators as a source of randomness
 //this brings some randomization in generators list
 RandomPermutation.randomness(generators);
 Set<Permutation> set = new HashSet<>();
 int k = 5616; //equal to order of group
 //choosing 5616 random elements
 for (; k > 0; --k)
     set.add(RandomPermutation.random(generators));
 //uniform
 System.out.println(set.size());//~3500
 

Since:

1.1.6

Field Summary

Fields

Modifier and Type	Field and Description
static int	DEFAULT_NUMBER_OF_RANDOM_REFINEMENTS Default size of random refinements
static int	DEFAULT_RANDOMNESS_EXTEND_TO_SIZE Default size of random source list of generators

Method Summary

Modifier and Type	Method and Description
static Permutation	random(java.util.List<Permutation> generators) Produces almost uniformly distributed elements of a group specified by specified generators (only if method randomness(java.util.List, int, int, org.apache.commons.math3.random.RandomGenerator) was invoked with specified generators); and brings additional randomness in the specified list.
static Permutation	random(java.util.List<Permutation> generators, org.apache.commons.math3.random.RandomGenerator random) Produces almost uniformly distributed elements of a group specified by specified generators (only if method randomness(java.util.List, int, int, org.apache.commons.math3.random.RandomGenerator) was invoked with specified generators); and brings additional randomness in the specified list.
static void	randomness(java.util.List<Permutation> generators) Brings randomness to a list of generators: the source list will be extended and filled by an equivalent set of generators generated randomly; commonly it should be used in a combination with random(java.util.List, org.apache.commons.math3.random.RandomGenerator) to produce almost uniform distributed permutations in a group defined by corresponding set of generators.
static void	randomness(java.util.List<Permutation> generators, int extendToSize, int numberOfRefinements, org.apache.commons.math3.random.RandomGenerator random) Brings randomness to a list of generators: the source list will be extended and filled by an equivalent set of generators generated randomly; commonly it should be used in a combination with random(java.util.List, org.apache.commons.math3.random.RandomGenerator) to produce almost uniform distributed permutations in a group defined by corresponding set of generators.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

DEFAULT_RANDOMNESS_EXTEND_TO_SIZE

public static final int DEFAULT_RANDOMNESS_EXTEND_TO_SIZE

Default size of random source list of generators

See Also:

Constant Field Values

DEFAULT_NUMBER_OF_RANDOM_REFINEMENTS

public static final int DEFAULT_NUMBER_OF_RANDOM_REFINEMENTS

Default size of random refinements

See Also:

Constant Field Values

Method Detail

randomness

public static void randomness(java.util.List<Permutation> generators)

Brings randomness to a list of generators: the source list will be extended and filled by an equivalent set of generators generated randomly; commonly it should be used in a combination with random(java.util.List, org.apache.commons.math3.random.RandomGenerator) to produce almost uniform distributed permutations in a group defined by corresponding set of generators. This method is a variant of PREINITIALIZE described in Sec. 3.2.2 in [Holt05].

Parameters:

generators - a list of generators

See Also:

random(java.util.List, org.apache.commons.math3.random.RandomGenerator)

randomness

public static void randomness(java.util.List<Permutation> generators,
                              int extendToSize,
                              int numberOfRefinements,
                              org.apache.commons.math3.random.RandomGenerator random)

Brings randomness to a list of generators: the source list will be extended and filled by an equivalent set of generators generated randomly; commonly it should be used in a combination with random(java.util.List, org.apache.commons.math3.random.RandomGenerator) to produce almost uniform distributed permutations in a group defined by corresponding set of generators. This method is a variant of PREINITIALIZE described in Sec. 3.2.2 in [Holt05].

Parameters:

generators - a list of generators

extendToSize - extend specified list to this size with additional (equivalent) random elements

numberOfRefinements - number of invocations of random procedure to refine the randomness

random - random generator

random

public static Permutation random(java.util.List<Permutation> generators)

Produces almost uniformly distributed elements of a group specified by specified generators (only if method randomness(java.util.List, int, int, org.apache.commons.math3.random.RandomGenerator) was invoked with specified generators); and brings additional randomness in the specified list. See algorithm PRRANDOM in Sec. 3.2.2 in [Holt05].

Parameters:

generators - generators (method randomness(java.util.List, int, int, org.apache.commons.math3.random.RandomGenerator) should be invoked before)

Returns:

random element of a group

random

public static Permutation random(java.util.List<Permutation> generators,
                                 org.apache.commons.math3.random.RandomGenerator random)

Produces almost uniformly distributed elements of a group specified by specified generators (only if method randomness(java.util.List, int, int, org.apache.commons.math3.random.RandomGenerator) was invoked with specified generators); and brings additional randomness in the specified list. See algorithm PRRANDOM in Sec. 3.2.2 in [Holt05].

Parameters:

generators - generators (method randomness(java.util.List, int, int, org.apache.commons.math3.random.RandomGenerator) should be invoked before)

random - random generator

Returns:

random element of a group