fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <stdbool.h>
  4.  
  5. //-----------------------------------------------------------------
  6.  
  7. // Pandita's algorithm to generate next lexicographic permutation
  8.  
  9. bool next_permutation(char *L, int n) {
  10.   // Step 1: find rightmost position i such that L[i] < L[i+1]
  11.   int i = n - 2;
  12.   while ((i >= 0) && (L[i] >= L[i+1])) i--;
  13.   if (i==-1) return false;
  14.  
  15.   // Step 2: find rightmost position j to the right of i such that L[j] > L[i]
  16.   int j = i + 1;
  17.   while ((j < n) & (L[j] > L[i])) j += 1;
  18.   j -= 1;
  19.  
  20.   // Step 3: swap L[i] and L[j]
  21.   char tmp = L[i];
  22.   L[i] = L[j];
  23.   L[j] = tmp;
  24.  
  25.   // Step 5: reverse everything to the right of i
  26.   int left = i + 1;
  27.   int right = n - 1;
  28.  
  29.   while (left < right) {
  30.     tmp = L[left];
  31.     L[left] = L[right];
  32.     L[right] = tmp;
  33.     left += 1;
  34.     right -= 1;
  35.   }
  36.  
  37.   return true;
  38. }
  39.  
  40.  
  41. //-----------------------------------------------------------------
  42.  
  43. int main(){
  44.   char L[] = "00000000001111111111";
  45.   int n = strlen(L);
  46.  
  47.   int count_in_church = 0;
  48.   int total_permutations = 0;
  49.  
  50.   while (1) {
  51.  
  52.     total_permutations += 1;
  53.     // check if bride steps into church by checking if
  54.     // the number of ones exceeds the number of zeros
  55.     int cnt_0 = 0;
  56.     int cnt_1 = 0;
  57.  
  58.  
  59.     for (int i=0; i<n; i++) {
  60.       char c = L[i];
  61.       if (c == '0') cnt_0 += 1;
  62.       else cnt_1 += 1;
  63.  
  64.       if (cnt_1 > cnt_0) {
  65.         count_in_church += 1;
  66.         break;
  67.       }
  68.     }
  69.  
  70.  
  71.     if (!next_permutation(L,n)) break;
  72.   }
  73.  
  74.  
  75.   printf("number of times bride entered church: %d\n", count_in_church);
  76.   printf("total permutations: %d\n", total_permutations);
  77.  
  78.   float ratio = 1.0 * count_in_church / total_permutations;
  79.   printf("probability: %f\n", ratio);
  80.  
  81. 	return 0;
  82. }
  83.  
Success #stdin #stdout 0s 10320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
number of times bride entered church: 167960
total permutations: 184756
probability: 0.909091
https://ideone.com/An2xpZ
language:
C (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!