org.jgrapht.experimental.permutation

Class IntegerPermutationIter

java.lang.Object

org.jgrapht.experimental.permutation.IntegerPermutationIter

All Implemented Interfaces:

Iterator, ArrayPermutationsIter

public class IntegerPermutationIter
extends Object
implements Iterator, ArrayPermutationsIter

Iterates through permutations of N elements.

1. use getNext() to get the next permutation order, for example(N=4): perm0=[1,2,3,4] perm1=[1,2,4,3] perm2=[1,3,2,4] .
2. use hasNext() or verify by counter<getTotalNumberOfPermutations () that you do not overflow the max number. RunTimeException will be thrown if you do. Getting the next permutation is done in O(N) Note: This class is not thread safe.

Since:

May 20, 2005

Author:

Assaf

Constructor Summary

Constructors

Constructor and Description
IntegerPermutationIter(int N) Creates an array of size N with elements 1,2,...,n-1 Useful for describing regular permutations.
IntegerPermutationIter(int[] array) Uses a predefined array (sorted), for example: [3,1,1,2,1]-->[1,1,1,2,3]; note that there are much less than 5! premutations here, because of the repetitive 1s.

Method Summary

Modifier and Type	Method and Description
int[]	getCurrent()
int[]	getNext() Facade.
boolean	hasNext() Efficiency: O(N) implementation, try to take the next!
boolean	hasNextPermutaions()
Object	next()
int[]	nextPermutation()
void	remove() UNIMPLEMENTED.
String	toString(int[] array) Utility method to convert the array into a string examples: [] [0] [0,1][1,0]

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.util.Iterator

forEachRemaining

Constructor Detail

IntegerPermutationIter

public IntegerPermutationIter(int N)

Creates an array of size N with elements 1,2,...,n-1 Useful for describing regular permutations. See IntegerPermutationIter(int[] array) for the other kind of permutations; efficency of initiation is O(N)

Parameters:

N -

IntegerPermutationIter

public IntegerPermutationIter(int[] array)

Uses a predefined array (sorted), for example: [3,1,1,2,1]-->[1,1,1,2,3]; note that there are much less than 5! premutations here, because of the repetitive 1s.

Parameters:

array - creates a copy of it (so sort / later changes will not matter)

Method Detail

hasNext

public boolean hasNext()

Efficiency: O(N) implementation, try to take the next!

Specified by:

hasNext in interface Iterator

next

public Object next()

Specified by:

next in interface Iterator

getNext

public int[] getNext()

Facade. use it with getNext. efficency: O(N)

Returns:

a new Array with the permutatation order. for example: perm0=[1,2,3,4] perm1=[1,2,4,3] perm2=[1,3,2,4]

getCurrent

public int[] getCurrent()

toString

public String toString(int[] array)

Utility method to convert the array into a string examples: [] [0] [0,1][1,0]

Parameters:

array -

remove

public void remove()

UNIMPLEMENTED. always throws new UnsupportedOperationException

Specified by:

remove in interface Iterator

See Also:

Iterator.remove()

nextPermutation

public int[] nextPermutation()

Specified by:

nextPermutation in interface ArrayPermutationsIter

hasNextPermutaions

public boolean hasNextPermutaions()

Specified by:

hasNextPermutaions in interface ArrayPermutationsIter