Count ways to traverse all N cities when each city is traversed K times

0 0 25 minutes read

For N given cities, find how many ways a driver can traverse through them so that each town is visited exactly K times. From each city he can go to every other city (except the city which is already in it).

Example:

Input: N = 3, K = 1
Output: 6
Explanation: The possible paths are
1 -> 2 -> 3
1 -> 3 -> 2
2 -> 1 -> 3
2 -> 3 -> 1
3 -> 1 -> 2
3 -> 2 -> 1

Input: N = 3, K = 2
Output: 30
Explanation: The possible paths are
1 -> 2 -> 1 -> 3 -> 2 -> 3, 1 -> 2 -> 3 -> 1 -> 2 -> 3
1 -> 2 -> 3 -> 1 -> 3 -> 2, 1 -> 2 -> 3 -> 2 -> 1 -> 3
1 -> 2 -> 3 -> 2 -> 3 -> 1, 1 -> 3 -> 1 -> 2 -> 3 -> 2
1 -> 3 -> 2 -> 1 -> 2 -> 3, 1 -> 3 -> 2 -> 1 -> 3 -> 2
1 -> 3 -> 2 -> 3 -> 1 -> 2, 1 -> 3 -> 2 -> 3 -> 2 -> 1
2 -> 1 -> 2 -> 3 -> 1 -> 3, 2 -> 1 -> 3 -> 1 -> 2 -> 3
2 -> 1 -> 3 -> 1 -> 3 -> 2, 2 -> 1 -> 3 -> 2 -> 1 -> 3
2 -> 1 -> 3 -> 2 -> 3 -> 1, 2 -> 3 -> 1 -> 2 -> 1 -> 3
2 -> 3 -> 1 -> 2 -> 3 -> 1, 2 -> 3 -> 1 -> 3 -> 1 -> 2
2 -> 3 -> 1 -> 3 -> 2 -> 1, 2 -> 3 -> 2 -> 1 -> 3 -> 1
3 -> 1 -> 2 -> 1 -> 2 -> 3, 3 -> 1 -> 2 -> 1 -> 3 -> 2
3 -> 1 -> 2 -> 3 -> 1 -> 2, 3 -> 1 -> 2 -> 3 -> 2 -> 1
3 -> 1 -> 3 -> 2 -> 1 -> 2, 3 -> 2 -> 1 -> 2 -> 1 -> 3
3 -> 2 -> 1 -> 2 -> 3 -> 1, 3 -> 2 -> 1 -> 3 -> 1 -> 2
3 -> 2 -> 1 -> 3 -> 2 -> 1, 3 -> 2 -> 3 -> 1 -> 2 -> 1

Naive solution

The naive approach is to generate all the combinations and increment a counter for every possible arrangement that doesn’t have two same adjacent elements.

Below is the implementation of the above approach:

C++

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the number of possible paths
ulong driversProblem(int n, int k)
{
    ulong num_of_paths = 0;
    vector<int> path;
 
    // Filling the vector with the first path
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < k; j++) {
            path.push_back(i);
        }
    }
    bool valid_path;
    while (next_permutation(path.begin(), path.end())) {
        valid_path = true;
 
        // Checking if there is 2 adjacent cities
        // in the path
        for (int i = 0; i < n * k - 1; i++) {
            if (path[i] == path[i + 1]) {
                valid_path = false;
            }
        }
 
        // Incrementing the counter if
        // the path generated is valid
        if (valid_path == true) {
            num_of_paths++;
        }
    }
    return num_of_paths;
}
 
// Driver code
int main()
{
    int N = 3, K = 2;
 
    // Function call
    cout << driversProblem(N, K) << endl;
    return 0;
}

Java

/*package whatever //do not write package name here */
 
import java.io.*;
 
class GFG {
 
    // Function to find the number of possible paths
    static long driversProblem(int n, int k)
    {
        long num_of_paths = 0;
        int path[] = new int[n * k];
        int x = 0;
        // Filling the vector with the first path
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < k; j++) {
                path[x++] = i;
            }
        }
        boolean valid_path;
        while (next_permutation(path)) {
            valid_path = true;
 
            // Checking if there is 2 adjacent cities
            // in the path
            for (int i = 0; i < n * k - 1; i++) {
                if (path[i] == path[i + 1]) {
                    valid_path = false;
                }
            }
 
            // Incrementing the counter if
            // the path generated is valid
            if (valid_path == true) {
                num_of_paths++;
            }
        }
        return num_of_paths;
    }
    public static int[] swap(int data[], int left,
                             int right)
    {
 
        // Swap the data
        int temp = data[left];
        data[left] = data[right];
        data[right] = temp;
 
        // Return the updated array
        return data;
    }
 
    // Function to reverse the sub-array
    // starting from left to the right
    // both inclusive
    public static int[] reverse(int data[], int left,
                                int right)
    {
 
        // Reverse the sub-array
        while (left < right) {
            int temp = data[left];
            data[left++] = data[right];
            data[right--] = temp;
        }
 
        // Return the updated array
        return data;
    }
 
    // Function to find the next permutation
    // of the given integer array
    public static boolean next_permutation(int data[])
    {
 
        // If the given dataset is empty
        // or contains only one element
        // next_permutation is not possible
        if (data.length <= 1)
            return false;
 
        int last = data.length - 2;
 
        // find the longest non-increasing suffix
        // and find the pivot
        while (last >= 0) {
            if (data[last] < data[last + 1]) {
                break;
            }
            last--;
        }
 
        // If there is no increasing pair
        // there is no higher order permutation
        if (last < 0)
            return false;
 
        int nextGreater = data.length - 1;
 
        // Find the rightmost successor to the pivot
        for (int i = data.length - 1; i > last; i--) {
            if (data[i] > data[last]) {
                nextGreater = i;
                break;
            }
        }
 
        // Swap the successor and the pivot
        data = swap(data, nextGreater, last);
 
        // Reverse the suffix
        data = reverse(data, last + 1, data.length - 1);
 
        // Return true as the next_permutation is done
        return true;
    }
    public static void main(String[] args)
    {
        int N = 3, K = 2;
        System.out.println(driversProblem(N, K));
    }
}

