Python – Reorder for consecutive elements

0 0 3 minutes read

Given a List perform reordering to get similar elements in consecution.

Input : test_list = [4, 7, 5, 4, 1, 4, 1, 6, 7, 5]
Output : [4, 4, 4, 7, 7, 5, 5, 1, 1, 6]
Explanation : All similar elements are assigned to be consecutive.

Input : test_list = [4, 7, 5, 1, 4, 1, 6, 7, 5]
Output : [4, 4, 7, 7, 5, 5, 1, 1, 6]
Explanation : All similar elements are assigned to be consecutive.

Method #1 : Using Counter() + loop + items()

In this, we perform the task of computing frequency using Counter(), and loop and items() are used to reorder elements according to count, and access frequencies respectively.

Python3

# Python3 code to demonstrate working of 
# Reorder for consecutive elements
# Using Counter() + loop + items()
from collections import Counter
 
# initializing list
test_list = [4, 7, 5, 4, 1, 4, 1, 6, 7, 5]
 
# printing original lists
print("The original list is : " + str(test_list))
 
# getting frequency
freqs = Counter(test_list)
res = []
 
# reordering basis of frequency
for val, cnt in freqs.items():
    res.extend([val]*cnt)
 
# printing result 
print("Reordered List : " + str(res))

Output:

The original list is : [4, 7, 5, 4, 1, 4, 1, 6, 7, 5]
Reordered List : [4, 4, 4, 7, 7, 5, 5, 1, 1, 6]

Time Complexity: O(n)
Auxiliary Space: O(n)

Method #2 : Using Counter() + elements()

In this, we perform the task of reordering the counted frequencies using elements(), providing a concise solution.

Python3

# Python3 code to demonstrate working of 
# Reorder for consecutive elements
# Using Counter() + elements()
from collections import Counter
 
# initializing list
test_list = [4, 7, 5, 4, 1, 4, 1, 6, 7, 5]
 
# printing original lists
print("The original list is : " + str(test_list))
 
# reordering using elements()
res = list(Counter(test_list).elements())
 
# printing result 
print("Reordered List : " + str(res))

Output:

The original list is : [4, 7, 5, 4, 1, 4, 1, 6, 7, 5]
Reordered List : [4, 4, 4, 7, 7, 5, 5, 1, 1, 6]

Time Complexity: O(n)
Auxiliary Space: O(n)

Method #3: Using dictionary comprehension + sorted()

Convert the list into a dictionary with keys as elements and values as their frequency using dictionary comprehension.
Use sorted() function to sort the dictionary based on frequency in descending order.
Create an empty list ‘res’ to store the reordered list.
Iterate through the sorted dictionary and append each element to the ‘res’ list as many times as its frequency.
Return the reordered list.

Python3

# Python3 code to demonstrate working of 
# Reorder for consecutive elements
# Using dictionary comprehension + sorted()
 
# initializing list
test_list = [4, 7, 5, 4, 1, 4, 1, 6, 7, 5]
 
# printing original lists
print("The original list is : " + str(test_list))
 
# convert list to dictionary with frequency
freq_dict = {val: test_list.count(val) for val in test_list}
 
# sort dictionary based on frequency in descending order
sorted_dict = dict(sorted(freq_dict.items(), key=lambda item: item[1], reverse=True))
 
# create empty list to store reordered list
res = []
 
# iterate through sorted dictionary and append element to res as many times as its frequency
for key, value in sorted_dict.items():
    res.extend([key] * value)
 
# print result
print("Reordered List : " + str(res))

Output

The original list is : [4, 7, 5, 4, 1, 4, 1, 6, 7, 5]
Reordered List : [4, 4, 4, 7, 7, 5, 5, 1, 1, 6]

Time complexity: O(n log n), where n is the length of the list. This is because of the sorting operation performed on the dictionary.
Auxiliary space: O(n), where n is the length of the list. This is because of the dictionary and list created to store the frequency and reordered list, respectively.