Permutation Algorithm Without Recursion? Java

Permutations without recursive function call

Here is a simple solution to compute the nth permutation of a string:

function string_nth_permutation(str, n) {
    var len = str.length, i, f, res;

    for (f = i = 1; i <= len; i++)
        f *= i;

    if (n >= 0 && n < f) {
        for (res = ""; len > 0; len--) {
            f /= len;
            i = Math.floor(n / f);
            n %= f;
            res += str.charAt(i);
            str = str.substring(0, i) + str.substring(i + 1);
        }
    }
    return res;
}

The algorithm follows these simple steps:

first compute f = len!, there are factorial(len) total permutations of a set of len different elements.
as the first element, divide the permutation number by (len-1)! and chose the element at the resulting offset. There are (len-1)! different permutations that have any given element as their first element.
remove the chosen element from the set and use the remainder of the division as the permutation number to keep going.
perform these steps with the rest of the set, whose length is reduced by one.

This algorithm is very simple and has interesting properties:

It computes the n-th permutation directly.
If the set is ordered, the permutations are generated in lexicographical order.
It works even if set elements cannot be compared to one another, such as objects, arrays, functions...
Permutation number 0 is the set in the order given.
Permutation number factorial(a.length)-1 is the last one: the set a in reverse order.
Permutations outside this range are returned as undefined.

It can easily be converted to handle a set stored as an array:

function array_nth_permutation(a, n) {
    var b = a.slice();  // copy of the set
    var len = a.length; // length of the set
    var res;            // return value, undefined
    var i, f;

    // compute f = factorial(len)
    for (f = i = 1; i <= len; i++)
        f *= i;

    // if the permutation number is within range
    if (n >= 0 && n < f) {
        // start with the empty set, loop for len elements
        for (res = []; len > 0; len--) {
            // determine the next element:
            // there are f/len subsets for each possible element,
            f /= len;
            // a simple division gives the leading element index
            i = Math.floor(n / f);
            // alternately: i = (n - n % f) / f;
            res.push(b.splice(i, 1)[0]);
            // reduce n for the remaining subset:
            // compute the remainder of the above division
            n %= f;
            // extract the i-th element from b and push it at the end of res
        }
    }
    // return the permutated set or undefined if n is out of range
    return res;
}

clarification:

f is first computed as factorial(len).
For each step, f is divided by len, giving exacty the previous factorial.
n divided by this new value of f gives the slot number among the len slots that have the same initial element. Javascript does not have integral division, we could use (n / f) ... 0) to convert the result of the division to its integral part but it introduces a limitation to sets of 12 elements. Math.floor(n / f) allows for sets of up to 18 elements. We could also use (n - n % f) / f, probably more efficient too.
n must be reduced to the permutation number within this slot, that is the remainder of the division n / f.

We could use i differently in the second loop, storing the division remainder, avoiding Math.floor() and the extra % operator. Here is an alternative for this loop that may be even less readable:

        // start with the empty set, loop for len elements
        for (res = []; len > 0; len--) {
            i = n % (f /= len);
            res.push(b.splice((n - i) / f, 1)[0]);
            n = i;
        }

String permutations in Java (non-recursive)

Permutation with repetitions

When you have n things to choose from ... you have n choices each time!

When choosing r of them, the permutations are:

n × n × ... (r times) = n^r

I'm presenting 2 cases. First case is when the we know the size of n and r already, and its the easy one. The second when n and r are dynamic.

//when n and r are known statically

class Permutation
{
    public static void main(String[] args)
    {
        char[] values = {'a', 'b', 'c', 'd'};
        int n = values.length;
        int r = 2; 

        int i = 0, j = 0;
        for(i=0; i<n; i++)
        {
            for(j=0; j<n; j++)
            {
                System.out.println(values[j] + " " + values[i]);
            }
        }
    }
}

//when n and r are known only dynamically

