Java permutations
I am trying to run my code so it prints cyclic permutations, though I can only get it to do the first one at the moment. It runs correctly up to the point which I have marked but I can't see what is going wrong. I think it has no break in the while loop, but I'm not sure. Really could do with some help here.
package permutation;
public class Permutation {
static int DEFAULT = 100;
public static void main(String[] args) {
int n = DEFAULT;
if (args.length > 0)
n = Integer.parseInt(args[0]);
int[] OA = new int[n];
for (int i = 0; i < n; i++)
OA[i] = i + 1;
System.out.println("The original array is:");
for (int i = 0; i < OA.length; i++)
System.out.print(OA[i] + " ");
System.out.println();
System.out.println("A permutation of the original array is:");
OA = generateRandomPermutation(n);
printArray(OA);
printPemutation(OA);
}
static int[] generateRandomPermutation(int n)// (a)
{
int[] A = new int[n];
for (int i = 0; i < n; i++)
A[i] = i + 1;
for (int i = 0; i < n; i++) {
int r = (int) (Math.random() * (n));
int swap = A[r];
A[r] = A[i];
A[i] = swap;
}
return A;
}
static void printArray(int A[]) {
for (int i = 0; i < A.length; i++)
System.out.print(A[i] + " ");
System.out.println();
}
static void printPemutation(int p[])// (b)
{
System.out
.println("The permutation is represented by the cyclic notation:");
int[] B = new int[p.length];
int m = 0;
while (m < p.length)// this is the point at which my code screws up
{
if (!check(B, m)) {
B = parenthesis(p, m);
printParenthesis(B);
m++;
} else
m++;
}//开发者_开发知识库 if not there are then repeat
}
static int[] parenthesis(int p[], int i) {
int[] B = new int[p.length];
for (int a = p[i], j = 0; a != B[0]; a = p[a - 1], j++) {
B[j] = a;
}
return B;
}
static void printParenthesis(int B[]) {
System.out.print("( ");
for (int i = 0; i < B.length && B[i] != 0; i++)
System.out.print(B[i] + " ");
System.out.print(")");
}
static boolean check(int B[], int m) {
int i = 0;
boolean a = false;
while (i < B.length || !a) {
if ((ispresent(m, B, i))){
a = true;
break;
}
else
i++;
}
return a;
}
static boolean ispresent(int m, int B[], int i) {
return m == B[i] && m < B.length;
}
}
Among others you should check p[m] in check(B, p[m]) instead of m:
in static void printPemutation(int p[]):
while (m < p.length){
if (!check(B, p[m])) {
B = parenthesis(p, m);
printParenthesis(B);
}
m++;
}
then
static boolean check(int B[], int m) {
int i = 0;
while (i < B.length) {
if (m == B[i]) {
return true;
}
i++;
}
return false;
}
this does somehow more what you want, but not always i fear...
精彩评论