标签： 全排列

遇到《机率课》这么一道作业题。

除了枚举，我是没想到任何方法。

欲用程序解决之，用1~8表示每朵花的漂亮程度，8为最美，但要求{1,2,3,4,5,6,7,8}全排列的算法，实在看得晕。

全排列的意思：例如有{1,2,3}，则它可以有以下排列{1,2,3},{1,3,2},{2,1,3}{2,3,1}{3,1,2}{3,2,1}.

要用枚举解出上面的概率题，则先要把1到8的所有排列举出，判断每一个排列是否能让柏拉图找到最美丽的花。

发现C++标准库里，有求全排列的算法。algorithm包里的next_permutation函数，可以列举数组的每个排列。

#include      // std::cout
#include     // std::next_permutation, std::sort
using namespace std;

int myints[] = {1,2,3,4,5,6,7,8}; // Represents the flowers. Rank 8 means the most beautiful one.
int success_times = 0; // Record how many times are succeed.

// This function checks if the current array can make platon succeed to find the most beautiful flower.
// if it does, increse the success_times by 1 and return true, otherwise return false.
bool check_succeed(){
	int biggest_num_in_first_three = 0;
	// Get the biggest number in the first three places.
	for(int i=0; i<3; i++){
		if(myints[i]>biggest_num_in_first_three) biggest_num_in_first_three = myints[i];
	}
	if (biggest_num_in_first_three == 8) return false;
	
	// Find the first number that bigger than the biggest_num_in_first_three;
	int result = 0;
	for(int i=3; i<8; i++){
		if(myints[i]>biggest_num_in_first_three){
			result = myints[i];
			break;
		}
	}
	if(result == 8){
		success_times++;
		return true;
	}
	return false;
}

int main () {

  sort (myints,myints+8);
  do {
  check_succeed();
  } while ( std::next_permutation(myints,myints+8) );

  cout << success_times<<'\n';  // Print out success times.
  cout << (float)success_times/(8*7*6*5*4*3*2*1); // Print out the probability.

  return 0;
}