a combination of permutations of elements in a java array

user_17301433 0
Viewed 39

I made a code that should show the entire combination of permutations of elements in an array.

    package com.company;

import java.util.ArrayList;
import java.lang.Math;
import java.util.Collections;
import java.util.List;

public class Main {

    public static void main(String[] args) {
     first(3);
    }

    static int factorial(int n) {
        int res = 1;
        for (int i = 2; i <= n; i++) {
            res *= i;
        }
        return res;
    }

   static void first(int n){
      int[] array = new int[n];
        for(int i = 0; i < n;i++){
          array[i]=i+1;
        }
        for(int i = 0; i < factorial(n);i++){
            for(int j = 0; j < n; j++) {
                if(j==n-1){
                    continue;
                }
                int t = array[j];
                array[j] = array[j+1];
                array[j+1] = t;
            }
            for(int k =0;k<n;k++){
                System.out.print(array[k]);
            }
            System.out.println();
            }


        }
   }

What should it be:

123 213 231 132 312 321

But it turns out like this:

231 312 123 231 312 123

How can a permutation be done the way it should?

java
2 Answers

It's better if you handle your set of elements to permute as a string, there are numerous examples over the internet, like:

 public class Permute {
    public static void main(String[] args) {
        String str = "123";
        permute(str);
    }
    public static void permute(String str) {
        permute("", str);
    }
    public static void permute(String prefix, String str) {
        int n = str.length();
        if (n == 0) {
            System.out.println(prefix);
        } else {
            for (int i = 0; i < n; i++) {
                permute(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
            }
        }
    }
}
user_150623610

Let's step back and review your underlying idea: I assume that you always take a pair of neighboring values in the array and swap those. So for the first step, you are swapping the values of indices 0 and 1, for the second step, you are swapping 1 and 2 etc. If you reach the end of your array, you are going back to the start, thus swapping indices n-1 and 0, then 0 and 1 again and so on.

Taking these preliminary thoughts into account, I came up with the following approach within the method permutation that uses mainly a while loop to find all factorial(n) permutations:

public class Main {

    public static void main(String[] args) {
        permutation(3);
    }

    static int factorial(int n) {
        int res = 1;
        for (int i = 2; i <= n; i++) {
            res *= i;
        }
        return res;
    }

    static void print_permutation(int[] array) {
        for (int k = 0; k < array.length; k++) {
            System.out.print(array[k]);
        }
        System.out.println();
    }

    static void permutation(int n) {
        int[] array = new int[n];
        for (int i = 0; i < n; i++){
            array[i] = i+1;
        }
        print_permutation(array);
        int counter = factorial(n);
        int i = 0;
        int j = i+1;
        while (counter > 1) {
            int t = array[i];
            array[i] = array[j];
            array[j] = t;
            print_permutation(array);
            // Swap the next pair of neighbors.
            // If there is no next value, use the first value again.
            if (i+1 == n) {
                i = 0;
            } else {
                i++;
            }
            if (j+1 == n) {
                j = 0;
            } else {
                j++;
            }
            counter--; // Stop after factorial(n) permutations.
        }

    }

}

The first step is similar to your own idea, just creating an array from 1 to n and printing the "default" permutation.

I reused your factorial function to create a counter value, which tells me when to stop looking for new permutations (it is used as a break condition in the while loop). I also added a little helper function that does the printing (which is not necessary, but better for understanding the overall idea of the algorithm in the method permutation).

Within the while loop, I basically just do what I already described above, always swapping the neighboring pairs of values (or jumping back to the start of the array) until counter has been decreased to 1.

For permutation(3), this program returns:

123
213
231
132
312
321

Unfortunately, this doesn't lead to correct results for e.g. permutation(4), thus I think, the general idea is not correct here.

user_115834840
Related