Given List of elements, for list of tuples, where each represents the continuity of occurrence of each element.
Input : test_list = [1, 1, 5, 6, 5, 5]
Output : {1: [(0, 1)], 5: [(2, 2), (4, 5)], 6: [(3, 3)]}
Explanation : 5 present at 2nd idx and also in continuation in 4th and 5th index, and hence recorded range.Input : test_list = [5, 5, 5, 5, 5, 5]
Output : {5: [(0, 5)]}
Explanation : Only 5 present, hence recorded.
Method 1: Using groupby() + defaultdict() + len() + loop
In this, we perform consecutive elements grouping using groupby(), defaultdict() is used to initialize the tuple list, The len() is used to get length of repetition.
Python3
# Python3 code to demonstrate working of # Grouped Consecutive Range Indices of Elements# Using groupby() + defaultdict() + len() + loopfrom itertools import groupbyfrom collections import defaultdict# initializing liststest_list = [1, 1, 5, 6, 5, 5, 6, 6, 6, 1, 5, 5]# printing stringprint("The original list : " + str(test_list))idx = 0res = defaultdict(list)# grouping Consecutivesfor key, sub in groupby(test_list): ele = len(list(sub)) # append strt index, and till index res[key].append((idx, idx + ele - 1)) idx += ele# printing results print("The grouped dictionary : " + str(dict(res))) |
The original list : [1, 1, 5, 6, 5, 5, 6, 6, 6, 1, 5, 5]
The grouped dictionary : {1: [(0, 1), (9, 9)], 5: [(2, 2), (4, 5), (10, 11)], 6: [(3, 3), (6, 8)]}
Time complexity: O(n), where n is the length of the input list.
Auxiliary space: O(k), where k is the number of unique elements in the input list.
Method 2: Using loop and dictionary
- Initialize an empty dictionary called res to store the grouped ranges.
- Initialize a variable i to keep track of the current position in the list.
- Start a while loop that will continue until the end of the list is reached.
- Get the current element in the list using test_list[i] and use it as the key for the dictionary.
- Initialize a variable start to store the starting index of the current group, which is the current value of i.
- Start another while loop that will continue as long as the current element in the list is equal to the key.
- Within the loop, increment i to move to the next element in the list.
- When the loop ends, i-1 is the end index of the current group.
- Append a tuple of (start, end) to the list for the current key in the dictionary using res.setdefault(key, []).append((start, end)).
- Repeat the loop from step 4 until the end of the list is reached.
- Print the resulting dictionary of grouped ranges.
Python3
# Python3 code to demonstrate working of# Grouped Consecutive Range Indices of Elements# Using loop and dictionary# initializing liststest_list = [1, 1, 5, 6, 5, 5, 6, 6, 6, 1, 5, 5]# printing stringprint("The original list : " + str(test_list))# create an empty dictionary to store the grouped rangesres = {}# initialize an index variable to keep track of the current position in the listi = 0# iterate over the listwhile i < len(test_list): # get the current element as the key for the dictionary key = test_list[i] # initialize a start variable to store the starting index of the group start = i # loop through the list as long as the next element is equal to the current element while i < len(test_list) and test_list[i] == key: i += 1 # when the loop ends, i-1 is the end index of the group end = i - 1 # append the start and end indices to the list for the current key in the dictionary res.setdefault(key, []).append((start, end))# printing resultsprint("The grouped dictionary : " + str(res)) |
The original list : [1, 1, 5, 6, 5, 5, 6, 6, 6, 1, 5, 5]
The grouped dictionary : {1: [(0, 1), (9, 9)], 5: [(2, 2), (4, 5), (10, 11)], 6: [(3, 3), (6, 8)]}
Time Complexity: O(n), where n is the length of the input list. The approach iterates through the input list exactly once, and the inner loop executes a constant number of times for each element in the list.
Auxiliary Space: O(n), where n is the length of the input list. The approach creates a dictionary to store the grouped ranges, with each group represented as a tuple of start and end indices.
Method 3: Using itertools.groupby() – We first groups the consecutive elements in test_list using itertools.groupby(), and then maps the resulting groups to a dictionary with keys as the unique elements in the list and values as the indices of the groups. The indices are calculated using enumerate() and the start and end indices are computed based on the length of each group.
Python3
import itertoolstest_list = [1, 1, 5, 6, 5, 5, 6, 6, 6, 1, 5, 5]# Using itertools.groupby() to group consecutive elementsgroups = [(k, list(g)) for k, g in itertools.groupby(test_list)]# Mapping the groups to a dictionaryres = {k: [(i, i + len(g) - 1) for i, (k_, g) in enumerate(groups) if k_ == k] for k, _ in groups}print("The grouped dictionary : " + str(res)) |
The grouped dictionary : {1: [(0, 1), (5, 5)], 5: [(1, 1), (3, 4), (6, 7)], 6: [(2, 2), (4, 6)]}
Time complexity: O(n), where n is the length of the input list test_list.
Auxiliary space: O(n), where n is the length of the input list test_list.
Method 4: Using numpy.split().
The algorithm works as follows:
- Convert the input list into a NumPy array.
- Use the np.diff() function to compute the difference between consecutive elements of the array, and add a -1 at the beginning and end of the result.
- Use the np.flatnonzero() function to find the indices of the non-zero elements in the result.
- Use the np.split() function to split the array into subarrays at the positions indicated by the non-zero indices.
- Iterate over the subarrays, and for each one:
a. Determine the key value (i.e., the first element of the subarray).
b. Determine the start and end indices of the subarray.
c. Add an entry to the result dictionary, with the key value as the key and a tuple containing the start and end indices as the value.
Python3
import numpy as nptest_list = [1, 1, 5, 6, 5, 5, 6, 6, 6, 1, 5, 5]arr = np.array(test_list)splits = np.flatnonzero(np.diff(arr, prepend=-1, append=-1))groups = np.split(np.arange(len(test_list)), splits[1:])res = {}for key, indices in zip(arr[splits[:-1]], groups): res.setdefault(key, []).append((indices[0], indices[-1]))print("The grouped dictionary : " + str(res)) |
Output
The grouped dictionary : {1: [(0, 1), (5, 5)], 5: [(1, 1), (3, 4), (6, 7)], 6: [(2, 2), (4, 6)]}
The time complexity of this algorithm is O(n), where n is the length of the input list, because it involves a single pass over the input list, and each operation inside the loop takes constant time.
The auxiliary space is also O(n), because it involves creating a NumPy array and a dictionary with at most n entries.
Method 5:using a recursive function:
Algorithm:
1.Define a recursive function group_consecutive_range_indices that takes test_list, res and start as arguments.
2.Inside the function, check if res is None, if so create a defaultdict object to store the results.
3.Check if start is greater than or equal to the length of test_list, if so return the result as a dictionary.
4.Define end as start.
5.While end is less than the length of test_list and the element at index end is equal to the element at index start, increment end.
6.Append the range of indices from start to end-1 for the element at index start to the res dictionary.
7.Call the group_consecutive_range_indices function recursively with updated start and res values.
8.Outside the function, initialize test_list and call the group_consecutive_range_indices function.
9.Print the original list and the resulting grouped dictionary.
Python3
from collections import defaultdictdef group_consecutive_range_indices(test_list, res=None, start=0): if res is None: res = defaultdict(list) if start >= len(test_list): return dict(res) end = start while end < len(test_list) and test_list[end] == test_list[start]: end += 1 res[test_list[start]].append((start, end - 1)) return group_consecutive_range_indices(test_list, res, end)# initializing liststest_list = [1, 1, 5, 6, 5, 5, 6, 6, 6, 1, 5, 5]# printing stringprint("The original list : " + str(test_list))# grouping Consecutives using recursionres = group_consecutive_range_indices(test_list)# printing resultsprint("The grouped dictionary : " + str(res))#This code is contributed by Vinay pinjala |
The original list : [1, 1, 5, 6, 5, 5, 6, 6, 6, 1, 5, 5]
The grouped dictionary : {1: [(0, 1), (9, 9)], 5: [(2, 2), (4, 5), (10, 11)], 6: [(3, 3), (6, 8)]}
Time Complexity: O(n), where n is the length of the input list. The function needs to traverse the entire list to group consecutive elements.
Auxiliary Space: O(n), where n is the length of the input list. The function uses a defaultdict object to store the results, which can have at most n distinct keys, and each key can have a list of ranges with at most n elements.
