How to generate permutations of the elements in an array

Backtracking technique can be employed to generate a list of permutations of the elements in an array.

For every iteration, we choose an element as a prefix and recursively permute the remaining elements. The order of growth of algorithm is O(n!).

import java.util.Arrays;

public class ArrayPermutation {

    private static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;

    private static void permute(Comparable[] a, int lo, int hi) {
        if (hi <= lo) {
        for (int i = lo; i <= hi; i++) {
            exch(a, lo, i);
            permute(a, lo + 1, hi);
            exch(a, i, lo);

    public static void permute(Comparable[] a) {
        permute(a, 0, a.length - 1);

    // == Test Client =========================================================
    public static void main(String[] args) {
        // 1. Permute characters in an array.
        Character[] ch = { 'A', 'B', 'C', 'D' };

         // 2. Permute Integers in an array.
         Integer[] in = { 1, 2, 3, 4, 5 };

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.