...
/Feature #11: Generate Movie Viewing Orders
Feature #11: Generate Movie Viewing Orders
Implementing the "Generate Movie Viewing Orders" feature for our "Netflix" project.
We'll cover the following...
Description
We want to offer marathons for our viewers. Each marathon will have a fixed set of movies catering to a specific taste. For a given marathon, different viewing orders of the movies will yield different user satisfaction results. We want to experiment (A/B testing) with different viewing orders of the same marathon.
Your task is to generate all the possible permutations of movies in a given marathon.
Let’s look at an example to better understand this:
Solution
To solve this problem, we will use the backtracking approach.
We will assume a backtrack
function that takes the index of the first movie to consider as an argument backtrack(first)
.
-
If the first movie to consider has index
n
, then that means that the current permutation is done. -
We will iterate over the marathon from index
first
to indexn - 1
. -
We will place the
i
th movie first in the permutation, that is,moviesList[first], moviesList[i] = moviesList[i], moviesList[first]
. -
We will proceed to create all the permutations that start from the
i
th movie:backtrack(first + 1)
. -
Now we will backtrack, that is,
moviesList[first], moviesList[i] = moviesList[i], moviesList[first]
back.
Let’s look at some illustrations to better understand this:
Note: We are using numbers to represent movies in the following illustration.
Let’s look at the code for this solution:
void backTrack(int first, int size, std::vector<std::string>& moviesList, std::vector<std::vector<std::string>>& output) {// If all strings of given array `moviesList` are used and// and Backtracking is performed push_back the permutations to output array.if (first == size) {std::vector<std::string> temp(moviesList.begin(), moviesList.end());output.push_back(temp);}// Perform Backtracking for the size of a given array.for (int i = first; i < size; i++) {// Swap: In the current permutation place i-th integer first.auto temp = moviesList[first];moviesList[first] = moviesList[i];moviesList[i] = temp;// Complete permutations using the next integers.backTrack(first + 1, size, moviesList, output);// Swap and Backtracktemp = moviesList[first];moviesList[first] = moviesList[i];moviesList[i] = temp;}}std::vector<std::vector<std::string>> generatePermutations(std::vector<std::string>& movies) {std::vector<std::vector<std::string>> output;int size = movies.size();// convert movies into list since the output is a list of listsstd::vector<std::string> moviesList;for (auto movie : movies)moviesList.push_back(movie);backTrack(0, size, moviesList, output);return output;}int main() {// Driver code// Example #1std::vector<std::string> input = {"Frozen","Dune","Coco"};auto output = generatePermutations(input);std::cout << "Output 1: " << toString(output) << std::endl;// Example #2std::vector<std::string> input2 = {"Frozen","Dune","Coco","Melificient"};output = generatePermutations(input2);std::cout << "Output 2: " << toString(output) << std::endl;// Example #3std::vector<std::string> input3 = {"Dune","Coco"};output = generatePermutations(input3);std::cout << "Output 3: " << toString(output) << std::endl;return 0;}