Python | Reshape a list according to given multi list

Given two lists, a single dimensional and a multidimensional list, write Python program to reshape the single dimensional list according to the length of multidimensional list. 

Examples:

Input : list1 = [[1], [2, 3], [4, 5, 6]]
        list2 = ['a', 'b', 'c', 'd', 'e', 'f']
Output : [['a'], ['b', 'c'], ['d', 'e', 'f']]

Input : list1 = [[8, 2, 5], [1], [12, 4, 0, 24]]
        list2 = ['m', 'n', 'o', 'p', 'q', 'r', 's', 't']
Output : [['m', 'n', 'o'], ['p'], ['q', 'r', 's', 't']]

  Method #1 : Using extended slices A simple and naive method is to use a for loop and Python extended slices to append each sublist of list2 to a variable ‘res’. 

[['a'], ['b', 'c'], ['d', 'e', 'f']]

  Method #2 : islice from itertools module Another method is to use islice function from itertools module. islice selectively prints the values mentioned in its iterable container. Thus, we yield slices of list2 according to list1 and append it to variable ‘res’. 

[['a'], ['b', 'c'], ['d', 'e', 'f']]

  Method #3 : Python iterator with list comprehension The iter() method returns an iterator for list2 and save it in variable ‘iterator’. Now using list comprehension reshape list2 according to list1. 

[['a'], ['b', 'c'], ['d', 'e', 'f']]

 Method #4 : Using the yield keyword and a for loop:
This approach uses the yield keyword to generate a sequence of sublists, which can then be converted to a list using the list function.

[['a'], ['b', 'c'], ['d', 'e', 'f']]

# Time complexity: O(n), where n is the total number of elements in lst1 and lst2
# Space complexity: O(n), since the function generates a sequence of sublists that may require up to O(n) space to store

Approach#5: Using Slicing

In this approach, we iterate through the given list list1 and for each sub-list lst in it, we create a new sub-list by taking the first len(lst) elements from list2. We do this using slicing and return the list of all the new sub-lists.

Algorithm

1. Create an empty list result.
2. For each sub-list lst in list1, create a new sub-list by taking the first len(lst) elements from list2 using slicing.
3. Append the new sub-list to result.
4. Return result.

[['a'], ['b', 'c'], ['d', 'e', 'f']]

Time Complexity: O(n^2) where n is the length of the longest sub-list in list1. This is because we are using slicing inside the loop, which has a time complexity of O(n).
Space Complexity: O(n) where n is the length of list2. We are using a new list new_lst for each sub-list in list1.

METHOD 6:using defaultdict: The defaultdict approach creates a dictionary of sublists where each sublist corresponds to a sublist in list1. It then iterates over the sublists and their elements in list1, and appends elements from list2 to the corresponding sublist in the dictionary. Finally, it extracts the sublists from the dictionary in the order of list1 to form the final result. 

• Initialize an empty dictionary using defaultdict. The keys of the dictionary will correspond to the indices of the sublists in list1.
• Iterate over the sublists in list1 using a nested loop. For each sublist, iterate over its elements and append the next element from list2 to the corresponding dictionary value.
• Extract the sublists from the dictionary in the order of list1 to obtain the reshaped list.

[['a'], ['b', 'c'], ['d', 'e', 'f']]

Time complexity: O(m * n), where m is the number of sublists in list1 and n is the maximum length of any sublist.

Space complexity: O(m * n), since we need to store the reshaped list in memory.

Using numpy:

Here’s a step-by-step breakdown of the algorithm:

flat_lst1 = np.concatenate(lst1).ravel(): Convert lst1 into a 1D NumPy array (flat_lst1) by concatenating all the sublists in lst1, and flattening the resulting array.

if len(flat_lst1) != len(lst2): raise ValueError(“The total number of elements in lst1 and lst2 do not match.”): Check if the total number of elements in flat_lst1 and lst2 match. If not, raise a ValueError with a message indicating that the total number of elements in lst1 and lst2 do not match.

cum_lengths = np.cumsum([0] + [len(sublst) for sublst in lst1]): Calculate the cumulative lengths of each sublist in lst1. This is done by creating a list of the lengths of each sublist in lst1, and using NumPy’s cumsum() function to calculate the cumulative sums of those lengths. The 0 at the beginning of the list ensures that the cumulative sum starts at 0.

return [lst2[cum_lengths[i]:cum_lengths[i+1]] for i in range(len(lst1))]: Create a list of sublists of lst2, where the i-th sublist contains the elements corresponding to the i-th sublist of lst1. This is done by using a list comprehension to iterate over the indices of lst1 and slicing lst2 using the corresponding start and end indices from cum_lengths.

output: 

[[‘a’], [‘b’, ‘c’], [‘d’, ‘e’, ‘f’]]
 

Time complexity: O(n), where n is the total number of elements in lst1 and lst2.

Auxiliary Space: O(n), since the function generates a new list of sublists that may require up to O(n) space to store.