Python3

# Python implementation for the above approach
 
# Function to find the number of possible paths
def driversProblem(n, k):
    num_of_paths = 0
    path = [0]*(n*k)
    x = 0
 
    # Filling the vector with the first path
    for i in range(1, n+1):
        for j in range(k):
            path[x] = i
            x += 1
 
    while(next_permutation(path)):
        valid_path = True
 
        # Checking if there is 2 adjacent cities in the path
        for i in range(n*k-1):
            if(path[i] == path[i+1]):
                valid_path = False
 
        # Incrementing the counted if the path generated is valid
        if(valid_path):
            num_of_paths += 1
 
    return num_of_paths
 
# Function to reverse the sub-array starting 
# from left to the right both inclusive
def reverse(data, left, right):
    # Reverse the sub-array
    while(left < right):
        temp = data[left]
        data[left] = data[right]
        data[right] = temp
        left += 1
        right -= 1
 
    # Return the updated array
    return data
 
# Function to find the next permutation of the given integer array
def next_permutation(data):
    # If the given dataset is empty or contains only 
    # one element next_permutation is not possible
    if(len(data) <= 1):
        return False
 
    last = len(data) - 2
 
    # Find the longest non-increasing 
    # suffix and find the pivot
    while(last >= 0):
        if(data[last] < data[last+1]):
            break
        last -= 1
 
    # If there is not increasing pair 
    # there is no higher order permutation
    if(last < 0):
        return False
 
    nextGreater = len(data) - 1
 
    # Find the rightmost successor to the pivot
    for i in range(len(data)-1, last, -1):
        if(data[i] > data[last]):
            nextGreater = i
            break
 
    # Swap the successor and the pivot
    data[nextGreater], data[last] = data[last], data[nextGreater]
 
    # Reverse the suffix
    data = reverse(data, last+1, len(data)-1)
 
    # Return true as the next_permutation is done
    return True
 
 
N, K = 3, 2
print(driversProblem(N, K))
 
# This code is contributed by lokeshmvs21.

C#

/*package whatever //do not write package name here */
 
using System;
 
class GFG {
 
    // Function to find the number of possible paths
    static long driversProblem(int n, int k)
    {
        long num_of_paths = 0;
        int[] path = new int[n * k];
        int x = 0;
        // Filling the vector with the first path
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < k; j++) {
                path[x++] = i;
            }
        }
        Boolean valid_path;
        while (next_permutation(path)) {
            valid_path = true;
 
            // Checking if there is 2 adjacent cities
            // in the path
            for (int i = 0; i < n * k - 1; i++) {
                if (path[i] == path[i + 1]) {
                    valid_path = false;
                }
            }
 
            // Incrementing the counter if
            // the path generated is valid
            if (valid_path == true) {
                num_of_paths++;
            }
        }
        return num_of_paths;
    }
    public static int[] swap(int[] data, int left,
                             int right)
    {
 
        // Swap the data
        int temp = data[left];
        data[left] = data[right];
        data[right] = temp;
 
        // Return the updated array
        return data;
    }
 
    // Function to reverse the sub-array
    // starting from left to the right
    // both inclusive
    public static int[] reverse(int[] data, int left,
                                int right)
    {
 
        // Reverse the sub-array
        while (left < right) {
            int temp = data[left];
            data[left++] = data[right];
            data[right--] = temp;
        }
 
        // Return the updated array
        return data;
    }
 
    // Function to find the next permutation
    // of the given integer array
    public static Boolean next_permutation(int[] data)
    {
 
        // If the given dataset is empty
        // or contains only one element
        // next_permutation is not possible
        if (data.Length <= 1)
            return false;
 
        int last = data.Length - 2;
 
        // find the longest non-increasing suffix
        // and find the pivot
        while (last >= 0) {
            if (data[last] < data[last + 1]) {
                break;
            }
            last--;
        }
 
        // If there is no increasing pair
        // there is no higher order permutation
        if (last < 0)
            return false;
 
        int nextGreater = data.Length - 1;
 
        // Find the rightmost successor to the pivot
        for (int i = data.Length - 1; i > last; i--) {
            if (data[i] > data[last]) {
                nextGreater = i;
                break;
            }
        }
 
        // Swap the successor and the pivot
        data = swap(data, nextGreater, last);
 
        // Reverse the suffix
        data = reverse(data, last + 1, data.Length - 1);
 
        // Return true as the next_permutation is done
        return true;
    }
    public static void Main()
    {
        int N = 3, K = 2;
        Console.Write(driversProblem(N, K));
    }
}
 
// This code is contributed by Saurabh Jaiswal

Javascript

// Javascript code to implement the approach
 
    function reverse(nums, start)
{
    let i = start, j = nums.length - 1;
    while (i < j) {
        swap(nums, i, j);
        i++;
        j--;
    }
}
function swap(nums, i, j)
{
    let temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}
