Merge pull request prabhupant#312 from aadityachapagain/master

prabhupant · web-flow · commit 16f8da5b37a5 · 2019-11-14T10:08:07.000+05:30
Bit Masking using Dynamic programming
diff --git a/algorithms/dynamic_programming/bit_masking1.py b/algorithms/dynamic_programming/bit_masking1.py
@@ -0,0 +1,99 @@
+"""
+Consider the below problems statement.
+
+There are 100 different types of caps each having a unique id from 1 to 100. Also,
+there are ‘n’ persons each having a collection of a variable number of caps.
+One day all of these persons decide to go in a party wearing a cap but to look unique
+they decided that none of them will wear the same type of cap. So, count the total number
+of arrangements or ways such that none of them is wearing the same type of cap.
+
+"""
+
+# Python program to find number of ways to wear hats
+from collections import defaultdict
+
+
+class AssignCap:
+
+    # Initialize variables
+    def __init__(self):
+
+        self.allmask = 0
+
+        self.total_caps = 100
+
+        self.caps = defaultdict(list)
+
+    #  Mask is the set of persons, i is the current cap number.
+    def count_ways_util(self, dp, mask, cap_no):
+
+        # If all persons are wearing a cap so we
+        # are done and this is one way so return 1
+        if mask == self.allmask:
+            return 1
+
+        # If not everyone is wearing a cap and also there are no more
+        # caps left to process, so there is no way, thus return 0;
+        if cap_no > self.total_caps:
+            return 0
+
+        # If we have already solved this subproblem, return the answer.
+        if dp[mask][cap_no] != -1:
+            return dp[mask][cap_no]
+
+        # Ways, when we don't include this cap in our arrangement
+        # or solution set
+        ways = self.count_ways_util(dp, mask, cap_no + 1)
+
+        # assign ith cap one by one  to all the possible persons
+        # and recur for remaining caps.
+        if cap_no in self.caps:
+
+            for ppl in self.caps[cap_no]:
+
+                # if person 'ppl' is already wearing a cap then continue
+                if mask & (1 << ppl):
+                    continue
+
+                # Else assign him this cap and recur for remaining caps with
+                # new updated mask vector
+                ways += self.count_ways_util(dp, mask | (1 << ppl), cap_no + 1)
+
+                ways = ways % (10**9 + 7)
+
+        # Save the result and return it
+        dp[mask][cap_no] = ways
+
+        return dp[mask][cap_no]
+
+    def count_ways(self, N):
+
+        # Reads n lines from standard input for current test case
+        # create dictionary for cap. cap[i] = list of person having
+        # cap no i
+        for ppl in range(N):
+
+            cap_possessed_by_person = map(int, input().strip().split())
+
+            for i in cap_possessed_by_person:
+
+                self.caps[i].append(ppl)
+
+        # allmask is used to check if all persons
+        # are included or not, set all n bits as 1
+        self.allmask = (1 << N) - 1
+
+        # Initialize all entries in dp as -1
+        dp = [[-1 for j in range(self.total_caps + 1)] for i in range(2 ** N)]
+
+        # Call recursive function countWaysUtil
+        # result will be in dp[0][1]
+        print(self.count_ways_util(dp, 0, 1,))
+
+# Driver Program
+
+
+def main():
+    No_of_people = int(input())  # number of persons in every test case
+
+    AssignCap().count_ways(No_of_people)
diff --git a/algorithms/dynamic_programming/k_palindrome1.py b/algorithms/dynamic_programming/k_palindrome1.py
@@ -0,0 +1,65 @@
+# code to find if given string
+# is K-Palindrome or not
+
+"""
+Explanation
+
+Process all characters one by one staring from either from left or right sides of both strings.
+Let us traverse from the right corner, there are two possibilities for every pair of character being traversed.
+
+If last characters of two strings are same, we ignore last characters and get count for remaining strings.
+So we recur for lengths m-1 and n-1 where m is length of str1 and n is length of str2.
+If last characters are not same, we consider remove operation on last character of first string and
+last character of second string, recursively compute minimum cost for the operations and take minimum of two values.
+Remove last char from str1: Recur for m-1 and n.
+Remove last char from str2: Recur for m and n-1.
+"""
+
+# Find if given string
+# is K-Palindrome or not
+
+
+def is_kpalrec(str1, str2, m, n):
+
+    # If first string is empty,
+    # the only option is to remove
+    # all characters of second string
+    if not m:
+        return n
+
+    # If second string is empty,
+    # the only option is to remove
+    # all characters of first string
+    if not n:
+        return m
+
+    # If last characters of two strings
+    # are same, ignore last characters
+    # and get count for remaining strings.
+    if str1[m - 1] == str2[n - 1]:
+        return isKPalRec(str1, str2, m - 1, n - 1)
+
+    # If last characters are not same,
+    # 1. Remove last char from str1 and recur for m-1 and n
+    # 2. Remove last char from str2 and recur for m and n-1
+    # Take minimum of above two operations
+    res = 1 + min(is_kpalrec(str1, str2, m - 1, n),  # Remove from str1
+                  (is_kpalrec(str1, str2, m, n - 1)))  # Remove from str2
+
+    return res
+
+# Returns true if str is k palindrome.
+
+
+def is_kPal(string, k):
+    revStr = string[::-1]
+    l = len(string)
+
+    return (is_kpalrec(string, revStr, l, l) <= k * 2)
+
+
+# Driver program
+string = "acdcb"
+k = 2
+
+print("Yes" if is_kPal(string, k) else "No")
