Permutation Iterator in java

Question

I want a class, that take in a possitive integer and produce a iterator that let me iterate through all possible of permutation of a list of possitive numbers under the positive integer.
eg. permulator p = paermulator(3)
p.next() -> [0,1,2]
p.next() -> [0,2,1]
p.next() -> [1,0,2]
p.next() -> [1,2,0]
...
which is 6 possible permutations in this case. I have designed a class, but it is incredibly slow, I want to make iterate faster. This is my design:
(I am doing it pruely for that sake that it seems possible. )

    package Mathematica.complexity;
    import java.util.Iterator;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.NoSuchElementException;

/**
 * Tthis will be a class that demonstrate what we call: 
 * a factorial complexity algorithm 
 * it's going to print all the possible permutations of some sort of collection 
 * in java. 
 * <br>
 * A recursive data structure that resembles the process of permutating. 
 * @author dashie
 *
 */
public class FactorialComplexity implements Iterator<List<Integer>>
{

 private List<Integer> G_Data; 


    // sub recursive structure of the class. 
    private FactorialComplexity G_next = null; 

    private int G_ChoosenIndex = 0; 

    private boolean G_canProduceNextElement= true;

    public static void main(String[] args) 
    {


    }

    public FactorialComplexity(int NumbersofElements)
    {
        if(NumbersofElements <0)throw new AssertionError();
        this.G_Data = new LinkedList<>();

        for(int i =0; i< NumbersofElements;i++)this.G_Data.add(i);

        this.prepareSubStructure();

    }

    protected FactorialComplexity(List<Integer> argIn)
    {

        this.G_Data = argIn;
        this.prepareSubStructure();

    }


    /**
     * Using the internal index to return the current element it is 
     * pointing at. 
     * <br></b>I doesn't increment the internal pointer. </b>
     * @return
     */
    public Integer getChoosenElement()
    {
        //if(this.G_Data.size() == 0)return null;
        return this.G_Data.get(this.G_ChoosenIndex);
    }

    /**
     * This function serves for the iterator. 
     * @return
     */
    public List<Integer> getPermutation()
    {
        // two of the base case. 
        if(this.G_Data.size()==0)
        {
            return new LinkedList<>();
        }
        if(this.G_Data.size()==1)
        {
            List<Integer> temp = new LinkedList<>();
            temp.add(this.G_Data.get(0));
            return temp;
        }

        return this.getPermutation_part1(new LinkedList<Integer>());
    }

    private List<Integer> getPermutation_part1(List<Integer> argIn)
    {
        argIn.add(getChoosenElement());
        argIn.addAll(this.G_next.getPermutation());
        return argIn;
    }


    /**
     * <ol>
     * <li>If the sub-structure has next element, increment the sub structure.
     * <li>If not, increment the index in this instance and recreate sub structure. 
     * <li>be careful about the base case please. 
     * </ol>
     * 
     * @return 
     * if this, including sub structure should be incremented. 
     * 
     */
    protected boolean increment()
    {

        if(this.G_next!= null)
        {
            boolean temp = this.G_next.increment();
            int pointer = this.G_ChoosenIndex;
            if(this.G_ChoosenIndex+1<this.G_Data.size())
            {
                if(temp)
                {
                    this.G_ChoosenIndex++;
                    this.prepareSubStructure();
                }
                return false;
            }
            else
            {
                return (this.G_ChoosenIndex+1 == this.G_Data.size())&&temp;
            }
        }
        else
        {
            //empty means not choice can make. 
            return true;
        }
    }




    @Override
    /**
     * All the nodes are at its last index. 
     */
    public boolean hasNext()
    {
        if(!this.G_canProduceNextElement)return false;
        if(this.isAllPointingAtLastIndex())this.G_canProduceNextElement=false;
        return true;
    }


    /**
     * This index in this class instance and 
     * all its sub structure are pointing at the last index? 
     * @return
     */
    boolean isAllPointingAtLastIndex()
    {
        if(this.G_Data.size()<=1)
        {
            return true;
        }
        return this.G_ChoosenIndex+1
                ==
               this.G_Data.size()&&this.G_next.isAllPointingAtLastIndex();
    }



    @Override
    public List<Integer> next() 
    {

        List<Integer> result = this.getPermutation();
        this.increment();
        return result;
    }

    public String toString()
    {
        String s = new String();
        s+= this.G_Data+":"+this.G_ChoosenIndex+"->";
        if(this.G_next!= null)s+= this.G_next.toString();
        return s;
    }



