101 Logo
onenoughtone

Code Implementation

Shift Scheduler Implementation

Below is the implementation of the shift scheduler:

solution.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
// Recursive Backtracking Approach
function generatePermutations(baristas) {
  const result = [];
  backtrack(baristas, [], result);
  return result;
}
 
function backtrack(available, current, result) {
  // Base case: all baristas have been used
  if (available.length === 0) {
    result.push([...current]);
    return;
  }
 
  // Try each available barista in the current position
  for (let i = 0; i < available.length; i++) {
    // Choose the barista
    const barista = available[i];
    available.splice(i, 1);
    current.push(barista);
 
    // Recursively generate permutations for the remaining baristas
    backtrack(available, current, result);
 
    // Backtrack: undo the choice
    current.pop();
    available.splice(i, 0, barista);
  }
}
 
// Heap's Algorithm
function generatePermutationsHeap(baristas) {
  const result = [];
  heapPermute([...baristas], baristas.length, result);
  return result;
}
 
function heapPermute(baristas, size, result) {
  // Base case: size is 1, add the current permutation to the result
  if (size === 1) {
    result.push([...baristas]);
    return;
  }
 
  for (let i = 0; i < size; i++) {
    // Recursively generate permutations with size-1
    heapPermute(baristas, size - 1, result);
 
    // If size is odd, swap first and last element
    if (size % 2 === 1) {
      [baristas[0], baristas[size - 1]] = [baristas[size - 1], baristas[0]];
    }
    // If size is even, swap i-th and last element
    else {
      [baristas[i], baristas[size - 1]] = [baristas[size - 1], baristas[i]];
    }
  }
}
 
// Test cases
const baristas1 = ['Ana', 'Bob', 'Carlos'];
console.log("Baristas:", baristas1);
 
console.log("\nPermutations (Backtracking):");
const permutations1 = generatePermutations([...baristas1]);
permutations1.forEach(perm => console.log(perm.join(', ')));
 
console.log("\nPermutations (Heap's Algorithm):");
const permutations2 = generatePermutationsHeap([...baristas1]);
permutations2.forEach(perm => console.log(perm.join(', ')));
 
const baristas2 = ['Dana', 'Eli'];
console.log("\nBaristas:", baristas2);
 
console.log("\nPermutations (Backtracking):");
const permutations3 = generatePermutations([...baristas2]);
permutations3.forEach(perm => console.log(perm.join(', ')));
 
console.log("\nPermutations (Heap's Algorithm):");
const permutations4 = generatePermutationsHeap([...baristas2]);
permutations4.forEach(perm => console.log(perm.join(', ')));

Step-by-Step Explanation

Let's break down the implementation:

  1. Understand the Problem: We need to generate all possible arrangements (permutations) of a given set of barista names.
  2. Identify the Recursive Structure: Recognize that this is a classic Ordering Pattern problem where we recursively place each available barista in the current position and then find all permutations of the remaining baristas.
  3. Define the Base Case: The base case is when all baristas have been used (the available list is empty), at which point we add the current permutation to the result.
  4. Implement the Recursive Solution: Write a function that handles the base case and recursively explores all possible arrangements, using backtracking to undo choices and try different options.
  5. Consider Alternative Approaches: Implement Heap's Algorithm, which is more efficient in practice because it minimizes the number of swaps needed to generate all permutations.
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone