전체 배열 알고리즘:재 귀 와 비 재 귀 실현
6378 단어 전체 배열
C(n,m),예 를 들 어 C(5,2)=5!/(2!*3!)=10.참고 하 세 요.
만약 P(n,n)를 요구한다 면,예 를 들 어 P(3,3)=3!=6.본 글 에서 언급 한 전체 배열 알고리즘 을 사용 합 니 다.
P(n,m),예 를 들 어 P(5,2)=5!/(5-2)!=20.먼저 C(n,m)를 구하 고 각 조합 에 P(m,m)를 구하 면 됩 니 다.왜냐하면 P(n,m)=C(n,m)*P(m,m)
1.비 귀속 실현 nextpermutation
1.1 기본 사상
주:이 알고리즘 은 배 열 된 각 요소 간 에'Natural Order'가 있어 야 합 니 다.즉,이 요소 들 은 질서 있 는 서열 을 구성 할 수 있 고 JAVA 에서 Comparable 을 실현 하여 완성 할 수 있 습 니 다.
1.초기 대기 열 을 정렬 하고 모든 배열 에서 가장 작은 배열 Pmin 을 찾 습 니 다. 2.Pmin 보다 크 고 다른 것 보다 작은 배열 P(min+1)를 찾 습 니 다. 3.가장 큰 배열 을 찾 을 때 까지 두 번 째 단 계 를 반복 해서 실행 합 니 다.알고리즘 이 끝 날 때 까지.
예 를 들 어 ABCDE 를 배열 하 는 것 은 모든 배열 에서 가장 작은 배열 이 고 ABCDE 보다 큰 배열 은 ABCED 이다.
1.2 알고리즘 설명
주어진 시퀀스 P=A1A2A 3.................................................................................1.뒤에서 앞으로(즉,An->A1 에서)첫 번 째 쌍 이 오름차 순 인 인접 요 소 를 찾 습 니 다.즉,Ai
1.3 코드
/* Print the all-permutation of the given int array. */
void next_permutation(int a[], int length)
{
if (length < 2)
{
return;
}
while (true)
{
print_array(a, length); // print the permutation
int i, j;
for (i = length-2; i >= 0; --i)
{
if (a[i] < a[i + 1])
break;
else if (i == 0)
return;
else
;
}
for (j = length-1; j > i; --j)
{
if (a[j] > a[i])
break;
else
;
}
swap(a, i, j);
reverse(a, i + 1, length - 1);
}
}
/* Reverse the elements between a[i] and a[j], inclusive. */
void reverse(int a[], int i, int j)
{
for (; i<j; i++, j--)
{
swap(a, i, j);
}
}
/* Swap two elements in an int array. */
void swap(int *a, int i, int j)
{
a[j] ^= a[i];
a[i] ^= a[j];
a[j] ^= a[i];
}
/* Print an int array to the standard output stream. */
void print_array(int a[], int length)
{
std::cout << "[";
for (int i = 0; i < length-1; i++)
{
std::cout << a[i] << ", ";
}
std::cout << a[length-1] << "]" << std::endl;
}2.귀속 실현
참조
좋은 웹페이지 즐겨찾기
