문자열의 순열을 재귀 적으로 생성하는 알고리즘을 읽었습니다.
invoke the function with j = 1 if (j == length of string) print the string and return else for (i = j to length of string) interchange jth character with ith character call function on j + 1
다음과 같이 Java를 사용하여 구현했습니다.
class PERMUTATION {
private int count = 1;
private char[] arr = {'A', 'B', 'C'};
public void perm(int k) {
if (k == 3) {
System.out.print(count+++".");
for (int i = 0; i < 3; ++i)
System.out.print(arr[i]+" ");
System.out.println();
return;
}
for (int i = k; i <= 3; ++i) {
/*interchanging ith character with kth character*/
char c = arr[i - 1];
arr[i - 1] = arr[k - 1];
arr[k - 1] = c;
perm(k + 1);
}
}
public static void main(String []args) {
System.out.println("the permutations are");
PERMUTATION obh=new PERMUTATION();
obh.perm(1);
}
}
하지만 내 프로그램은 중복 순열을 생성합니다. 왜?
이 알고리즘은 "원본"배열이 변경되지 않은 경우 작동하므로 각 인덱스가 올바르게 처리됩니다.
코드의 출력을 살펴 보겠습니다.
1.ABC
2.ACB
3.CAB
4.CBA
5.ABC
6.ACB
보시다시피, 반복에서. 3, B 를 첫 번째 인덱스 로 이동해야하는 경우 대신 C 를 이동 해야합니다. B 를 이미 다른 위치 로 이동했기 때문 입니다. 이 사실로 인해 B 는 첫 번째 지수를 올릴 기회가 없으며 2와 3 사이에서만 "반동"할 것입니다.
주요 문제는 "소스"배열을 변경한다는 것입니다. 이를 피하면 알고리즘이 올바르게 작동합니다.
class PERMUTATION {
private int count = 1;
public void perm(char[] arr, int k) {
if (k == 3) {
System.out.print(count++ + ".");
for (int i = 0; i < 3; ++i)
System.out.print(arr[i] + " ");
System.out.println();
return;
}
char[] arr2 = arr.clone(); // clone the passed array, so we don't mess it up
for (int i = k; i <= 3; ++i) {
/* interchanging ith character with kth character */
char c = arr2[k - 1];
arr2[k - 1] = arr2[i - 1];
arr2[i - 1] = c;
perm(arr2, k + 1);
}
}
public static void main(String[] args) {
System.out.println("the permutations are");
PERMUTATION obh = new PERMUTATION();
obh.perm(new char[] {'A', 'B', 'C'}, 1); // pass the original array
}
}
출력은 다음과 같습니다.
1.ABC
2.ACB
3.BAC
4.BCA
5.CAB
6.CBA
BTW : 마음하시기 바랍니다 자바 명명 규칙을 그래서 당신의 클래스를 호출하지 않는, PERMUTATION사용 Permutation대신.
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다