8

I am writing a JAVA code to generate all permutations of a integer array. Though I am getting the number of permutations right, the permutations themselves are not correct.

On running I obtain:

Input array Length
3
1
2
3
0Permutation is
1,  2,  3,  
##########################
1Permutation is
1,  3,  2,  
##########################
2Permutation is
3,  1,  2,  
##########################
3Permutation is
3,  2,  1,  
##########################
4Permutation is
1,  2,  3,  
##########################
5Permutation is
1,  3,  2,  
##########################
6  number of permutations obtained
BUILD SUCCESSFUL (total time: 3 seconds)


public class PermulteArray {

    public static int counter = 0;

    public static void Permute(int[] input, int startindex) {
        int size = input.length;

        if (size == startindex + 1) {
            System.out.println(counter + "Permutation is");
            for (int i = 0; i < size; i++) {
                System.out.print(input[i] + ",  ");
            }
            System.out.println();
            System.out.println("##########################");
            counter++;
        } else {
            for (int i = startindex; i < size; i++) {

                int temp = input[i];
                input[i] = input[startindex];
                input[startindex] = temp;
                Permute(input, startindex + 1);
            }
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.println("Input array Length");
        int arraylength = in.nextInt();
        int[] input = new int[arraylength];
        for (int i = 0; i < arraylength; i++) {
            input[i] = in.nextInt();
        }
        counter = 0;
        Permute(input, 0);
        System.out.println(counter + "  number of permutations obtained");
    }
}
6
  • Please write your expected output and actual output. Nov 4, 2012 at 11:14
  • 1
    What do you need help with? The first thing I would do is fix the format of your code and output so its easier to read. I would step through the code in your debugger to see what it doing. Nov 4, 2012 at 11:15
  • in the beginning I have added the obtained output for size 3, input array [1,2,3] I should get [1,2,3] [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] in any order... I am getting... 1, 2, 3, 1, 3, 2, 3, 1, 2, 3, 2, 1, 1, 2, 3, 1, 3, 2, Nov 4, 2012 at 11:17
  • -1 This question shows zero effort (copy-pasting code and output is not considered "effort"). Read SSCCE
    – Bohemian
    Nov 4, 2012 at 11:18
  • I used the debugger too... Basically what I think is happening is that when Permute(int[] input,int startindex) is called (That should permute the subarray startindex... end) the input array gets altered after a few recursive calls, which is unexpected (to me). Nov 4, 2012 at 11:21

9 Answers 9

14
int temp=input[i];
input[i]=input[startindex];
input[startindex]=temp;
Permute(input, startindex+1);

You've swapped an element before calling Permute but you need to swap it back again afterwards to keep consistent positions of elements across iterations of the for-loop.

0
11

This is the best solution I have seen so far :

public static void main(String[] args) {
    int[] a = { 1, 2, 3, 4, 5, 6 };
    permute(0, a);
}

public static void permute(int start, int[] input) {
    if (start == input.length) {
        //System.out.println(input);
        for (int x : input) {
            System.out.print(x);
        }
        System.out.println("");
        return;
    }
    for (int i = start; i < input.length; i++) {
        // swapping
        int temp = input[i];
        input[i] = input[start];
        input[start] = temp;
        // swap(input[i], input[start]);

        permute(start + 1, input);
        // swap(input[i],input[start]);

        int temp2 = input[i];
        input[i] = input[start];
        input[start] = temp2;
    }
}   
1

check this out

for (int i = startindex; i < input2.length; i++) {
            char[] input = input2.clone();
            char temp = input[i];
            input[i] = input[startindex];
            input[startindex] = temp;
            permute(input, startindex + 1);
        }
1
//This will give correct output 

import java.util.Scanner;

public class PermulteArray {

    public static int counter = 0;

