...

/

Feature #11: Generate Movie Viewing Orders

Feature #11: Generate Movie Viewing Orders

Implementing the "Generate Movie Viewing Orders" feature for our "Netflix" project.

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 index n - 1.

  • We will place the ith movie first in the permutation, that is, Movies[First], Movies[i] = Movies[i], Movies[First].

  • We will proceed to create all the permutations that start from the ith movie: Backtrack(First + 1).

  • Now we will backtrack, that is, Movies[First], Movies[i] = Movies[i], Movies[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:

import Swift
func GeneratePermutations(Movies: [String]) -> [[String]] {
var movies: [String] = Movies
let Size: Int = movies.count
var Output: [[String]] = []
func Backtrack(First: Int){
/* If all integers of given array `Movies` are used and
and Backtracking is performed add the permutations to Output array. */
if First == Size {
Output.append(movies)
}
var i: Int = First
/* Perform Backtracking for the Size of a given array. */
while i < Size {
/* Swap: In the current permutaion place i-th integer first. */
var temp = movies[First]
movies[First] = movies[i]
movies[i] = temp
/* Complete permuations using the next integers. */
Backtrack(First: First + 1)
/* Swap and Backtrack */
temp = movies[First]
movies[First] = movies[i]
movies[i] = temp
i += 1
}
}
Backtrack(First: 0)
return Output
}
// Example #1
var Input: [String] = ["Frozen","Dune","Coco"]
var Output: [[String]] = GeneratePermutations(Movies: Input)
print("Output 1:", terminator: "")
print(Output)
// Example #2
Input = ["Frozen","Dune","Coco","Melificient"]
Output = GeneratePermutations(Movies: Input)
print("Output 2:", terminator: "")
print(Output)
// Example #3
Input = ["Dune","Coco"]
Output = GeneratePermutations(Movies: Input)
print("Output 3:", terminator: "")
print(Output)
Generate movie viewing orders

Complexity measures

Time complexity
...