7.2.1 1 1 ~ n 배열 생성(전체 배열)[STL__next_permutation()_의 적용]

6272 단어 ext
#include <stdio.h>

#include <math.h>

#include <string.h>

#include <stdlib.h>

#include <string.h>

#include <iostream>

#include <algorithm>

using namespace std;

int a[20];

void print_permutation(int n, int a[], int cur){

    int i, j;

    if(cur == n){

        for(i = 0; i < n; ++i)  printf("%d ",a[i]);

        printf("
"); } else for(i = 1; i <= n; ++i){ bool flag = true; for(j = 0; j < cur; ++j) if(a[j] == i) flag = false; if(flag){ a[cur] = i; print_permutation(n, a, cur+1); } } } int main(){ print_permutation(3, a, 0); return 0; }

STL의 next_ 사용permutation () 이 더 편리합니다.
next_permutation 실현 원리
에서 이 함수를 찾았습니다. 여기서 원리를 간단히 설명합니다.
 
STL에서 next_ 제외permutation 외에 함수prev_permutation, 둘 다 배열 조합을 계산하는 함수입니다.전자는 다음 배열 조합을 구하고, 후자는 이전 배열 조합을 구한다.이른바'다음'과'이전'이라는 책에서 간단한 예를 들었다. 서열 {a, b, c}, 모든 원소는 뒤의 원소보다 작고 사전 서열에 따라 a를 고정한 후에 a는 bc보다 작고 c는 b보다 크다. 그의 다음 서열은 바로 {a, c, b}이고 {a, c, b}의 이전 서열은 {a, b, c}이다. 같은 이치로 모든 6개의 서열을 내놓을 수 있다., b},{c, b, a}, 그중 {a, b, c}는 이전 원소가 없고, {c, b, a}는 다음 원소가 없습니다.
 
next_permutation의 함수 원형은 다음과 같습니다.
template<class BidirectionalIterator>

bool next_permutation(

      BidirectionalIterator _First, 

      BidirectionalIterator _Last

);

template<class BidirectionalIterator, class BinaryPredicate>

bool next_permutation(

      BidirectionalIterator _First, 

      BidirectionalIterator _Last,

      BinaryPredicate _Comp

 );


두 번째 재부팅 함수의 세 번째 매개 변수에 대한 기본 비교 순서는 보다 작습니다.다음 시퀀스를 찾으면 진짜로 돌아가고, 그렇지 않으면 가짜로 돌아갑니다.
그래서 이 문제의 코드는 이렇게 쓸 수 있다.
 1 #include <iostream>

 2 #include <algorithm>

 3 using namespace std;

 4 int main(){

 5     int n,A[100],cur=0;

 6     cin >> n;

 7     int i;

 8     for(i=0; i<n; ++i)  A[i]=i+1;

 9     do{

10         for(i=0; i<n; i++)  cout<<A[i]<<' ';

11         cout<<endl;

12     }

13     while(next_permutation(A,A+n));

14     return 0;

15 }

작은 매듭
next_로permutation 및prev_permutation은 배열 조합을 구하는 데 편리하지만, 헤더 파일 #include 을 포함하는 것을 기억해야 합니다.
마지막 배열은 다음 배열은 없지만 넥스트_permutation은false를 되돌려주지만, 이 방법을 사용하면 시퀀스는 사전 시퀀스의 첫 번째가 됩니다. 예를 들어 cba는 abc가 됩니다.prev_permutation 동리.

좋은 웹페이지 즐겨찾기