class Permutation
{
    public static void main(String[] args)
    {
        char[] values = {'a', 'b', 'c', 'd'};
        int n = values.length;
        int r = 2; 
        int i[] = new int[r];
        int rc = 0;
        for(int j=0; j<Math.pow(n,r); j++)
        {

            rc=0;
            while(rc<r)
            {
                System.out.print(values[i[rc]] + " ");
                rc++;
            }
            System.out.println();
            rc = 0;
            while(rc<r)
            {
                if(i[rc]<n-1)
                {
                    i[rc]++;
                    break;
                }
                else
                {
                    i[rc]=0;
                }
                rc++;
            }
        }
    }
}

Generating all permutations of a given string

public static void permutation(String str) { 
    permutation("", str); 
}

private static void permutation(String prefix, String str) {
    int n = str.length();
    if (n == 0) System.out.println(prefix);
    else {
        for (int i = 0; i < n; i++)
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
    }
}

(via Introduction to Programming in Java)

Finding permutations of Array without for loops

The following recursive algorithm will attempt to print every subset of {1,.., n}. These subsets are in one to one with numbers between 0 and 2^n-1 via the following bijection: to an integer x between 0 and 2^n-1, associate the set that contains 1 if the first bit of x is set to one, 2 if the second bit of x is set to one, ..

void print_all_subsets (int n, int m, int x) {
    if (x==pow(2,n)) {
        return;
    }
    else if (x has m bits set to one) {
        print the set corresponding to x;
    }
    print_all_subsets(n,m,x+1);
}

You need to call it with n = 5 (in your case), m=3 (in your case), and x = 0.

Then you need to implement the two functions "print the set corresponding to x" and "x has m bits set to one" without for loops... but this is easily done using again recursion.

However, I think this is more of a challenge -- there is no point in completely eliminating for-loops, what makes sense is just to use them in a smart way.

An algorithm for enumerating all permutations of the numbers {1,2,...,n} using an stack

Considering that the function already have access to character array input (if you are using java) or string input if the language you are using allows you to edit the characters in string.
Its less efficient than Heap algorithm but more simple and easy to understand

  void permutate(int i){
  //starts  
      //  n is the size of input.
     n = input.size
    if(i==n){
        print(input);

    }
    else {
        for(int j=i; j<n; j++){

            swap( input[i] , input[j] );
            permutate( i+1 );
            swap( input[i] , input[j]);

        }
    }
    //end
}

Permutation algorithm that creates an array of all permutations

Permutation can be solved in a typical Backtrack algorithm in which we have to traverse all possibilities in the state space. Backtrack is a very important algorithm and my suggestion is that you have a look at it(which is usually in a recursion form) and try to master the basic idea of it, rather than trying to solving permuation problem in your own way.

Basically to find a permutaion we have to walk n steps(setting one bit is one step), after we choose one bit for each step, we have a permutation, so we have one possible solution(say, it is 1,2,3,4,5,6). After that, we backtrack to the second last bit, note that we chosed 5 in our first solution, but we can have another choice 6, after that we only have one choice for the last bit which is 5. For other solutions we continue to backtrack to the third last bit, fourth last bit..., and so on. That is the reason why backtrack is named.

You can compare backtrack with DFS, or traveral algorithm on a binary tree. They are in many places very similar with each other.

Below is my solution for this problem in which the result is an arrayList and permutaion is given according to 1...n instead of 0...n-1, but the thought in it is exactly the same.

class Solution {
public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> permutations=new ArrayList();
    backtrack(permutations,new ArrayList<Integer>(),nums);
    return permutations;
}

private void backtrack(List<List<Integer>> permutations,List<Integer> tempList,int[] nums){
    if(tempList.size()==nums.length){
        permutations.add(new ArrayList<Integer>(tempList));
        return;
    }

    for(int i=0;i<nums.length;i++){
        if(tempList.contains(nums[i])){
            continue;
        }

        tempList.add(nums[i]);    
        backtrack(permutations,tempList,nums);
        tempList.remove(tempList.size()-1);
    }

}

}

Javascript Heap's algorithm (non-recursive)

The problem is that arrays are just references so when you push in the array you are just pushing a reference to it. So, on the next iteration you update the array and when you look at the final output, all the indexes will be the same since it is the same array.

So what can you do? clone it.

allPermutations.push(arr.slice(0));