aud.util.PermutationIterator Class Reference

Iterator over all permutations of length n. More...

Inheritance diagram for aud.util.PermutationIterator:

Collaboration diagram for aud.util.PermutationIterator:

Public Member Functions
	PermutationIterator (int n)
	create new iterator More...
boolean	hasNext ()
int[]	next ()
void	remove ()

Static Public Member Functions
static void	main (String[] args)
	demonstration and test More...

Detailed Description

Iterator over all permutations of length n.

Permutations are represented as int[] arrays with entries 0,..,n-1.

Implementation inspired by std::next_permutation of the C++ standard library: assume ordered sequence and "count up" to lexicographically next sequence. (Requires only sequence as state.)

Definition at line 14 of file PermutationIterator.java.

Constructor & Destructor Documentation

PermutationIterator()

aud.util.PermutationIterator.PermutationIterator

(

int

n

)

create new iterator

Parameters

n	length of permutation

Definition at line 30 of file PermutationIterator.java.

                                    {
    if (n>0) {
      p_=new int[n];
      for (int i=0;i<n;++i)
        p_[i]=i;            // initial
    }
  }

Member Function Documentation

hasNext()

boolean aud.util.PermutationIterator.hasNext

(

)

Definition at line 38 of file PermutationIterator.java.

                                     {
    return p_!=null;
  }

Referenced by aud.util.PermutationIterator.main().

Here is the caller graph for this function:

main()

static void aud.util.PermutationIterator.main ( String[]  args )

static

demonstration and test

Definition at line 77 of file PermutationIterator.java.

                                         {
 
    int n=args.length>0 ? Integer.parseInt(args[0]) : 3;
 
    for (PermutationIterator ii=new PermutationIterator(n);ii.hasNext();) {
      int[] p=ii.next();
      for (int j : p)
        System.out.print(j);
      System.out.println();
    }
  }

References aud.util.PermutationIterator.hasNext().

Here is the call graph for this function:

next()

int[] aud.util.PermutationIterator.next

(

)

Definition at line 42 of file PermutationIterator.java.

                                {
    int[] p = new int[p_.length];
 
    for (int j=0;j<p_.length;++j)
      p[j]=p_[j];
 
    int last=p_.length;
    int i=last-1;
 
    for (;;) {
      int ii=i;
      if (p_[--i]<p_[ii]) {
        int j=last;
        while (p_[i]>=p_[--j]) {}
        swap(i,j);
        reverse(ii,last);
 
        break;
      }
      else if (i==0) {
        //reverse(0,last);
        p_=null;
        break;
      }
    }
 
    return p;
  }

remove()

void aud.util.PermutationIterator.remove

(

)

Exceptions

UnsupportedOperationException

Definition at line 72 of file PermutationIterator.java.

                                 {
    throw new UnsupportedOperationException();
  }

---

The documentation for this class was generated from the following file:

• PermutationIterator.java