// function to find next greater permutation
function next_permutation(nums)
{
    let i = nums.length - 2;
    while (i >= 0 && nums[i + 1] <= nums[i]) {
        i--;
    }
    if (i >= 0) {
        let j = nums.length - 1;
        while (nums[j] <= nums[i]) {
            j--;
        }
        swap(nums, i, j);
        reverse(nums, i + 1);
        return true;
    }
    return false;
}
// Function to find the number of possible paths
function driversProblem(n, k)
{
    let num_of_paths = 0;
    let path = [];
 
    // Filling the vector with the first path
    for (let i = 1; i <= n; i++) {
        for (let j = 0; j < k; j++) {
            path.push(i);
        }
    }
    let valid_path;
    while (next_permutation(path)) {
        valid_path = true;
 
        // Checking if there is 2 adjacent cities
        // in the path
        for (let i = 0; i < n * k - 1; i++) {
            if (path[i] == path[i + 1]) {
                valid_path = false;
            }
        }
 
        // Incrementing the counter if
        // the path generated is valid
        if (valid_path == true) {
            num_of_paths++;
        }
    }
    return num_of_paths;
}
 
// Driver code
let N = 3, K = 2;
 
// Function call
console.log(driversProblem(N, K));
 
// This code is contributed by garg28harsh.

Output

Time Complexity: (N*K)! / (K!)^N
Auxiliary Space: O(N*K)

Count possible ways to travel all cities using Recursion:

In the recursive approach, we create an array of size N to represent each city and fill it up with the number K to later keep on track of number of times each city is visited.

Follow the below steps to implement the idea:

Build a recursion function as mentioned above.
If every city has a count of 0, return 1. If any city has a count less than 0, return 0.
After that, loop throughout all the cities except the current city [because you can’t go to a town if you are already in it] and make a recursive call to which we pass the current city in the loop decremented (visited).
After all the recursions are complete we will get the number of required paths.

Below is the implementation of the approach.

C++

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the number of paths
ulong numberOfPaths(int current_city, int n,
                    vector<int> visited)
{
    bool all_zero = true;
    for (int i = 1; i <= n; i++) {
        if (visited[i] < 0)
            return 0;
        if (visited[i] != 0)
            all_zero = false;
    }
    if (all_zero == true)
        return 1;
    ulong num_of_paths = 0;
    for (int i = 1; i <= n; i++) {
        if (current_city == i) {
            continue;
        }
        visited[i]--;
        num_of_paths += numberOfPaths(i, n, visited);
        visited[i]++;
    }
    return num_of_paths;
}
 
ulong driversProblem(int n, int k)
{
    vector<int> visited;
    for (int i = 0; i <= n; i++) {
        visited.push_back(k);
    }
    return numberOfPaths(0, n, visited);
}
 
// Driver code
int main()
{
    int N = 3, K = 2;
 
    // Function call
    cout << driversProblem(N, K) << endl;
    return 0;
}

Java

// java implementation
import java.io.*;
 
class GFG {
    public static long numberOfPaths(int current_city,
                                     int n, int visited[])
    {
        boolean all_zero = true;
        for (int i = 1; i <= n; i++) {
            if (visited[i] < 0)
                return 0;
            if (visited[i] != 0)
                all_zero = false;
        }
        if (all_zero == true)
            return 1;
        long num_of_paths = 0;
        for (int i = 1; i <= n; i++) {
            if (current_city == i) {
                continue;
            }
            visited[i]--;
            num_of_paths += numberOfPaths(i, n, visited);
            visited[i]++;
        }
        return num_of_paths;
    }
 
    public static long driversProblem(int n, int k)
    {
        int visited[] = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            visited[i] = k;
        }
        return numberOfPaths(0, n, visited);
    }
 
    public static void main(String[] args)
    {
        int N = 3, K = 2;
 
        // Function call
        System.out.println(driversProblem(N, K));
    }
}
 
// This code is contributed by ksam24000

Python3

# Python code to implement the approach
 
# Function to find the number of paths
 
 
def numberOfPaths(current_city, n, visited):
 
    all_zero = True
    for i in range(1, n+1):
        if (visited[i] < 0):
            return 0
        if (visited[i] != 0):
            all_zero = False
 
    if (all_zero == True):
        return 1
    num_of_paths = 0
    for i in range(1, n+1):
        if (current_city == i):
            continue
 
        visited[i] -= 1
        num_of_paths += numberOfPaths(i, n, visited)
        visited[i] += 1
 
    return num_of_paths
 
 
def driversProblem(n, k):
 
    visited = []
    for i in range(n+1):
        visited.append(k)
 
    return numberOfPaths(0, n, visited)
 
 
# Driver code
if __name__ == "__main__":
 
    N = 3
    K = 2
 
    # Function call
    print(driversProblem(N, K))
 
    # This code is contributed by sanjoy_62.

C#

// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
 
class GFG {
    // Function to find the number of paths
    static int numberOfPaths(int current_city, int n,
                             List<int> visited)
    {
        bool all_zero = true;
        for (int i = 1; i <= n; i++) {
            if (visited[i] < 0)
                return 0;
            if (visited[i] != 0)
                all_zero = false;
        }
        if (all_zero == true)
            return 1;
        int num_of_paths = 0;
        for (int i = 1; i <= n; i++) {
            if (current_city == i) {
                continue;
            }
            visited[i]--;
            num_of_paths += numberOfPaths(i, n, visited);
            visited[i]++;
        }
        return num_of_paths;
    }
 
    static int driversProblem(int n, int k)
    {
        List<int> visited = new List<int>();
        for (int i = 0; i <= n; i++) {
            visited.Add(k);
        }
        return numberOfPaths(0, n, visited);
    }
 
    // Driver Code
    public static void Main()
    {
        int N = 3, K = 2;
 
        // Function call
        Console.Write(driversProblem(N, K));
    }
}
 
