Search⌘ K
AI Features
Home
Courses
Decode the Coding Interview in Ruby: Real-World Examples

Feature #11: Generate Movie Viewing Orders

Explore how to generate every possible order of movies in a marathon using backtracking. This lesson helps you understand permutation generation and its application for experimenting with different viewing sequences to enhance user satisfaction in real-world projects.

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 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:

Ruby
def generate_permutations(movies)
    
    size = movies.length
    $output=Array.new
    def backtrack(first, movies, size)
        # If all integers of given array `Movies` are used and 
        # and Backtracking is performed add the permutations to Output array. 
        if first == size 
            temp = Array.new(movies.length)
            temp= movies[0...movies.length]
            $output.push(temp)
        end
        # Perform Backtracking for the Size of a given array. 
        for i in (first...size)
            # 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, movies, size)
            # Swap and Backtrack 
            movies[first], movies[i] = movies[i], movies[first]
        end
    end
    backtrack(0, movies, size)
    return $output
end
# Example #1
input = ["Frozen","Dune","Coco"]
output = generate_permutations(input)
print("Output 1: [")
print(output)
puts()
#  Example #2
input = ["Frozen","Dune","Coco","Melificient"]
output = generate_permutations(input)
print("Output 2: [")
print(output)
puts()
# // Example #3
# Input = new string[2]{"Dune","Coco"};
input = ["Dune","Coco"]
output = generate_permutations(input)
print("Output 3: [")
print(output)
puts()

Complexity measures

Time complexity
...