algorithms/src/01_random_permutation/main.cpp at main · ak4shravikumar/algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <unordered_set>

using namespace std;
/*

code to generate sandom permutation of a given array


a permutation is good if A[i] != i for any i


*/
#include <iostream>
#include <vector>
#include <map>
#include <algorithm> // For shuffle
#include <random>    // For random_device and mt19937
#include <ctime>

vector<int> random_vector() {

    vector<int> v;
    for(int i = 1; i < 64; i++){
        v.push_back(i);
    }
    set<string> s;


    static random_device rd;
    static mt19937 rng(rd());

    // Shuffle the vector
    shuffle(v.begin(), v.end(), rng);

    return v;
}

int maxUpdates(vector<int> arr){
    int count = 0;
    int max = arr[0];
    for(int i = 0; i < arr.size(); i++){
        if(arr[i] > max){
            max = arr[i];
            count++;
        }
    }

    return count;
}

int main() {
    // map<vector<int>, int> mpp;

    // for (int i = 0; i < 600000; i++) {
    //     vector<int> v = random_vector();
    //     mpp[v] += 1;
    // }

    // for (const auto &it : mpp) {
    //     cout << "vector: ";
    //     for (int i : it.first) {
    //         cout << i << " ";
    //     }
    //     cout << "count: " << it.second << endl;
    // }

    double cnt = 0;
    int itr = 100000;

    for (int i = 0; i < itr; i++) {
        vector<int> v = random_vector();
        int c = maxUpdates(v);
        cnt += c;
        cnt / itr;
    }


    cout << "Average: " << cnt / itr << endl;


    return 0;
}