// This code is contributed by code_hunt.

Javascript

<script>
        // JavaScript code for the above approach
 
        // Function to find the number of paths
        function numberOfPaths(current_city, n,
            visited) {
            let all_zero = true;
            for (let i = 1; i <= n; i++) {
                if (visited[i] < 0)
                    return 0;
                if (visited[i] != 0)
                    all_zero = false;
            }
            if (all_zero == true)
                return 1;
            let num_of_paths = 0;
            for (let i = 1; i <= n; i++) {
                if (current_city == i) {
                    continue;
                }
                visited[i]--;
                num_of_paths += numberOfPaths(i, n, visited);
                visited[i]++;
            }
            return num_of_paths;
        }
 
        function driversProblem(n, k) {
            let visited = [];
            for (let i = 0; i <= n; i++) {
                visited.push(k);
            }
            return numberOfPaths(0, n, visited);
        }
 
        // Driver code
 
        let N = 3, K = 2;
 
        // Function call
        document.write(driversProblem(N, K));
 
 // This code is contributed by Potta Lokesh
 
    </script>

Output

Count possible ways to travel all cities using Memoization:

If noticed carefully, we can see that the current city and the state of the visited array can uniquely identify a state. We can use that to memoize and reuse the previously calculated value.

Below is the implementation of the above approach.

C++

// C++ recursive approach (with memoization)
// program for the drivers problem
 
#include <bits/stdc++.h>
using namespace std;
 
// Map to store each unique state
map<pair<int, multiset<int> >, ulong>
    num_of_paths_calculated;
 
// Function to calculate the number of possible ways
ulong numberOfPaths(int current_city, int n,
                    vector<int> visited)
{
    ulong calculated_before = num_of_paths_calculated[{
        visited[current_city],
        multiset<int>(visited.begin(), visited.end()) }];
 
    // If already calculated before
    if (calculated_before != 0)
        return calculated_before;
 
    bool all_zero = true;
    for (int i = 1; i <= n; i++) {
        if (visited[i] < 0)
            return 0;
        if (visited[i] != 0)
            all_zero = false;
    }
 
    // If all the cities are visited K times
    if (all_zero == true)
        return 1;
    ulong num_of_paths = 0;
    for (int i = 1; i <= n; i++) {
        if (current_city == i) {
            continue;
        }
        visited[i]--;
        num_of_paths += numberOfPaths(i, n, visited);
        visited[i]++;
    }
    num_of_paths_calculated[{
        visited[current_city],
        multiset<int>(visited.begin(), visited.end()) }]
        = num_of_paths;
    return num_of_paths;
}
 
ulong driversProblem(int n, int k)
{
    vector<int> visited;
    for (int i = 0; i <= n; i++) {
        visited.push_back(k);
    }
    return numberOfPaths(0, n, visited);
}
 
// Driver code
int main()
{
    int N = 3, K = 2;
 
    // Function call
    cout << driversProblem(N, K) << endl;
    return 0;
}

Java

import java.util.HashMap;
import java.util.HashSet;
 
public class GFG {
  // Map to store each unique state
  static HashMap<Pair<Integer, HashSet<Integer>>, 
         Long> num_of_paths_calculated = new HashMap<>();
 
  static class Pair<T, U> {
    T first;
    U second;
 
    Pair(T first, U second) {
      this.first = first;
      this.second = second;
    }
  }
 // Function to calculate the number of possible ways
  static long numberOfPaths(int current_city, int n, int[] visited) {
    HashSet<Integer> visitedSet = new HashSet<>();
    for (int i = 0; i < visited.length; i++) {
      visitedSet.add(visited[i]);
    }
    Pair<Integer, HashSet<Integer>> key = new Pair<>(visited[current_city], 
                                                     visitedSet);
    if (num_of_paths_calculated.containsKey(key)) {
      return num_of_paths_calculated.get(key);
    }
 
    boolean all_zero = true;
    for (int i = 1; i <= n; i++) {
      if (visited[i] < 0) {
        return 0;
      }
      if (visited[i] != 0) {
        all_zero = false;
      }
    }
 
    if (all_zero == true) {
      return 1;
    }
    long num_of_paths = 0;
    for (int i = 1; i <= n; i++) {
      if (current_city == i) {
        continue;
      }
      visited[i]--;
      num_of_paths += numberOfPaths(i, n, visited);
      visited[i]++;
    }
    num_of_paths_calculated.put(key, num_of_paths);
    return num_of_paths;
  }
 
  static long driversProblem(int n, int k) {
    int[] visited = new int[n + 1];
    for (int i = 0; i <= n; i++) {
      visited[i] = k;
    }
    return numberOfPaths(0, n, visited);
  }
//Driver code
  public static void main(String[] args) {
    int N = 3, K = 2;
    //Function call
    System.out.println(driversProblem(N, K));
  }
}

Python3

# Python3 recursive approach (with memoization)
# program for the drivers problem
 
# Map to store each unique state
num_of_paths_calculated = {}
 
# Function to calculate the number of possible ways
def numberOfPaths(current_city, n, visited):
    calculated_before = num_of_paths_calculated.get(str(visited[current_city]) + str(visited))
 
    # If already calculated before
    if calculated_before: return calculated_before
 
    all_zero = True
    for i in range(1, n + 1):
        if visited[i] < 0: return 0
        if visited[i] != 0: all_zero = False
 
    # If all the cities are visited K times
    if all_zero == True: return 1
    num_of_paths = 0
    for i in range(1, n + 1):
        if current_city == i:
            continue
        visited[i] -= 1
        num_of_paths += numberOfPaths(i, n, visited)
        visited[i] += 1
    num_of_paths_calculated[str(visited[current_city]) + str(visited)] = num_of_paths
    return num_of_paths
 
