Relay Practice Lineups

EasybacktrackingAlso known as Permutations

A swim coach has a freestyle relay team. Each swimmer swims exactly one leg, one after another, and the coach suspects the order matters: a fast starter, a steady middle, a strong finisher. So over the season the team will time every possible order once.

The coach needs the complete list of lineups to pin on the board, with no lineup missing and none listed twice.

Your task

Write allLineups(swimmers). swimmers is a list of different names. Return every possible lineup: a list that contains each swimmer exactly once, in the order they swim.

The lineups can be returned in any order, but the order of names inside a lineup is the swim order, so it matters. An empty team has exactly one lineup, the empty one: return [[]].

allLineups(swimmers: string[]) → string[][] Any order of the returned list is accepted.

Examples

Example 1

Input

swimmers = ["Ana", "Ben", "Cy"]

Output

[["Ana", "Ben", "Cy"], ["Ana", "Cy", "Ben"], ["Ben", "Ana", "Cy"], ["Ben", "Cy", "Ana"], ["Cy", "Ana", "Ben"], ["Cy", "Ben", "Ana"]]

Why

3 choices for the first leg, then 2 for the second, then the last swimmer is fixed: 3 × 2 × 1 = 6 lineups. Ana-Ben-Cy and Ben-Ana-Cy are different lineups, because the first leg is swum by someone else.

Example 2

Input

swimmers = ["Mo"]

Output

[["Mo"]]

Why

One swimmer, one lineup.

Constraints

0 ≤ swimmers.length ≤ 6
All names are different, non-empty strings.
Lineups may be returned in any order.

Start with brute force

Generate every sequence of n names where each leg may be anyone, including repeats, and keep only the ones without a repeated name. That is nⁿ sequences to make the n! valid ones: 46,656 for 6 swimmers to find 720 lineups, and 10 billion for 10 swimmers to find 3.6 million.

The waste comes from noticing a repeat only at the end. If Ana is already in the lineup, every sequence that picks Ana again is dead from that moment, so do not build it at all.

Hints

0 of 4 shown

Hint 1
With Ana, Ben and Cy: how many choices are there for the first leg? Once Ana takes the first leg, how many are left for the second?
Hint 2
Build a lineup one leg at a time. For the next leg you may pick anyone who is not already in the lineup. That gives 3 × 2 × 1 lineups, and the choices form a tree: 3 branches, then 2 under each, then 1.
Hint 3
Write a recursive helper fill(). If the current lineup has every swimmer, record it. Otherwise try each swimmer who is still free for the next leg, and for each one fill the remaining legs.
Hint 4
Keep a boolean list used next to the shared current list. For each free swimmer: mark used, push, recurse, pop, unmark. Recording must store a copy of current.

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

A lineup is a sequence of choices: who swims leg 1, then who swims leg 2 from those left, and so on. Recursion makes one choice per call, and the used list stops anyone from being picked twice on the same path.

Trace ["Ana", "Ben", "Cy"]:

Leg 1 = Ana. Free: Ben, Cy. Leg 2 = Ben, leg 3 = Cy. Record Ana-Ben-Cy.
Undo Cy and Ben. Leg 2 = Cy, leg 3 = Ben. Record Ana-Cy-Ben.
Undo back to leg 1. Ana is free again. Leg 1 = Ben, then Ana-Cy and Cy-Ana give Ben-Ana-Cy and Ben-Cy-Ana.
Leg 1 = Cy gives Cy-Ana-Ben and Cy-Ben-Ana.

Six lineups, no repeats, and no dead sequence was ever built. Forgetting used[i] = false after the recursive call is the classic bug: every swimmer stays marked after the first lineup, so no other lineup can ever be completed and you get just one.

Reference solution

function allLineups(swimmers) {
  const lineups = [];
  const current = [];                          // the lineup so far
  const used = new Array(swimmers.length).fill(false);
  function fill() {
    if (current.length === swimmers.length) {
      lineups.push([...current]);              // copy the finished lineup
      return;
    }
    for (let i = 0; i < swimmers.length; i++) {
      if (used[i]) continue;
      used[i] = true;
      current.push(swimmers[i]);               // choose the next leg
      fill();                                  // fill the remaining legs
      current.pop();                           // undo the choice
      used[i] = false;
    }
  }
  fill();
  return lineups;
}

def all_lineups(swimmers):
    lineups = []
    current = []                     # the lineup so far, leg by leg
    used = [False] * len(swimmers)   # used[i]: swimmer i already swims
 
    def fill():
        if len(current) == len(swimmers):
            lineups.append(current[:])  # copy the finished lineup
            return
        for i, name in enumerate(swimmers):
            if used[i]:
                continue
            used[i] = True
            current.append(name)        # choose who swims the next leg
            fill()                      # fill the remaining legs
            current.pop()               # undo the choice
            used[i] = False
 
    fill()
    return lineups

TimeO(n · n!)There are n! lineups, and each takes up to n work to build and copy.

SpaceO(n)The recursion depth, current and used are all size n, not counting the output.

Learn the idea: Backtracking Recursion

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code