2024-03-06

OBP:

Calculating the number of solutions in the full neighborhood of the scheduling problem.

The size of the full solution space is:

\[\dbinom{N+T-1}{N} = \frac{(N+T-1)!}{N!*(T-1)!}\]

import math
def full_nh(N, T):
  result = math.factorial(N + T - 1) / (math.factorial(N) * math.factorial(T - 1))
  return int(result)

def generate_words(N, T, current='', results=None):
    if results is None:
        results = []

    # Base case: if the length of the current string is equal to the total length required
    if len(current) == N + T - 1:
        results.append(current)
        return results

    # If adding a point does not exceed the total points limit, add a point and recurse
    if current.count('.') < N:
        generate_words(N, T, current + '.', results)

    # If adding a stick does not exceed the total sticks limit (T-1), add a stick and recurse
    # Also ensure that we don't start with a stick or place multiple sticks consecutively
    if current.count('|') < T - 1 and len(current) >= 0:
        generate_words(N, T, current + '|', results)

    return results, full_nh(N, T)

# Example usage:
N = 6
T = 3
words = generate_words(N, T)
for word in words[0]:
    print(word)
print(words[1])

......||
.....|.|
.....||.
....|..|
....|.|.
....||..
...|...|
...|..|.
...|.|..
...||...
..|....|
..|...|.
..|..|..
..|.|...
..||....
.|.....|
.|....|.
.|...|..
.|..|...
.|.|....
.||.....
|......|
|.....|.
|....|..
|...|...
|..|....
|.|.....
||......
28

What happens when N and T double?

N = [5, 10, 20, 40]
T = [2, 4, 8, 16]
s = []

for i in range(len(N)):
    n, t= [N[i], T[i]]
    s.append(full_nh(n, t))
    if i == 0: print(f'size = {s[i]} , with N={n} and T={t}')
    else: print(f'size = {s[i]} (factor = {int(s[i] / s[i - 1])}, with N={n} and T={t}')

size = 6 , with N=5 and T=2
size = 286 (factor = 47, with N=10 and T=4
size = 888030 (factor = 3105, with N=20 and T=8
size = 11899700525790 (factor = 13400110, with N=40 and T=16

How does time complexity scales scale when N+T grows?

Starting with \(\dbinom{N+T-1}{N}\) and ignoring constants we have:

\[\dbinom{N+T}{N} = \frac{(N+T)!}{N!T!} = \frac{1}{T!} \frac{(N+T)!}{N!} = \] \[=\frac{1}{T!}((N+T)(N+T-1) .... (N+1)) = \frac{1}{T!}(N+T)^T(1(1-\frac{1}{N+T})(1-\frac{2}{N+T}) .... (1-\frac{T}{N+T}))\]

(Clement 2015)

As \(N + T\) increases the fractions with \(N + T\) in the denominator will tend to zero. The products \(T!\) and \((N+T)^T\) have the same number of terms. However as \(N+T >> T\), the size of the problem will grow with \(\mathcal{O}((N+T)^T)\)

Next calculate complexity reduction from local search algorithm.

References

Clement, C. 2015. “Answer to "Approximation of Combination $ {n \Choose k} = \Theta \Left( n^k \Right) $?".” Mathematics Stack Exchange. https://math.stackexchange.com/a/1265529.