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_list[first], movies_list[i] = movies_list[i], movies_list[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_list[first], movies_list[i] = movies_list[i], movies_list[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:

Rust 1.57.0
fn backtrack( n: i32,  mut movies_list: &mut Vec<String>, mut output:&mut Vec<Vec<String>>, first: i32) {
    
    // If all integers of given array `Movies` are used and 
    // and Backtracking is performed add the permutations to Output array.
    if first == n
      {output.push(movies_list.to_vec());}
    
    // Perform Backtracking for the Size of a given array.
    for i  in first as usize..n as usize {
      
      // Swap: In the current permutaion place i-th integer first.
      let temp = movies_list[first as usize].to_string();
      movies_list[first as usize] = movies_list[i].to_string();
      movies_list[i] = temp.to_string();
      
      // Complete permuations using the next integers.
      backtrack(n,&mut movies_list,&mut output, first + 1);
      
      // Swap and Backtrack
      let temp2 = movies_list[first as usize].to_string();
      movies_list[first as usize] = movies_list[i].to_string();
      movies_list[i] = temp2.to_string();
    }
  }
fn generate_permutations(movies: Vec<String>)-> Vec<Vec<String>> {
    // init output list
    let mut output: Vec<Vec<String>> = Vec::new();
    // convert movies into list since the output is a list of lists
    let mut movies_list: Vec<String> = Vec::new();
    for num in movies.clone().into_iter(){
      movies_list.push(num);
    }
    let n = movies.len() as i32;
    backtrack(n,&mut movies_list,&mut output, 0);
    return output;
  }
fn main(){
    // Example #1
    let mut input: Vec<String> = vec!["Frozen","Dune","Coco"].into_iter().map(String::from).collect();
    let mut output = generate_permutations(input);
    println!("Output 1: ");
    println!("{:?}",output);
    // Example #2
    input = vec!["Frozen","Dune","Coco","Melificient"].into_iter().map(String::from).collect();
    output = generate_permutations(input);
    println!("Output 2: ");
    println!("{:?}",output);
  //   // Example #3
    input = vec!["Dune","Coco"].into_iter().map(String::from).collect();
    output = generate_permutations(input);
    println!("Output 3: ");
    println!("{:?}",output);
}

Complexity measures

...