Sometimes while working with Python dictionaries, we can have a problem in which we need to extract combination of certain key’s value of size K. This is usually when values are in form of strings. This can have application in day-day programming. Let’s discuss a way in which this task can be performed.
Input : test_dict = {‘a’ : ‘a’, ‘b’ : ‘b’, ‘c’ : ‘c’, ‘d’ : ‘d’}
Output : [‘aaa’, ‘bbb’, ‘ccc’, ‘ddd’]Input : test_dict = {‘a’ : ‘abcd’, ‘b’ : ”, ‘c’ : ”, ‘d’ : ”}
Output : [‘aaa’, ‘aab’, ‘aac’, ‘aad’]
Method 1: Using recursion + generator function + yield
The combination of above functionalities can be used to solve this problem. In this, we perform the task of combinations all possible using recursion. The generator function is used to dynamically create values and return to calling function using yield.
Python3
# Python3 code to demonstrate working of # Dictionary values combination of size K# Using yield + generator function + recursiondef gen_strs(chr_key, test_dict, K): def hlpr(s): if len(s) == K: yield s elif len(s) < K: for ltr in test_dict[s[-1]]: yield from hlpr(s + ltr) for ltr in chr_key: yield from hlpr(ltr)# initializing dictionarytest_dict = {'a' : 'abc', 'b' : 'bd', 'c' : 'c', 'd' : 'ab'}# printing original dictionaryprint("The original dictionary : " + str(test_dict))# initializing K K = 3# initializing character keys chr_key = 'abcd'# Dictionary values combination of size K# Using yield + generator function + recursionres = []for ele in gen_strs(chr_key, test_dict, K): res.append(ele)# printing result print("The extracted combinations : " + str(res)) |
The original dictionary : {‘b’: ‘bd’, ‘a’: ‘abc’, ‘d’: ‘ab’, ‘c’: ‘c’}
The extracted combinations : [‘aaa’, ‘aab’, ‘aac’, ‘abb’, ‘abd’, ‘acc’, ‘bbb’, ‘bbd’, ‘bda’, ‘bdb’, ‘ccc’, ‘daa’, ‘dab’, ‘dac’, ‘dbb’, ‘dbd’]
Time Complexity: O(n), where n is the length of the list test_dict
Auxiliary Space: O(n) additional space of size n is created where n is the number of elements in the res list
Method 2: Using itertools.product() function:
Approach:
We can use the itertools.product() function to generate all possible combinations of size K from the values in the dictionary. We can first create a list of the values in the dictionary and then use the itertools.product() function to generate all possible combinations of size K.
Python3
import itertoolsdef generate_combinations(test_dict, K): values = list(test_dict.values()) result = [] for combination in itertools.product(values, repeat=K): temp = ''.join(combination) result.append(temp*K) return resulttest_dict1 = {'a' : 'a', 'b' : 'b', 'c' : 'c', 'd' : 'd'}test_dict2 = {'a' : 'abcd', 'b' : '', 'c' : '', 'd' : ''}K = 3output1 = generate_combinations(test_dict1, K)print(output1) # Expected Output : ['aaa', 'bbb', 'ccc', 'ddd']output2 = generate_combinations(test_dict2, K)print(output2) # Expected Output : ['aaa', 'aab', 'aac', 'aad'] |
...addaddad', 'dbadbadba', 'dbbdbbdbb', 'dbcdbcdbc', 'dbddbddbd', 'dcadcadca', 'dcbdcbdcb', 'dccdccdcc', 'dcddcddcd', 'ddaddadda', 'ddbddbddb', 'ddcddcddc', 'ddddddddd'] ['abcdabcdabcdabcdabcdabcdabcdabcdabcd', 'abcdabcdabcdabcdabcdabcd', 'abcdabcdabcdabcdabcdabcd', 'abcdabcdabcdabcdabcdabcd', 'abcdabcdabcdabcdabcdabcd', 'abcdabcdabcd', 'abcdabcdabcd', 'abcdabcdabcd', 'abcdabcdabcdabcdabcdabcd', 'abcdabcdabcd', 'abcdabcdabcd', 'abcdabcdabcd', 'abcdabcdabcdabcdabcdabcd', 'abcdabcdabcd', 'abcdabcdabcd', 'abcdabcdabcd', 'abcdabcdabcdabcdabcdabcd', 'abcdabcdabcd', 'abcdabcdabcd', 'abcdabcdabcd', 'abcdabcdabcd', '', '', '', 'abcdabcdabcd', '', '', '', 'abcdabcdabcd', '', '', '', 'abcdabcdabcdabcdabcdabcd', 'abcdabcdabcd', 'abcdabcdabcd', 'abcdabcdabcd', 'abcdabcdabcd', '', '', '', 'abcdabcdabcd', '', '', '', 'abcdabcdabcd', '', '', '', 'abcdabcdabcdabcdabcdabcd', 'abcdabcdabcd', 'abcdabcdabcd', 'abcdabcdabcd', 'abcdabcdabcd', '', '', '', 'abcdabcdabcd', '', '', '', 'abcdabcdabcd', '', '', '']
Time Complexity: O(n^K), where n is the number of values in the dictionary.
Space Complexity: O(n^K), as we need to store all possible combinations in the list.
Method 3: Using Nested for Loops
- Step 1: Initialize an empty list called combinations.
- Step 2: Use a nested for loop to iterate over the values of the dictionary, test_dict.
- Step 3: Inside the inner loop, use another nested loop to iterate over the values of the dictionary for the next key, and so on until K levels of nested loops have been completed.
- Step 4: For each combination of values, join them together into a single string and append the string to the combinations list.
- Step 5: Return the combinations list.
Python3
def find_combinations(test_dict, K, chr_key): combinations = [] for value_1 in test_dict[chr_key[0]]: if K == 1: combinations.append(value_1) else: for value_2 in test_dict[chr_key[1]]: if K == 2: combinations.append(value_1 + value_2) else: for value_3 in test_dict[chr_key[2]]: if K == 3: combinations.append(value_1 + value_2 + value_3) else: for value_4 in test_dict[chr_key[3]]: combinations.append(value_1 + value_2 + value_3 + value_4) return combinations# Example usagetest_dict = {'a': 'abc', 'b': 'bd', 'c': 'c', 'd': 'ab'}K = 3chr_key = 'abcd'combinations = find_combinations(test_dict, K, chr_key)print(combinations) |
['abc', 'adc', 'bbc', 'bdc', 'cbc', 'cdc']
Time complexity: O(N^K), where N is the maximum number of values for a key in the dictionary.
Auxiliary space: O(N^K), to store the list of all combinations.