    /**
     * <ol>
     * <li>Base case: the list in this instant is empty. 
     * <li>Make a copy of the local collection, excluding the 
     * element the pointer is pointing to
     * <li>Make connect the this object to its sub structure and recurse. 
     * </ol>
     */
    protected void prepareSubStructure()
    {
        if(this.G_Data.size() == 0)return;
        List<Integer> temp = new LinkedList<>();
        temp.addAll(this.G_Data);
        temp.remove(this.G_ChoosenIndex);
        this.G_next = new FactorialComplexity(temp);
        this.G_next.prepareSubStructure();
    }


    public static int factorial(int n)
    {
        if(n<0)return 0;
        if(n<=1)return 1;
        return n*factorial(n-1);
    }

}

To summarize: The class is recursive like a linked list, each node contains the an index that indicate the element it is pointing at and a list of all the element got passed from the previouse node.

How Naive is this approach? How can I make it faster?

Answer 1

This is a better solution, inspired by https://stackoverflow.com/a/10117424/312172

To achieve, instead of getting a list of elements that are jumbled, we focus on the choices we make when deducting elements from the list. give the function a size, and a number that is smaller than factorial(size); it will return a sequence of choices we need to make to get the permutation.

for example:
getTheIndexOfSelection(100,5)-> for a list of 5 elements, we want the 100th permutation.

it should output: [4, 0, 2, 0, 0]

it means, remove the element at index 4, for the list that got removed, remove element at 0 ....

if the list is[1,2,3,4,5]; this will be the procujure:
[1,2,3,4,5] remove index 4 -> 5
[1,2,3,4] remove index 0 -> 1
[2,3,4] remove index 2 -> 4
[2,3] rovmove index 0 -> 2
[3] remove index 0 -> 3
all the element we removed sequentially is the permutation.

/**
     * Feed this function a number, it gives you a sequence of choices 
     * to make a permutation. 
     * <br>
     * if this return [0,0,0,0]
     * it means remove element at 0, and then remove again... until 
     * reaches the end. 
     * @return
     * 
     * @param
     * len: the length of the list
     * n: the number that got match to a certain permutation. 
     */
    public static int[] getTheIndexOfSelection(int n, int size)
    {
        int[] lst = new int[size];
        return getTheIndexOfSelection( n,  size,  0, lst);

    }




 private static int[] getTheIndexOfSelection(int n, int size, int index, int[] lst)
    {
        if(size==1)
        {
            int[] result = {0}; // a list of one element, you can only choose the one that is in it
            // which is at index 0; 
            return result;
        }

        if(n >= factorial(size))return null; // This is not possible to do. 

        size-=1;
        int   firstchoice = n/factorial(size);

        lst[index]        = firstchoice;

        n = n-firstchoice*factorial(size);

        if(size>1)return getTheIndexOfSelection(n ,size, index+1, lst);
        return lst;
    }

This is a better solution because:

1. The speed really depends on the factorial function, assume factorial is super fast, this will be o(n).
2. It matches numbers to permutation, making the expandable for things like map and iterator.
3. It is not the full solution, the part that is left to solve do is pretty much trivial by now.

Answer 2

An implementation using Heap's Algorithm. It compute next permutations on the fly. And have only one array copying

import java.util.Arrays;
import java.util.Iterator;

class Permutator<E> implements  Iterator<E[]>{

    E[] arr1 = null;
    E[] arr2 = null;
    int size;
    int[] stack = null;

    int index = 0;
    public Permutator( E[] arr ){

        if( arr.length > 0 ){
            arr1 = arr;

            size = arr1.length;
            arr2 = Arrays.copyOf(arr1, size);

            stack = new int[size];
            Arrays.fill(stack, 0);
        }
    }

    @Override
    public boolean hasNext() {
        return (null != arr1 && arr1.length > 0);
    }

    @Override
    public E[] next() {

        // start computing.
        // We will return original array as value of last permutation.
        // This is to make "hasNext() " implementation easy.
        updateValue();
        return arr2;
    }

    protected void updateValue(){

        boolean bret = false;

        for( ; index < size ; ){

            if( stack[index] < index ){

                if( index %2 == 0 ){
                    swap(0, index);
                }else{
                    swap(stack[index], index);
                }

                stack[index]++;           
                index = 0;
                bret = true;
                break;
            }else{
                stack[index] = 0;
                index++;
            }
        }

        if( !bret ){
            // No more permutation available. 
            // Set the original array as return value.
            // Also set arr1 = null , so that hasNext() will return false for next test
            arr2 = arr1;
            arr1 = null;
        }
    }

    private void swap (final int i, final int j) {
        E temp = arr2[i];
        arr2[i] = arr2 [j];
        arr2[j] = temp;
    }
}

Usage:

public static void main(String[] args) {

        Permutator<Integer> perm = new Permutator<Integer>(new Integer[]{1,2,3, 4, 5});
        int count = 0;
        while(perm.hasNext()){
            System.out.println(Arrays.toString(perm.next()));
            count++;
        }
        System.out.println("total: " + count);
    }