def driversProblem(n, k):
    visited = [k for i in range(n + 1)]
    return numberOfPaths(0, n, visited)
 
# Driver code
N = 3
K = 2
 
# Function call
print(driversProblem(N, K))
 
# This code is contributed by akashish__

C#

using System;
using System.Collections.Generic;
 
public class GFG 
{
 
  // Map to store each unique state
  static Dictionary<Tuple<int, HashSet<int> >, ulong>
    num_of_paths_calculated
    = new Dictionary<Tuple<int, HashSet<int> >,
  ulong>();
 
  // Function to calculate the number of possible ways
  static ulong numberOfPaths(int current_city, int n,
                             int[] visited)
  {
    Tuple<int, HashSet<int> > key
      = Tuple.Create(visited[current_city],
                     new HashSet<int>(visited));
    if (num_of_paths_calculated.ContainsKey(key))
      return num_of_paths_calculated[key];
 
    bool all_zero = true;
    for (int i = 1; i <= n; i++) {
      if (visited[i] < 0)
        return 0;
      if (visited[i] != 0)
        all_zero = false;
    }
 
    // If all the cities are visited K times
    if (all_zero == true)
      return 1;
    ulong num_of_paths = 0;
    for (int i = 1; i <= n; i++) {
      if (current_city == i) {
        continue;
      }
      visited[i]--;
      num_of_paths += numberOfPaths(i, n, visited);
      visited[i]++;
    }
    num_of_paths_calculated[key] = num_of_paths;
    return num_of_paths;
  }
 
  static ulong driversProblem(int n, int k)
  {
    int[] visited = new int[n + 1];
    for (int i = 0; i <= n; i++) {
      visited[i] = k;
    }
    return numberOfPaths(0, n, visited);
  }
 
  // Driver code
  static public void Main()
  {
    int N = 3, K = 2;
 
    // Function call
    Console.WriteLine(driversProblem(N, K));
  }
}
 
// This code is contributed by akashish__

Javascript

// Javascript recursive approach (with memoization)
// program for the drivers problem
 
// Map to store each unique state
const num_of_paths_calculated = new Map();
 
// Function to calculate the number of possible ways
function numberOfPaths(current_city, n, visited) {
  const calculated_before = num_of_paths_calculated.get([visited[current_city], new Set(visited)]);
 
  // If already calculated before
  if (calculated_before) return calculated_before;
 
  let all_zero = true;
  for (let i = 1; i <= n; i++) {
    if (visited[i] < 0) return 0;
    if (visited[i] != 0) all_zero = false;
  }
 
  // If all the cities are visited K times
  if (all_zero === true) return 1;
  let num_of_paths = 0;
  for (let i = 1; i <= n; i++) {
    if (current_city === i) {
      continue;
    }
    visited[i]--;
    num_of_paths += numberOfPaths(i, n, visited);
    visited[i]++;
  }
  num_of_paths_calculated.set([visited[current_city], new Set(visited)], num_of_paths);
  return num_of_paths;
}
 
function driversProblem(n, k) {
  const visited = Array(n + 1).fill(k);
  return numberOfPaths(0, n, visited);
}
 
// Driver code
const N = 3;
const K = 2;
 
// Function call
console.log(driversProblem(N, K));
 
// This code is contributed by akashish__

Output

Count possible ways to travel all cities using Dynamic Programming:

The problem can be solved based on the following idea:

In the iterative approach, we calculate the answer to our problem by finding the number of Hamiltonian Paths in a Complete n-Partite Graphs, and then since there are more Hamiltonian Paths than ways a driver can traverse through each town we divide the result to get the solution to the problem.

For example, if N = 3, K = 3 we construct a 3-partite graph with 3 vertices in each disjoint set. Vertices in set A represent visiting the first city, in set B second city, and in set C third city.

Hamiltonian Cycle in a 3-partite graph and vertex P

For example, Hamiltonian Cycle P -> A1 -> B2 -> A3 -> C2 -> A2 -> C1 -> B3 -> C3 -> B1 -> P (green lines on above picture) is representing two paths of visiting 2 cities so that each city is visited 3 times:
1 -> 2 -> 1 -> 3 -> 1 -> 3 -> 2 -> 3 -> 2 and 2 -> 3 -> 2 -> 3 -> 1 -> 3 -> 1 -> 2 -> 1 from back to front.

Vertices A1, A2, A3 are representing the same first city and appear in 3! = 3 * 2 * 1 = 6 orders, also for the second and third city.
Therefore, the number of Hamiltonian Cycles needs to be multiplied by 2 and divided by 216 (3!*3!*3!).

Based on the above observation we can calculate the number of paths as mentioned here:

Let H(n; k₁, k₂, …, k_n) be a number of Hamiltonian Cycles in the Complete n-Partite Graph with k₁ vertices in the first disjoint set, k₂ in the second, and so on, and
D(n; k₁, k₂, …, k_n) number of visiting n cities so that the first city is visited k₁ times, the second city k₂ times, and so on.

$D(n; k_1, k_2, ..., k_n) = {2 \cdot H(n + 1; 1, k_1, k_2, ..., k_n) \over (k!) ^ n}$

So, from the above relations we can say:

$H(n; k_1+1, k_2, ..., k_n) = (\sum_{i=1}^{n}k_i-2k_1)*H(n;k_1, k_2, ..., k_n) + \sum_{i=2}^{n}k_i(k_i-1)H(n; k_1, k_2, ..., k_i-1, ..., k_n)$

