...

/

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:

package main
import (
"fmt"
)
func GeneratePermutations(Movies []string) [][]string {
Size := len(Movies)
var Backtrack func(int)
var Output [][]string
Backtrack = func(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 {
temp := make([]string,len(Movies[:]))
copy(temp,Movies[:])
Output = append(Output, temp)
}
/* Perform Backtracking for the Size of a given array. */
for i := First; i < Size; i++{
/* Swap: In the current permutaion place i-th integer first. */
Movies[First], Movies[i] = Movies[i], Movies[First]
/* Complete permuations using the next integers. */
Backtrack(First+1)
/* Swap and Backtrack */
Movies[First], Movies[i] = Movies[i], Movies[First]
}
}
Backtrack(0)
return Output
}
func main() {
// Example #1
Input := []string{"Frozen","Dune","Coco"}
Output := GeneratePermutations(Input)
fmt.Println("Output 1:",Output)
// Example #2
Input = []string{"Frozen","Dune","Coco","Melificient"}
Output = GeneratePermutations(Input)
fmt.Println("Output 2:",Output)
// Example #3
Input = []string{"Dune","Coco"}
Output = GeneratePermutations(Input)
fmt.Println("Output 3:",Output)
}
Generate movie viewing orders

Complexity measures

Time complexity
...