暴力算法:排列生成

1.生成1~n的排列
思路:
引入cur(当前确定第cur个数),以(cur+1)的方式递归;
注意:
1).递归函数的位置;
代码:

#include<cstdio>
#include<iostream>
using namespace std ;

void print_permutation ( int n , int *A , int cur ) {
 if ( cur == n ) {
  for ( int i = 0 ; i < n ; i ++ ) printf("%d",A[i]) ;
  printf("\n") ;  //
 }
 else {
  for ( int i = 1 ; i <= n ; i ++ ) {
   int ok = 1 ;
   for ( int j = 0 ; j < cur ; j ++ ) {
    if ( A[j] == i ) {
     ok = 0 ;
     break ;
    }
   }
   if ( ok == 1 ) {
    A[cur] = i ;
    print_permutation ( n , A , cur + 1 ) ;
   }   
  }  
 }
} 

int main() {
 int n , A[100];
 cin>>n ;
 for ( int i = 0 ; i < n ; i ++ ) A[i] = i + 1 ;
 print_permutation ( n , A , 0 ) ;
 return 0 ;
}

2.生成给定数组P的排列(可重集)
思路:
1).算出P中包含 P[ i ] 的次数c1,算出A中前 cur-1 个包含 P[ i ] 的次数c2,比较,若c1大于c2,则 P[ i ] 还可选,每次选择 A[cur] 时遍历整个P数组;
2).当遇到 P[ i ] = P[ i - 1 ] 的情况,不执行整个以它为开头的过程。
比如 P = { 1,1,1 },若均执行,会输出 333 = 27 个 { 1,1,1 } ;只执行第一个时,输出 1 个 { 1,1,1 },第一次循环,挑出第一个1,第二次循环,挑出第一个1,第三次循环,挑出第一个1;(有重集时函数操作的都是第一个数)
代码:

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std ;

void print_permutation ( int n , int *P , int *A , int cur ) {
 if ( cur == n ) {
  for ( int i = 0 ; i < n ; i ++ ) printf("%d",A[i]) ;
  printf("\n") ; 
 }
 else {
  for ( int j = 0 ; j < n ; j ++ ) 
  if ( j == 0 || P[j] != P[j - 1] ) {
   int c1 = 0 , c2 = 0 ; 
   for ( int i = 0 ; i < n ; i ++ ) {
    if ( P[j] == P[i] ) c1 ++ ;
   } 
   for ( int i = 0 ; i < cur ; i ++ ) {
    if ( A[i] == P[j] ) c2 ++ ;
   }
   if ( c1 > c2 ) {
    A[cur] = P[j] ;
    print_permutation ( n , P , A , cur + 1 ) ;
   }
  }
 }
} 

int main() {
 int n ;
 cin>>n ;
 int P[n] , A[n] ;
 for ( int i = 0 ; i < n ; i ++ ) scanf("%d",&P[i]) ;
 print_permutation ( n , P , A , 0 ) ;
 return 0 ;
}

3.下一个排列:next_permutation()
代码:

#include<cstdio>
#include<algorithm>
using namespace std ;

int main() {
 int n ;
 scanf ( "%d",&n ) ;
 int p[n] ;
 for ( int i = 0 ; i < n ; i ++ ) scanf ( "%d", &p[i] ) ;
 sort ( p , p + n ) ;
 do {
  for ( int i = 0 ; i < n ; i ++ ) printf ( "%d",p[i] ) ;
  printf ( "\n" ) ;
 } while ( next_permutation( p , p + n ) ) ;
 return 0 ;
}
上一篇:next_permutation函数


下一篇:独特的排列生成器?