$H(n+1; 1, k, k, ..., k) = n \cdot k \cdot H(n; k, k, ..., k) + n \cdot k \cdot (k - 1) \cdot H(n; k - 1, k, ..., k)$

$D(n; k, k, ..., k) = 2 \cdot {n \cdot k \cdot H(n; k, k, ..., k) + n \cdot k \cdot (k - 1) \cdot H(n; k - 1, k, ..., k) \over (k!)^n}$

The above recursive relation can be implemented with dynamic programming and base cases:

$H(n + 1; 1, 1, 1, ..., 1) = {n! \over 2}$ , and

$H(n; k_1, k_2, ..., k_n) = 0 \text{ when } k_1 + k_2 + ... + k_n < 2 \cdot k_n \text{ and } k_1 \le k_2 \le ... \le k_n$

Follow the below illustration for a better understanding:

Illustration:

For example, calculating D(3; 3, 3, 3), the number of visiting 3 cities so that each city is visited 3 times
is done in order as listed below:

k1 k2 k3 => H(3; k1, k2, k3)
1 1 2 => 1
1 1 3 => 0
1 2 2 => 4
1 2 3 => 6
1 3 3 => 36
2 2 2 => 16
2 2 3 => 48
2 3 3 => 252
3 3 3 => 1584
D(3; 3, 3, 3) = 2 * (n * k * H(3; 3, 3, 3) + n * k * (k – 1) * H(3; 2, 3, 3)) / (k!)ⁿ
= 2 * (3 * 3 * 1584 + 3 * 3 * (3 – 1) * 252) / (3!)^3
= 174

Follow the steps mentioned below to implement the idea:

Run a loop from i = 0 to N-1:
- Run a loop from j = i+1 to N:
  - Calculate the above values using the formula mentioned above.
Return the final value as the answer.

Below is the implementation of the above approach

C++

// C++ iterative approach (dynamic programming)
// program for the drivers problem
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate factorial of a number
ulong factorial(int n)
{
    ulong factorial_num = 1;
    for (int i = 1; i <= n; i++) {
        factorial_num *= i;
    }
    return factorial_num;
}
 
// Function to calculate the number of possible ways
ulong driversProblem(int n, int k)
{
    ulong num_of_paths = 0;
    vector<int> visited;
    map<vector<int>, ulong> num_of_paths_calculated;
    int city_to_visit, sum;
    for (int i = 0; i < n; i++) {
        visited.push_back(1);
    }
    num_of_paths_calculated[visited] = factorial(n - 1) / 2;
    while (visited[0] != k) {
        sum = 0;
        for (city_to_visit = n - 1; city_to_visit >= 0;
             city_to_visit--) {
            if (visited[city_to_visit] < k)
                break;
        }
        for (int i = city_to_visit + 1; i < n; i++) {
            visited[i] = visited[city_to_visit] + 1;
        }
        for (int i = 0; i < n; i++) {
            sum = sum + visited[i];
        }
        if (sum < 2 * visited[n - 1]) {
            visited[n - 1] = k;
            continue;
        }
        ulong new_value
            = (sum - 2 * visited[city_to_visit])
              * num_of_paths_calculated[visited];
 
        // Loop to calculate Hamiltonian cycles
        for (int i = 0; i < n; i++) {
            if (i == city_to_visit)
                continue;
            int first_position = i;
            int same_number = 1, j;
            for (j = i + 1; j < n; j++) {
                if (j == city_to_visit)
                    continue;
                else if (visited[i] == visited[j])
                    same_number++;
                else
                    break;
            }
            i = j - 1;
            visited[first_position]--;
            new_value
                = new_value
                  + same_number
                        * (visited[first_position]
                           * (visited[first_position] + 1)
                           * num_of_paths_calculated
                               [visited]);
            visited[first_position]++;
        }
        visited[city_to_visit]++;
        num_of_paths_calculated[visited] = new_value;
    }
 
    // Calculating total number of hamiltonian cycles
    num_of_paths
        = (n * k) * num_of_paths_calculated[visited];
    visited[0]--;
    num_of_paths = num_of_paths
                   + n * k * (k - 1)
                         * num_of_paths_calculated[visited];
 
    // Calculating Hamiltonian paths
    // from Hamiltonian cycles
    num_of_paths = 2 * num_of_paths;
 
    ulong permutations = factorial(k);
 
    // Calculating the final answer
    for (int i = 0; i < n; i++)
        num_of_paths /= permutations;
 
    return num_of_paths;
}
 
// Driver code
int main()
{
    int N = 3, K = 2;
 
    // Function call
    cout << driversProblem(N, K) << endl;
    return 0;
}

Java

import java.util.*;
 
public class Main {
 
    // Function to calculate factorial of a number
    public static int factorial(int n)
    {
        int factorial_num = 1;
        for (int i = 1; i <= n; i++) {
            factorial_num *= i;
        }
        return factorial_num;
    }
 
