#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

//-----------------------------------------------------------------

// Pandita's algorithm to generate next lexicographic permutation

bool next_permutation(char *L, int n) {
  // Step 1: find rightmost position i such that L[i] < L[i+1]
  int i = n - 2;
  while ((i >= 0) && (L[i] >= L[i+1])) i--;
  if (i==-1) return false;
  
  // Step 2: find rightmost position j to the right of i such that L[j] > L[i]
  int j = i + 1;
  while ((j < n) & (L[j] > L[i])) j += 1;
  j -= 1;
  
  // Step 3: swap L[i] and L[j]
  char tmp = L[i];
  L[i] = L[j];
  L[j] = tmp;
  
  // Step 5: reverse everything to the right of i
  int left = i + 1;
  int right = n - 1;
 
  while (left < right) {
    tmp = L[left];
    L[left] = L[right];
    L[right] = tmp;
    left += 1;
    right -= 1;
  }
             
  return true;
}


//-----------------------------------------------------------------

int main(){
  char L[] = "00000000001111111111";
  int n = strlen(L);
  
  int count_in_church = 0;
  int total_permutations = 0;
  
  while (1) {
    
    total_permutations += 1;
    // check if bride steps into church by checking if
    // the number of ones exceeds the number of zeros
    int cnt_0 = 0;
    int cnt_1 = 0;
    
    
    for (int i=0; i<n; i++) {
      char c = L[i];
      if (c == '0') cnt_0 += 1;
      else cnt_1 += 1;
    
      if (cnt_1 > cnt_0) {
        count_in_church += 1;
        break;
      }
    }
  
  
    if (!next_permutation(L,n)) break;
  }
  
  
  printf("number of times bride entered church: %d\n", count_in_church);
  printf("total permutations: %d\n", total_permutations);

  float ratio = 1.0 * count_in_church / total_permutations;
  printf("probability: %f\n", ratio);

	return 0;
}