Class MultiSetLinkedList

java.lang.Object

MultiSetLinkedList

All Implemented Interfaces:

java.io.Serializable

public class MultiSetLinkedList
extends java.lang.Object
implements java.io.Serializable

A class for iterating through the permutations of a multiset without repetition. The idea is that it requires a lot of memory to list all permutations of a big multiset at the same time, so this class stores the current permutation in memory and has the ability to 'step' to the permutation that is 'next' in some ordering on all permutations of this multiset. The ordering is the cool-lex ordering, which, along with this iteration algorithm, is described in the paper by Aaron Williams: Loopless Generation of Multiset Permutations using a Constant Number of Variables by Prefix Shifts.

See Also:

Serialized Form

Method Summary

Methods

Modifier and Type	Method and Description
static MultiSetLinkedList	createMultiSetLinkedList(int[] d) Public static factory method.
static MultiSetLinkedList	createMultiSetLinkedList(java.lang.Integer[] d) Public static factory method.
static MultiSetLinkedList	createMultiSetLinkedList(java.util.List<java.lang.Integer> d) Public static factory method.
MultiSetLinkedList	deepCopy() Make a deep copy of this.
boolean	equals(java.lang.Object obj)
int[]	getArray() Produce an array version of the current permutation.
int	hashCode()
void	iterate() Change to the next permutation in cool-lex order.
java.lang.String	toString() Output a String representation of the current state of this.

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Method Detail

createMultiSetLinkedList

public static MultiSetLinkedList createMultiSetLinkedList(java.util.List<java.lang.Integer> d)

Public static factory method. Create a MultiSetLinkedList where the underlying multiset is input as a List of Integers.

Parameters:

d - The underlying multiset, giving as a List of Integers.

Returns:

The MultiSetLinkedList that iterates through permutations of d.

createMultiSetLinkedList

public static MultiSetLinkedList createMultiSetLinkedList(java.lang.Integer[] d)

Public static factory method. Create a MultiSetLinkedList where the underlying multiset is input as an array of Integers.

Parameters:

d - The underlying multiset, giving as an array of Integers.

Returns:

The MultiSetLinkedList that iterates through permutations of d.

createMultiSetLinkedList

public static MultiSetLinkedList createMultiSetLinkedList(int[] d)

Public static factory method. Create a MultiSetLinkedList where the underlying multiset is input as an array of int.

Parameters:

d - The underlying multiset, giving as an array of int.

Returns:

The MultiSetLinkedList that iterates through permutations of d.

deepCopy

public MultiSetLinkedList deepCopy()

Make a deep copy of this.

Returns:

Another MultiSetLinkedList with the same underlying multiset as this and in the same state, but with the internal fields pointing to different memory addresses.

toString

public java.lang.String toString()

Output a String representation of the current state of this.

Overrides:

toString in class java.lang.Object

Returns:

A String containing the current permutation of the underlying multiset, with entries separated by spaces and enclosed by parentheses.

iterate

public void iterate()

Change to the next permutation in cool-lex order.

getArray

public int[] getArray()

Produce an array version of the current permutation.

Returns:

An array representing the current permutation of the underlying multiset.

equals

public boolean equals(java.lang.Object obj)

Overrides:

equals in class java.lang.Object

hashCode

public int hashCode()

Overrides:

hashCode in class java.lang.Object