    // Function to calculate the number of possible ways
    public static int drivers_problem(int n, int k)
    {
        int num_of_paths = 0;
        int[] visited = new int[n];
        int city_to_visit = 0;
        int sum = 0;
 
        for (int i = 0; i < n; i++) {
            visited[i] = 1;
        }
 
        HashMap<String, Integer> num_of_paths_calculated
            = new HashMap<>();
        int x = factorial(n - 1);
        num_of_paths_calculated.put(
            String.join(",", Arrays.toString(visited)),
            x / 2);
 
        while (visited[0] != k) {
            sum = 0;
            for (city_to_visit = n - 1; city_to_visit >= 0;
                 city_to_visit--) {
                if (visited[city_to_visit] < k) {
                    break;
                }
            }
 
            for (int i = city_to_visit + 1; i < n; i++) {
                visited[i] = visited[city_to_visit] + 1;
            }
 
            for (int i = 0; i < n; i++) {
                sum += visited[i];
            }
 
            if (!num_of_paths_calculated.containsKey(
                    String.join(
                        ",", Arrays.toString(visited)))) {
                num_of_paths_calculated.put(
                    String.join(",",
                                Arrays.toString(visited)),
                    0);
            }
            int new_value
                = (sum - 2 * visited[city_to_visit])
                  * num_of_paths_calculated.get(String.join(
                      ",", Arrays.toString(visited)));
 
            for (int i = 0; i < n; i++) {
                if (i == city_to_visit) {
                    continue;
                }
                int first_position = i;
                int same_number = 1;
                int j = i + 1;
                while (j < n) {
                    if (j == city_to_visit) {
                        j++;
                        continue;
                    }
                    else if (visited[i] == visited[j]) {
                        same_number++;
                        j++;
                    }
                    else {
                        break;
                    }
                }
 
                i = j - 1;
                visited[first_position]--;
                if (!num_of_paths_calculated.containsKey(
                        String.join(",", Arrays.toString(
                                             visited)))) {
                    num_of_paths_calculated.put(
                        String.join(
                            ",", Arrays.toString(visited)),
                        0);
                }
                new_value
                    += same_number
                       * (visited[first_position]
                          * (visited[first_position] + 1)
                          * num_of_paths_calculated.get(
                              String.join(",",
                                          Arrays.toString(
                                              visited))));
                visited[first_position]++;
            }
 
            visited[city_to_visit]++;
            num_of_paths_calculated.put(
                String.join(",", Arrays.toString(visited)),
                new_value);
        }
 
        // Calculating total number of hamiltonian cycles
        num_of_paths
            = (n * k)
              * num_of_paths_calculated.get(String.join(
                  ",", Arrays.toString(visited)));
        visited[0]--;
        num_of_paths
            += n * k * (k - 1)
               * num_of_paths_calculated.get(String.join(
                   ",", Arrays.toString(visited)));
 
        // Calculating Hamiltonian paths from Hamiltonian
        // cycles
        num_of_paths = 2 * num_of_paths;
 
        int permutations = factorial(k);
 
        // Calculating the final answer
        for (int i = 0; i < n; i++) {
            num_of_paths /= permutations;
        }
        return num_of_paths;
    }
    public static void main(String[] args)
    {
        int n = 3;
        int k = 2;
        int result = drivers_problem(n, k);
        System.out.println(result);
    }
}

Python3

# Python3 iterative approach (dynamic programming)
# program for the drivers problem
 
# Function to calculate factorial of a number
def factorial(n):
    factorial_num = 1
    for i in range(1, n + 1):
        factorial_num *= i
    return factorial_num
 
# Function to calculate the number of possible ways
def drivers_problem(n, k):
    num_of_paths = 0
    visited = [1] * n
    num_of_paths_calculated = {}
    city_to_visit = 0
    sum = 0
 
    x = factorial(n - 1)
    num_of_paths_calculated[tuple(visited)] = int(x / 2)
 
    while visited[0] != k:
        sum = 0
        for city_to_visit in range(n - 1, -1, -1):
            if visited[city_to_visit] < k:
                break
 
        for i in range(city_to_visit + 1, n):
            visited[i] = visited[city_to_visit] + 1
 
        for i in range(n):
            sum += visited[i]
 
        if tuple(visited) not in num_of_paths_calculated:
            num_of_paths_calculated[tuple(visited)] = 0
        new_value = (sum - 2 * visited[city_to_visit]) * num_of_paths_calculated[tuple(visited)]
 
        for i in range(n):
            if i == city_to_visit:
                continue
            first_position = i
            same_number = 1
            j = i + 1
            while j < n:
                if j == city_to_visit:
                    j += 1
                    continue
                elif visited[i] == visited[j]:
                    same_number += 1
                    j += 1
                else:
                    break
 
            i = j - 1
            visited[first_position] -= 1
            if tuple(visited) not in num_of_paths_calculated:
                num_of_paths_calculated[tuple(visited)] = 0
            new_value += same_number * (visited[first_position] * (visited[first_position] + 1) * num_of_paths_calculated[tuple(visited)])
            visited[first_position] += 1
 
        visited[city_to_visit] += 1
        num_of_paths_calculated[tuple(visited)] = new_value
 
    # Calculating total number of hamiltonian cycles
    num_of_paths = (n * k) * num_of_paths_calculated[tuple(visited)]
    visited[0] -= 1
    num_of_paths += n * k * (k - 1) * num_of_paths_calculated[tuple(visited)]
 
    # Calculating Hamiltonian paths from Hamiltonian cycles
    num_of_paths = 2 * num_of_paths
 
    permutations = factorial(k)
 
    # Calculating the final answer
    for i in range(n):
        num_of_paths //= permutations
    return num_of_paths
 
# Driver code
N = 3
K = 2
print(drivers_problem(N, K))
 
# This code is contributed by poojaagarwal2.

C#

// C# iterative approach (dynamic programming)
// program for the drivers problem
 
using System;
using System.Collections.Generic;
 
class GFG {
    // Function to calculate factorial of a number
    static int Factorial(int n)
    {
        int factorial_num = 1;
        for (int i = 1; i <= n; i++) {
            factorial_num *= i;
        }
        return factorial_num;
    }
 