    public static void Permute(int[] input, int startindex) {
        int size = input.length;

        if (size == startindex + 1) {
            System.out.println(counter + "Permutation is");
            for (int i = 0; i < size; i++) {
                System.out.print(input[i] + ",  ");
            }
            System.out.println();
            System.out.println("##########################");
            counter++;
        } else {
            for (int i = startindex; i < size; i++) {

                int temp = input[i];
                input[i] = input[startindex];
                input[startindex] = temp;
                Permute(input, startindex + 1);
                temp = input[i];
                input[i] = input[startindex];
                input[startindex] = temp;
            }
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.println("Input array Length");
        int arraylength = in.nextInt();
        int[] input = new int[arraylength];
        for (int i = 0; i < arraylength; i++) {
            input[i] = in.nextInt();
        }
        counter = 0;
        Permute(input, 0);
        System.out.println(counter + "  number of permutations obtained");
    }

}
2
  • Can you please clarify what you've changed? Jan 28, 2016 at 23:51
  • I added this code temp = input[i]; input[i] = input[startindex]; input[startindex] = temp; below Permute(input, startindex + 1);
    – poonam
    Feb 6, 2016 at 9:48
1

You can solve this using recursive calls.

https://github.com/Pratiyush/Master/blob/master/Algorithm%20Tutorial/src/arrays/Permutations.java

public void swap(int[] arr, int i, int j)
{
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

public void permute(int[] arr, int i)
{
    if (i == arr.length)
    {
        System.out.println(Arrays.toString(arr));
        return;
    }
    for (int j = i; j < arr.length; j++)
    {
        swap(arr, i, j); 
        permute(arr, i + 1);  // recurse call
        swap(arr, i, j);      // backtracking
    }
} 

public static void main(String[] args) {

    Permutations permutations = new Permutations();
    int[] arr = {1, 2, 3,4};
    permutations.permute(arr, 0);
}

Also, other approaches are available in

  1. http://www.programcreek.com/2013/02/leetcode-permutations-java/
  2. http://www.programcreek.com/2013/02/leetcode-permutations-ii-java/
1
public class PermuteArray {

    public static void permute(char[] input2, int startindex) {

        if (input2.length == startindex) {
             displayArray(input2);
        } else {
            for (int i = startindex; i < input2.length; i++) {
                char[] input = input2.clone();
                char temp = input[i];
                input[i] = input[startindex];
                input[startindex] = temp;
                permute(input, startindex + 1);
            }
        }
    }


    private static void displayArray(char[] input) {
        for (int i = 0; i < input.length; i++) {
            System.out.print(input[i] + ";  ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        char[] input = { 'a', 'b', 'c', 'd'};
        permute(input, 0);
    }

}
0
import java.util.ArrayList;

public class RecursivePermGen {

    void permGen(int n, int m, ArrayList<Integer> cur) {
        if(m == 0) {
            System.out.println(cur);
            return;
        }
        for(int i = 1; i <= n; i++) {
            cur.add(0, i);
            permGen(n, m-1, cur);
            cur.remove(0);
        }

    }

    public static void main(String[] args) {
        RecursivePermGen pg = new RecursivePermGen();
        ArrayList<Integer> cur = new ArrayList<Integer>();

        pg.permGen(2, 2, cur);
    }
}
0

I have simple answer for this question, you can try with this.

public class PermutationOfString {
    public static void main(String[] args) {
        permutation("123");
    }

    private static void permutation(String string) {
        printPermutation(string, "");
    }

    private static void printPermutation(String string, String permutation) {
        if (string.length() == 0) {
            System.out.println(permutation);
            return;
        }

        for (int i = 0; i < string.length(); i++) {
            char toAppendToPermutation = string.charAt(i);
            String remaining = string.substring(0, i) + string.substring(i + 1);

            printPermutation(remaining, permutation + toAppendToPermutation);
        }
    }
}
0

A solution i have used several times (mostly for testing purposes) is in the following gist. It is based on the well-known algorithm to generate permutations in lexicographic order (no recursion):

/**
 * Compute next (in lexicographic order) permutation and advance to it.
 *
 * Find greater index i for which a j exists, such that:
 * j > i and a[i] < a[j] (i.e. the 1st non-inversion).
 * For those j satisfying the above, we pick the greatest.
 * The next permutation is provided by swapping
 * items at i,j and reversing the range a[i+1..n]
 */
void advanceToNext() {
    // The array `current` is the permutation we start from
    // Find i when 1st non-inversion happens
    int i = n - 2;
    while (i >= 0 && current[i] >= current[i + 1])
        --i;

    if (i < 0) {
        // No next permutation exists (current is fully reversed)
        current = null;
        return;
    }

    // Find greater j for given i for 1st non-inversion
    int j = n - 1;
    while (current[j] <= current[i])
        --j;

    // Note: The range a[i+1..n] (after swap) is reverse sorted
    swap(current, i, j); // swap current[i] <-> current[j]
    reverse(current, i + 1, n); // reverse range [i+1..n]
}

A complete solution (in the form of a class) lies here: https://gist.github.com/drmalex07/345339117fef6ca47ca97add4175011f

2
  • While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes
    – slfan
    Aug 27, 2018 at 16:47
  • 1
    I rewrote the answer according to @slfan 's remarks Aug 28, 2018 at 18:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.