Home/

...

/

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 scala.collection.mutable._
object Solution {
  def swap(first:Int, i:Int, moviesList:ArrayBuffer[String]):Unit={
    var temp = moviesList(first)
    var temp2 = moviesList(i)
    moviesList.update(i, temp)
    moviesList.update(first, temp2)
  }
  def backTrack(first: Int, size: Int, moviesList: ArrayBuffer[String], output: ArrayBuffer[ArrayBuffer[String]]): Unit = { // If all strings of given array `moviesList` are used and
    // and Backtracking is performed add the permutations to output array.
    if (first == size) {
      val temp = new ArrayBuffer[String] ++ moviesList
      output.addOne(temp)
    }
    // Perform Backtracking for the size of a given array.
    for (i <- first until size) { // Swap: In the current permutation place i-th integer first.
      swap(first, i, moviesList)
      // Complete permutations using the next integers.
      backTrack(first + 1, size, moviesList, output)
      // Swap and Backtrack
      swap(first, i, moviesList)
    }
  }
  def generatePermutations(movies: Array[String]): ArrayBuffer[ArrayBuffer[String]] = {
    val output = new ArrayBuffer[ArrayBuffer[String]]
    val size = movies.length
    // convert movies into list since the output is a list of lists
    val moviesList = new ArrayBuffer[String]
    for (movie <- movies) {
      moviesList.addOne(movie)
    }
    backTrack(0, size, moviesList, output)
    output
  }
  def printArrayBuffer(list:ArrayBuffer[ArrayBuffer[String]]):Unit={
    print("[")
    for(l <- list){
      print("[" + l.mkString(", ") + "]")
    }
    println("]")
  }
  def main(args: Array[String]): Unit = {
    // Example #1
    val input = Array("Frozen", "Dune", "Coco")
    var output = generatePermutations(input)
    println("Output 1: ")
    printArrayBuffer(output)
    // Example #2
    val input2 = Array("Frozen", "Dune", "Coco", "Melificient")
    output = generatePermutations(input2)
    println("Output 2: ")
    printArrayBuffer(output)
    // Example #3
    val input3 = Array("Dune", "Coco")
    output = generatePermutations(input3)
    println("Output 3: ")
    printArrayBuffer(output)
  }
}
Permutations

Complexity measures

Time complexity
...