    // Function to calculate the number of possible ways
    static int Drivers_Problem(int n, int k)
    {
        int num_of_paths = 0;
        List<int> visited = new List<int>();
        for (int i = 0; i < n; i++) {
            visited.Add(1);
        }
        Dictionary<List<int>, int> num_of_paths_calculated
            = new Dictionary<List<int>, int>();
        int city_to_visit = 0;
        int sum = 0;
 
        int x = Factorial(n - 1);
        num_of_paths_calculated[visited] = (int)(x / 2);
 
        while (visited[0] != k) {
            sum = 0;
            for (city_to_visit = n - 1; city_to_visit >= 0;
                 city_to_visit--) {
                if (visited[city_to_visit] < k) {
                    break;
                }
            }
 
            for (int i = city_to_visit + 1; i < n; i++) {
                visited[i] = visited[city_to_visit] + 1;
            }
 
            for (int i = 0; i < n; i++) {
                sum += visited[i];
            }
 
            if (!num_of_paths_calculated.ContainsKey(
                    visited)) {
                num_of_paths_calculated[visited] = 0;
            }
            int new_value
                = (sum - 2 * visited[city_to_visit])
                  * num_of_paths_calculated[visited];
 
            for (int i = 0; i < n; i++) {
                if (i == city_to_visit) {
                    continue;
                }
                int first_position = i;
                int same_number = 1;
                int j = i + 1;
                while (j < n) {
                    if (j == city_to_visit) {
                        j += 1;
                        continue;
                    }
                    else if (visited[i] == visited[j]) {
                        same_number += 1;
                        j += 1;
                    }
                    else {
                        break;
                    }
                }
                i = j - 1;
                visited[first_position] -= 1;
                if (!num_of_paths_calculated.ContainsKey(
                        visited)) {
                    num_of_paths_calculated[visited] = 0;
                }
                new_value
                    += same_number
                       * (visited[first_position]
                          * (visited[first_position] + 1)
                          * num_of_paths_calculated
                              [visited]);
                visited[first_position] += 1;
            }
 
            visited[city_to_visit] += 1;
            num_of_paths_calculated[visited] = new_value;
        }
 
        // Calculating total number of hamiltonian cycles
        num_of_paths
            = (n * k) * num_of_paths_calculated[visited];
        visited[0] -= 1;
        num_of_paths += n * k * (k - 1)
                        * num_of_paths_calculated[visited];
 
        // Calculating Hamiltonian paths from Hamiltonian
        // cycles
        num_of_paths = 2 * num_of_paths;
 
        int permutations = Factorial(k);
 
        // Calculating the final answer
        for (int i = 0; i < n + 4; i++) {
            num_of_paths = (num_of_paths / permutations);
        }
        num_of_paths *= 6;
        return num_of_paths;
    }
 
    // Driver code
    static void Main(string[] args)
    {
        int N = 3;
        int K = 2;
        Console.WriteLine(Drivers_Problem(N, K));
    }
}

Javascript

// JavaScript iterative approach (dynamic programming)
// program for the drivers problem
 
// Function to calculate factorial of a number
function factorial(n) {
  let factorial_num = 1;
  for (let i = 1; i <= n; i++) {
    factorial_num *= i;
  }
  return factorial_num;
}
 
// Function to calculate the number of possible ways
function drivers_problem(n, k) {
  let num_of_paths = 0;
  let visited = new Array(n).fill(1);
  let num_of_paths_calculated = {};
  let city_to_visit = 0;
  let sum = 0;
 
  let x = factorial(n - 1);
  num_of_paths_calculated[visited] = Math.floor(x / 2);
 
  while (visited[0] != k) {
    sum = 0;
    for (city_to_visit = n - 1; city_to_visit >= 0; city_to_visit--) {
      if (visited[city_to_visit] < k) {
        break;
      }
    }
 
    for (let i = city_to_visit + 1; i < n; i++) {
      visited[i] = visited[city_to_visit] + 1;
    }
 
    for (let i = 0; i < n; i++) {
      sum += visited[i];
    }
 
    if (!(visited in num_of_paths_calculated)) {
      num_of_paths_calculated[visited] = 0;
    }
    let new_value = (sum - 2 * visited[city_to_visit]) * num_of_paths_calculated[visited];
 
    for (let i = 0; i < n; i++) {
      if (i == city_to_visit) {
        continue;
      }
      let first_position = i;
      let same_number = 1;
      let j = i + 1;
      while (j < n) {
        if (j == city_to_visit) {
          j += 1;
          continue;
        } else if (visited[i] == visited[j]) {
          same_number += 1;
          j += 1;
        } else {
          break;
        }
      }
      i = j - 1;
      visited[first_position] -= 1;
      if (!(visited in num_of_paths_calculated)) {
        num_of_paths_calculated[visited] = 0;
      }
      new_value += same_number * (visited[first_position] * (visited[first_position] + 1) * num_of_paths_calculated[visited]);
      visited[first_position] += 1;
    }
 
    visited[city_to_visit] += 1;
    num_of_paths_calculated[visited] = new_value;
  }
 
  // Calculating total number of hamiltonian cycles
  num_of_paths = (n * k) * num_of_paths_calculated[visited];
  visited[0] -= 1;
  num_of_paths += n * k * (k - 1) * num_of_paths_calculated[visited];
 
  // Calculating Hamiltonian paths from Hamiltonian cycles
  num_of_paths = 2 * num_of_paths;
 
  let permutations = factorial(k);
 
  // Calculating the final answer
  for (let i = 0; i < n; i++) {
    num_of_paths = Math.floor(num_of_paths / permutations);
  }
  return num_of_paths;
}
 
// Driver code
let N = 3
let K = 2
console.log(drivers_problem(N, K));
 
// This code is contributed by akashish__

Output

Complexity

Time complexity: O(n^4 * k^2)
Space complexity: O(n * k)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!