Question

How can I write this code (posted below) using vectors instead of arrays?

This is the task I have and the code below is for Task 1.3:

Generate twenty random permutations of the number 0, 1, 2, ..., 9 using of the algorithms you designed for Task 1.3. Store these permutations into a vector and print them to the screen with the additional information of unchanged positions and number of calls torand(). Calculate the total numbers of unchanged positions. Compare the outcomes of two approaches of random permutation generation.

#include <iostream>

#define SIZE 10

using namespace std;

//O(n^2) = Quadratic time

//Nested Loop

//More operations involved so time execution is longer

int methodOne(int a[]) { //function to randomly insert 0 to 9 into an array

  

int count = 0; //variable to count number of times rand() is used

for(int i = 0; i < SIZE; i++){ //We run a loop for every number to be entered into the array

bool flag = false;

int pos=-1;

while(!flag) {//we run for loop till a new number is generated

flag = true;

pos = rand() % 10;

count++;

for(int j = 0; j < SIZE; j++){

if(a[j] == pos)

flag = false;

}

}

a[i] = pos; //entering the number into the array

}

return count; //returning number of times rand() was called

}

//O(n) = Linear time

//When an algorithm accepts n input size, it would perform n operations as well.

//less operations = less execution time

int methodTwo(int a[]) { //function to randomly insert 0 to 9 into an array

  

int count=0; //variable to count number of times rand() is used

for(int i=0;i<SIZE;i++){

int pos=-1;

while(a[pos] != -1) { //running loop till an unoccupied position is found

  

pos = rand()%10;

count++;

}

a[pos] = i; //entering the number into the array

}

return count; //returning number of times rand() was called

}

int main() {

srand(static_cast<unsigned int>(time(nullptr)));

int a[] = {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}; //filling the array with random numbers

int count=methodOne(a);

cout<< "First Approach: "<< endl;

for (int i : a) {

cout << i << " ";

}

cout<< endl;

cout<< "Calls to rand() function: "<< count << endl;

cout<< endl;

int b[] = {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1};

count = methodTwo(b);

cout<< "Second Approach: "<< endl;

for (int i : b) {

cout << i << " ";

}

cout<< endl;

cout<< "Calls to rand() function: "<< count << endl;

  

int unchangedPos = 0;

cout << "Total number of unchanged position is: ";

for (int i = 0; i < SIZE; ++i) {

if (a[i] == b[i]) { // check if a[i] == b[i] if yes then increment unchangedPos

unchangedPos++;

}

}

cout << unchangedPos << endl;

  

return 0;

}

Answer 1

#include <iostream>
#include <bits/stdc++.h>
#include <vector>
#define SIZE 10

using namespace std;

//O(n^2) = Quadratic time

//Nested Loop

//More operations involved so time execution is longer

int methodOne(vector<int> &a) //function to randomly insert 0 to 9 into an array
{

int count = 0; //variable to count number of times rand() is used

for(int i = 0; i < SIZE; i++) //We run a loop for every number to be entered into the array
{

bool flag = false;

int pos=-1;

while(!flag) //we run for loop till a new number is generated
{

flag = true;

pos = rand() % 10;

count++;

for(int j = 0; j < SIZE; j++)
{

if(a[j] == pos)

flag = false;

}

}

a[i] = pos; //entering the number into the array

}

return count; //returning number of times rand() was called

}

//O(n) = Linear time

//When an algorithm accepts n input size, it would perform n operations as well.

//less operations = less execution time

int methodTwo(vector<int> &a) //function to randomly insert 0 to 9 into an array
{

int count=0; //variable to count number of times rand() is used

for(int i=0; i<SIZE; i++)
{

int pos=-1;

while(a[pos] != -1) //running loop till an unoccupied position is found
{

pos = rand()%10;

count++;

}

a[pos] = i; //entering the number into the array

}

return count; //returning number of times rand() was called

}

int main()
{
vector<int> c;
vector<int> d;

srand(static_cast<unsigned int>(time(0)));

for(int i=0; i<SIZE; i++) //filling the array with random numbers
c.push_back(-1);
int count=methodOne(c);

cout<< "First Approach: "<< endl;

for (int i=0; i<10; i++)
{

cout << c[i] << " ";

}

cout<< endl;

cout<< "Calls to rand() function: "<< count << endl;

cout<< endl;

for(int i=0; i<SIZE; i++) //filling the array with random numbers
d.push_back(-1);

count = methodTwo(d);

cout<< "Second Approach: "<< endl;

for (int i=0; i<10; i++)
{

cout << d[i] << " ";

}

cout<< endl;

cout<< "Calls to rand() function: "<< count << endl;

int unchangedPos = 0;

cout << "Total number of unchanged position is: ";

for (int i = 0; i < SIZE; ++i)
{

if (c[i] == d[i]) // check if a[i] == b[i] if yes then increment unchangedPos
{

unchangedPos++;

}

}

cout << unchangedPos << endl;

return 0;
}