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?
CodePudding user response:
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));
}
}
}
}
CodePudding user response:
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.