Write an application code that will suggest movies from a list randomly and there won\'t be any repeat while suggesting the movies

We can use Fisher-Yates random shuffling algorithm to solve this problem. Firstly, we need to create a map to store indexes of the movies as we will shuffle based on their indexes.

So the map will be:

KEY	VALUE
1	"D-DAY"
2	"RAINCOAT"
3	"OCTOBER"
4	"LUNCHBOX"
5	"BARFI"
6	"RAAZI"
7	"PIKU"

So our movie list will be converted as: [1,2,3,4,5,6,7]

Then we will shuffle using the Fisher-Yates algorithm

At each step iteration, we will suggest movie[i]. Below is the detailed algorithm for suggesting movie randomly

The detailed algorithm will be,

For i=n-1 to 1
    Pick and element in the range [0,i-1] randomly
    Swap the randomly picked element with a[i]
    // since it's not going to be reshuffled again 
    // as we are decrementing i , 
    // thus it's guaranteed that it won't be suggested twice 
    Recommend movie[a[i]]
Decrement i
End for loop

So, how this guarantees unique suggestion each time?

Because, we are fixing the ith element after the swap and decrementing i, so that the movie that got suggested never takes part again in swaps.

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

void recommend_movie_randomly(vector<string> movies)
{
    srand(time(0));

    map<int, string> mymap;
    int n = movies.size();

    for (int i = 0; i < n; i++) {
        mymap[i] = movies[i];
    }

    vector<int> arr(n); //stores the indexes
    for (int i = 0; i < n; i++)
        arr[i] = i;

    //shiffling randomly and suggesting movie 
    //at each iteartion
    for (int i = n - 1; i >= 1; i--) {
        //j will be a random no with in range 0 to i-1
        int j = rand() % i;
        //swap ith index with jth
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;

        //suggest the ith movie now
        cout << "Suggesting next movie...\n";
        cout << mymap[arr[i]] << endl;
    }
}

int main()
{
    //input list
    vector<string> movie_list{ "D-DAY", "RAINCOAT", "OCTOBER", "LUNCHBOX", "BARFI", "RAAZI", "PIKU" };

    cout << "Recommending movies randomly from the list\n";

    recommend_movie_randomly(movie_list);

    return 0;
}

Output:

Recommending movies randomly from the list
Suggesting next movie...
RAAZI
Suggesting next movie...
OCTOBER
Suggesting next movie...
PIKU
Suggesting next movie...
D-DAY
Suggesting next movie...
RAINCOAT
Suggesting next movie...
LUNCHBOX