Feature #11: Generate Movie Viewing Orders

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 add the moveList to the output

• We will iterate over the marathon from index first to index n - 1.

• We will place the ith movie first in the permutation, using function Collections.swap(moviesList, first, i).

• We will proceed to create all the permutations that start from the ith movie: backTrack(first + 1, size, moviesList, output).

• Now we will swap again, that is, Collections.swap(moviesList, first, i) back. ...