Python | Incremental slice partition in list
Sometimes, while working with lists, we can come across a problem in which we need to slice a list incrementally, i.e., with each slice, the number of elements increases by 1. This has applications in competitive programming. Let’s discuss certain ways in which this task can be performed.
Method #1: Using loops
This is the brute force method by which this task can be performed. We just manually count and increase the counter with each iteration for slicing and dictionary key creation.
Python3
# Python3 code to demonstrate working of # Incremental slice partition in list # Using loop # initializing list test_list = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 ] # printing original list print ( "The original list is : " + str (test_list)) # Incremental slice partition in list # Using loop res = {} N = 1 strt = 0 # Till we have start within list length while strt < len (test_list): res[N] = test_list[strt: strt + N] strt + = N N + = 1 # printing result print ( "The partitioned dictionary from list is : " + str (res)) |
The original list is : [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] The partitioned dictionary from list is : {1: [1], 2: [2, 3], 3: [4, 5, 6], 4: [7, 8, 9, 10]}
Time complexity: O(n^2)
Auxiliary space: O(n)
Method #2: Using enumerate() + slice() + next() + iter() + count()
The combination of the above functions can be used to perform this task. In this, next() is used to iterate the list converted to iterator by iter(). The slice() performs list slicing. The count() helps in managing the counter and enumerate keeps track of elements and indices in the list.
Python3
# Python3 code to demonstrate working of # Incremental slice partition in list # Using enumerate() + slice() + next() + iter() + count() from itertools import islice, count # initializing list test_list = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 ] # printing original list print ( "The original list is : " + str (test_list)) # Incremental slice partition in list # Using enumerate() + slice() + next() + iter() + count() res = {key: val for key, val in enumerate ( iter ( lambda i = iter (test_list), c = count( 1 ): list (islice(i, next (c))), []), 1 )} # printing result print ( "The partitioned dictionary from list is : " + str (res)) |
The original list is : [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] The partitioned dictionary from list is : {1: [1], 2: [2, 3], 3: [4, 5, 6], 4: [7, 8, 9, 10]}
Time complexity: O(n)
Auxiliary space: O(n)
Using recursion:
Python3
def recursive_slice(lst, start, step, res): # base case: if start index exceeds the length of the list, # return the result if start > = len (lst): return res # slice the list and store it in the result dictionary res[step] = lst[start: start + step] # recursively call the function with updated start and step index return recursive_slice(lst, start + step, step + 1 , res) # initial test list test_list = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 ] # empty dictionary to store the result result = {} # calling the recursive function and print the result print (recursive_slice(test_list, 0 , 1 , result)) |
{1: [1], 2: [2, 3], 3: [4, 5, 6], 4: [7, 8, 9, 10]}
Time complexity: O(n)
Auxiliary Space: O(n)
Method 4: Using itertools
Python3
# Python3 code to demonstrate working of # Incremental slice partition in list # Using itertools import itertools # initializing list test_list = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 ] # printing original list print ( "The original list is: " + str (test_list)) # Incremental slice partition in list # Using itertools res = {} start = 0 # slice partioning the list for i in itertools.count( 1 ): slice_len = min (i, len (test_list) - start) if slice_len = = 0 : break res[i] = test_list[start: start + slice_len] start + = slice_len # printing result print ( "The partitioned dictionary from list is: " + str (res)) |
The original list is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] The partitioned dictionary from list is: {1: [1], 2: [2, 3], 3: [4, 5, 6], 4: [7, 8, 9, 10]}
Time complexity: O(n^2), where n is the length of the input list.
Auxiliary space: O(n), where n is the length of the input list.
Contact Us