我編寫的代碼采用數(shù)組的元素并遍歷數(shù)組以給出所有排列。但我需要它只顯示一定數(shù)量的排列：最終代碼僅給出 9 個元素的 6 個排列（換句話說，打印總共 362880 個輸出的前 60480 個排列）。為簡單起見，我使用數(shù)組中的 4 個元素，并打印出所有 24 個排列。但我需要代碼適用于任意數(shù)量的排列。例如，如果我需要它打印出 1-permutation，代碼應(yīng)該打印前 4 個排列 - ABCD、ABDC、ACBD 和 ACDB。我不確定如何解決這個問題。public static void main(String[] args) { // TODO Auto-generated method stub String[] myArray = {"A","B","C", "D"}; int size = myArray.length; permutation(myArray, 0, size-1); // Calculate Permutations int n=size; int r=6; // subject to change int p = n - r; int total=1; int total2=1; int total3=0; for (int top=n; top>0; top--) { total *= top; } if ((n-r<0)) { System.out.println("r value cannot be greater than array size"); total3=0; } else { for (int bot=1; bot<=p; bot++) { if (p==0) // should be -- else if (p==0) -- after correction { total2=1; } else { total2 *= bot; } } total3 = total/total2; } System.out.printf("%d permutations of %d elements = %d\n",r,n,total3); // end calculation}// end main// print arraypublic static void prtArray(String[] myArray, int size){ for(int i=0; i<size; i++) { System.out.printf("%s", myArray[i]); } System.out.println();}// swap elements public static void swap(String[] myArray, int i, int j) { String temp; temp = myArray[i]; myArray[i]=myArray[j]; myArray[j]=temp;}// permutation private static void permutation(String[] myArray, int b, int e){ if (b == e) prtArray(myArray, e+1); // accounts for array of size 1 else { for(int i = b; i <= e; i++) { swap(myArray, i, b); permutation(myArray, b+1, e); swap(myArray, i, b); } }}}
1 回答
慕標(biāo)5832272
TA貢獻(xiàn)1966條經(jīng)驗 獲得超4個贊
我假設(shè)您不希望元素在排列中重復(fù)。例如。
如果輸入陣列{1, 2, 3, 4}，則對于長度3： 123，124等是有效的排列，但122還是111不是。
為了避免挑選已經(jīng)挑選的元素，我們需要visited在遞歸中傳遞一個數(shù)組。
public class Main {
// Maintain a global counter. After finding a permutation, increment this.
private static int count = 0;
// pos is the current index, and K is the length of permutation you want to print, and N is the number of permutation you want to print.
private static void printPermutations(int[] arr, int[] visited, int pos, int K, int N, String str) {
// We have already found N number of permutations. We don't need anymore. So just return.
if (count == N) {
return;
}
if (pos == K) {
System.out.println(str);
count++; // we have found a valid permutation, increment counter.
return;
}
for (int i = 0; i < arr.length; i++) {
// Only recur if the ith element is not visited.
if (visited[i] == 0) {
// mark ith element as visited.
visited[i] = 1;
printPermutations(arr, visited, pos + 1, K, N, str + arr[i]);
// unmark ith element as visited.
visited[i] = 0;
}
}
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4};
int[] visited = {0, 0, 0, 0}; // same as size of input array.
count = 0; // make sure to reset this counter everytime you call printPermutations.
// let's print first 4 permutations of length 3.
printPermutations(arr, visited, 0, 3, 4, "");
}
}
輸出：
對于 N = 4 和 K = 3（即長度為 3 的前 4 個排列）：
printPermutations(arr, visited, 0, 3, 4, "");
123
124
132
134
對于 N = 4 和 K = 4（即長度為 4 的前 4 個排列）：
printPermutations(arr, visited, 0, 4, 4, "");
1234
1243
1324
1342
添加回答
舉報
0/150
提交
取消