Python | Combinations of elements till size N in list

The problem of finding the combinations of list elements of specific size has been discussed. But sometimes, we require more and we wish to have all the combinations of elements of all sizes till N. Let’s discuss certain ways in which this function can be performed. 

Method #1 : Using list comprehension + combinations() This task can be performed using the list comprehension which can perform the task of varying the combination length and combination() can perform the actual task of finding combinations. 

Time Complexity: O(n!) where n is the number of elements in the list “res_list”.  
Auxiliary Space: O(n!), where n is the number of elements in the new res list 

  Method 2 : Using loop + extend() + combinations() This method is similar to above method, just the loop is being used to iterate for combination size and extend() performs the task of adding the combinations one after another to final result. 

Method#3: Using Recursive method.

Algorithm:

1. Initialize a list “test_list” with some values.
2. Define a function “get_combinations” that takes a list “lst” and an integer “n” as input.
3. If “n” is equal to 0, return a list with an empty list as its only element.
4. Otherwise, for each index “i” from 0 to “len(lst) – n”, create a list “c” that contains “lst[i]” and all the elements in the combinations of “lst[i+1:]” with “n-1” elements.
5. Return a list that contains all the lists “c” obtained in step 4.
6. Create a list comprehension that generates all the combinations of elements of “test_list” with length between 1 and 3,using the “get_combinations” function.
7. Convert each list of combinations to a tuple, and store all the tuples in a list “res”.
8. Print the original list and the list of combinations.

The original list is : [4, 5, 6, 7, 3, 8]
The combinations of elements till length N : [(4,), (5,), (6,), (7,), (3,), (8,), (5, 4), (6, 4), (7, 4), (3, 4), (8, 4), (6, 5), (7, 5), (3, 5), (8, 5), (7, 6), (3, 6), (8, 6), (3, 7), (8, 7), (8, 3), (6, 5, 4), (7, 5, 4), (3, 5, 4), (8, 5, 4), (7, 6, 4), (3, 6, 4), (8, 6, 4), (3, 7, 4), (8, 7, 4), (8, 3, 4), (7, 6, 5), (3, 6, 5), (8, 6, 5), (3, 7, 5), (8, 7, 5), (8, 3, 5), (3, 7, 6), (8, 7, 6), (8, 3, 6), (8, 3, 7)]

Time complexity:

The time complexity of the code is dominated by the time complexity of the “get_combinations” function, which is O(n * 2^n).
The list comprehension that generates all the combinations of elements with length between 1 and 3 has a time complexity of O(n^3), as there are n^3 possible combinations.
The time complexity of converting each list of combinations to a tuple is O(n), where “n” is the length of the list.
The time complexity of storing all the tuples in a list “res” is O(n^3), where “n” is the length of the list “test_list”.
Printing the original list and the list of combinations has a time complexity of O(n), where “n” is the length of the list “test_list”.
Therefore, the overall time complexity of the code is O(n * 2^n + n^3), where “n” is the length of the list “test_list”.

Auxiliary Space:

The space complexity of the code is dominated by the space used to store the list of combinations in the “get_combinations” function.
The space complexity of the “get_combinations” function is O(n * 2^n), as there are 2^n combinations of elements with length n, and for each combination, the function creates a list with n elements.
The space complexity of the list comprehension that generates all the combinations of elements with length between 1 and 3 is O(n^3), as there are n^3 possible combinations.
The space complexity of storing all the tuples in a list “res” is also O(n^3), where “n” is the length of the list “test_list”.
Therefore, the overall space complexity of the code is O(n * 2^n + n^3), where “n” is the length of the list “test_list”.

Method#4: Using heapq:

Algorithm :

1. Initialize the input list.
2. Define a function to get combinations of elements till size N in a list using the heapq module and recursion.
   If N is 0, return a list with an empty list.
3. Otherwise, initialize an empty list, loop over the length of the list, and get combinations of elements by calling the function recursively with the remaining elements.
4. Append the first element of the list to each combination and append the resulting list to the list of combinations.
5. Return the list of combinations.
6. Use a list comprehension to get all combinations of elements till length N, convert them to tuples, and store them in a list.
7. Print the list of combinations.

The original list is : [4, 5, 6, 7, 3, 8]
The combinations of elements till length N : [(4,), (5,), (6,), (7,), (3,), (8,), (4, 5), (4, 6), (4, 7), (4, 3), (4, 8), (5, 6), (5, 7), (5, 3), (5, 8), (6, 7), (6, 3), (6, 8), (7, 3), (7, 8), (3, 8), (4, 5, 6), (4, 5, 7), (4, 5, 3), (4, 5, 8), (4, 6, 7), (4, 6, 3), (4, 6, 8), (4, 7, 3), (4, 7, 8), (4, 3, 8), (5, 6, 7), (5, 6, 3), (5, 6, 8), (5, 7, 3), (5, 7, 8), (5, 3, 8), (6, 7, 3), (6, 7, 8), (6, 3, 8), (7, 3, 8)]

Time Complexity: The time complexity of this code is O(n^k), where n is the length of the input list and k is the maximum length of the combinations. This is because the code generates all possible combinations of the elements in the list till size N using recursion, and the number of such combinations is n^k.

Space Complexity: The space complexity of this code is O(n^k) as well because all the combinations of elements till size N are stored in a list, and the size of this list is n^k. Additionally, the recursion stack also takes up O(n^k) space because the maximum depth of the recursion tree is k.