Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement