Merge branch 'master' into strassen-multiplication

ShuN6211 · Jan 24, 2023 · 0545555 · 0545555
2 parents 729e874 + a6a9d8e
commit 0545555
Show file tree

Hide file tree

Showing 9 changed files with 844 additions and 208 deletions.
diff --git a/DIRECTORY.md b/DIRECTORY.md
@@ -20,6 +20,7 @@
   * [Find Non Repeating Number](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/bit_manipulation/find_non_repeating_number.cpp)
   * [Hamming Distance](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/bit_manipulation/hamming_distance.cpp)
   * [Set Kth Bit](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/bit_manipulation/set_kth_bit.cpp)
+  * [Travelling Salesman Using Bit Manipulation](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/bit_manipulation/travelling_salesman_using_bit_manipulation.cpp)
 
 ## Ciphers
   * [A1Z26 Cipher](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/ciphers/a1z26_cipher.cpp)
@@ -66,7 +67,7 @@
   * [Reverse A Linked List](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/data_structures/reverse_a_linked_list.cpp)
   * [Skip List](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/data_structures/skip_list.cpp)
   * [Sparse Table](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/data_structures/sparse_table.cpp)
-  * [Stack](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/data_structures/stack.h)
+  * [Stack](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/data_structures/stack.hpp)
   * [Stack Using Array](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/data_structures/stack_using_array.cpp)
   * [Stack Using Linked List](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/data_structures/stack_using_linked_list.cpp)
   * [Stack Using Queue](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/data_structures/stack_using_queue.cpp)

diff --git a/bit_manipulation/travelling_salesman_using_bit_manipulation.cpp b/bit_manipulation/travelling_salesman_using_bit_manipulation.cpp
@@ -0,0 +1,119 @@
+/**
+ * @file
+ * @brief Implementation to
+ * [Travelling Salesman problem using bit-masking]
+ * (https://www.geeksforgeeks.org/travelling-salesman-problem-set-1/)
+ *
+ * @details
+ * Given the distance/cost(as and adjacency matrix) between each city/node to the other city/node ,
+ * the problem is to find the shortest possible route that visits every city exactly once
+ * and returns to the starting point or we can say the minimum cost of whole tour.
+ *
+ * Explanation:
+ *  INPUT -> You are given with a adjacency matrix A = {} which contains the distance between two cities/node.
+ *
+ *  OUTPUT ->  Minimum cost of whole tour from starting point
+ *
+ * Worst Case Time Complexity: O(n^2 * 2^n)
+ * Space complexity: O(n)
+ * @author [Utkarsh Yadav](https://github.com/Rytnix)
+ */
+#include <algorithm>   /// for std::min
+#include <cassert>    /// for assert
+#include <iostream>  /// for IO operations
+#include <vector>   /// for std::vector 
+#include <limits>  /// for limits of integral types
+
+/**
+ * @namespace bit_manipulation
+ * @brief Bit manipulation algorithms
+ */
+namespace bit_manipulation {
+/**
+ * @namespace travellingSalesman_bitmanipulation
+ * @brief Functions for the [Travelling Salesman
+ * Bitmask](https://www.geeksforgeeks.org/travelling-salesman-problem-set-1/)
+ * implementation
+ */
+namespace travelling_salesman_using_bit_manipulation {
+/**
+ * @brief The function implements travellingSalesman using bitmanipulation
+ * @param dist is the cost to reach between two cities/nodes
+ * @param setOfCitites represents the city in bit form.\
+ * @param city is taken to track the current city movement.
+ * @param n is the no of citys .
+ * @param dp vector is used to keep a record of state to avoid the recomputation.
+ * @returns minimum cost of traversing whole nodes/cities from starting point back to starting point
+ */
+std::uint64_t travelling_salesman_using_bit_manipulation(std::vector<std::vector<uint32_t>> dist,  // dist is the adjacency matrix containing the distance.
+        // setOfCities as a bit represent the cities/nodes. Ex: if setOfCities = 2 => 0010(in binary)
+        // means representing the city/node B if city/nodes are represented as D->C->B->A.
+        std::uint64_t setOfCities,
+        std::uint64_t city, // city is taken to track our current city/node movement,where we are currently.
+        std::uint64_t n, // n is the no of cities we have.
+        std::vector<std::vector<uint32_t>> &dp) //dp is taken to memorize the state to avoid recomputition
+{
+    //base case;
+    if (setOfCities == (1 << n) - 1) // we have covered all the cities
+        return dist[city][0]; //return the cost from the current city to the original city.
+
+    if (dp[setOfCities][city] != -1)
+        return dp[setOfCities][city];
+    //otherwise try all possible options
+    uint64_t ans = 2147483647 ;
+    for (int choice = 0; choice < n; choice++) {
+        //check if the city is visited or not.
+        if ((setOfCities & (1 << choice)) == 0 ) { // this means that this perticular city is not visited.
+            std::uint64_t subProb = dist[city][choice] + travelling_salesman_using_bit_manipulation(dist, setOfCities | (1 << choice), choice, n, dp);
+            // Here we are doing a recursive call to tsp with the updated set of city/node
+            // and choice which tells that where we are currently.
+            ans = std::min(ans, subProb);
+        }
+
+    }
+    dp[setOfCities][city] = ans;
+    return ans;
+}
+} // namespace travelling_salesman_using_bit_manipulation
+} // namespace bit_manipulation
+
+/**
+ * @brief Self-test implementations
+ * @returns void
+ */
+static void test() {
+    // 1st test-case
+    std::vector<std::vector<uint32_t>> dist = {
+        {0, 20, 42, 35}, {20, 0, 30, 34}, {42, 30, 0, 12}, {35, 34, 12, 0}
+    };
+    uint32_t V = dist.size();
+    std::vector<std::vector<uint32_t>> dp(1 << V, std::vector<uint32_t>(V, -1));
+    assert(bit_manipulation::travelling_salesman_using_bit_manipulation::travelling_salesman_using_bit_manipulation(dist, 1, 0, V, dp) == 97);
+    std::cout << "1st test-case: passed!" << "\n";
+
+    // 2nd test-case
+    dist = {{0, 5, 10, 15}, {5, 0, 20, 30}, {10, 20, 0, 35}, {15, 30, 35, 0}};
+    V = dist.size();
+    std::vector<std::vector<uint32_t>> dp1(1 << V, std::vector<uint32_t>(V, -1));
+    assert(bit_manipulation::travelling_salesman_using_bit_manipulation::travelling_salesman_using_bit_manipulation(dist, 1, 0, V, dp1) == 75);
+    std::cout << "2nd test-case: passed!" << "\n";
+    // 3rd test-case
+    dist = {
+        {0, 10, 15, 20}, {10, 0, 35, 25}, {15, 35, 0, 30}, {20, 25, 30, 0}
+    };
+    V = dist.size();
+    std::vector<std::vector<uint32_t>> dp2(1 << V, std::vector<uint32_t>(V, -1));
+    assert(bit_manipulation::travelling_salesman_using_bit_manipulation::travelling_salesman_using_bit_manipulation(dist, 1, 0, V, dp2) == 80);
+
+    std::cout << "3rd test-case: passed!" << "\n";
+
+}
+
+/**
+ * @brief Main function
+ * @returns 0 on exit
+ */
+int main() {
+    test();  // run self-test implementations
+    return 0;
+}
diff --git a/data_structures/stack.h b/data_structures/stack.h
diff --git a/data_structures/stack.hpp b/data_structures/stack.hpp
@@ -0,0 +1,106 @@
+/**
+ * @file
+ * @author danghai
+ * @author [Piotr Idzik](https://github.com/vil02)
+ * @brief  This class specifies the basic operation on a stack as a linked list
+ **/
+#ifndef DATA_STRUCTURES_STACK_HPP_
+#define DATA_STRUCTURES_STACK_HPP_
+
+#include <iostream>   /// for IO operations
+#include <memory>     /// for std::shared_ptr
+#include <stdexcept>  /// for std::invalid_argument
+#include <vector>     /// for std::vector
+
+/** Definition of the node as a linked-list
+ * \tparam ValueType type of data nodes of the linked list should contain
+ */
+template <class ValueType>
+struct node {
+    ValueType data = {};  ///< data at current node
+    std::shared_ptr<node<ValueType>> next =
+        {};  ///< pointer to the next ::node instance
+};
+
+template <typename Node, typename Action>
+void traverse(const Node* const inNode, const Action& action) {
+    if (inNode) {
+        action(*inNode);
+        traverse(inNode->next.get(), action);
+    }
+}
+
+/** Definition of the stack class
+ * \tparam value_type type of data nodes of the linked list in the stack should
+ * contain
+ */
+template <class ValueType>
+class stack {
+ public:
+    using value_type = ValueType;
+
+    /** Show stack */
+    void display() const {
+        std::cout << "Top --> ";
+        traverse(stackTop.get(), [](const node<value_type>& inNode) {
+            std::cout << inNode.data << "  ";
+        });
+        std::cout << std::endl;
+        std::cout << "Size of stack: " << size << std::endl;
+    }
+
+    std::vector<value_type> toVector() const {
+        std::vector<value_type> res;
+        res.reserve(this->size);
+        traverse(stackTop.get(), [&res](const node<value_type>& inNode) {
+            res.push_back(inNode.data);
+        });
+        return res;
+    }
+
+ private:
+    void ensureNotEmpty() const {
+        if (isEmptyStack()) {
+            throw std::invalid_argument("Stack is empty.");
+        }
+    }
+
+ public:
+    /** Determine whether the stack is empty */
+    bool isEmptyStack() const { return (stackTop == nullptr); }
+
+    /** Add new item to the stack */
+    void push(const value_type& item) {
+        auto newNode = std::make_shared<node<value_type>>();
+        newNode->data = item;
+        newNode->next = stackTop;
+        stackTop = newNode;
+        size++;
+    }
+
+    /** Return the top element of the stack */
+    value_type top() const {
+        ensureNotEmpty();
+        return stackTop->data;
+    }
+
+    /** Remove the top element of the stack */
+    void pop() {
+        ensureNotEmpty();
+        stackTop = stackTop->next;
+        size--;
+    }
+
+    /** Clear stack */
+    void clear() {
+        stackTop = nullptr;
+        size = 0;
+    }
+
+ private:
+    std::shared_ptr<node<value_type>> stackTop =
+        {};                /**< Pointer to the stack */
+    std::size_t size = 0;  ///< size of stack
+};
+
+#endif  // DATA_STRUCTURES_STACK_HPP_