Python combination without itertools

You can generate combinations of elements in a list without using the itertools module by implementing a recursive function. Here’s an example of how to do it:

def generate_combinations(arr, r):
    def backtrack(remaining, current_combination, start_index):
        if len(current_combination) == r:
            combinations.append(tuple(current_combination))
            return
        for i in range(start_index, len(remaining)):
            current_combination.append(remaining[i])
            backtrack(remaining, current_combination, i + 1)
            current_combination.pop()

    combinations = []
    backtrack(arr, [], 0)
    return combinations

# Example usage:
my_list = [1, 2, 3, 4]
r = 2  # Size of combinations

combinations = generate_combinations(my_list, r)
for combo in combinations:
    print(combo)

In this code:

1. generate_combinations is a function that takes a list arr and an integer r as arguments and returns a list of tuples representing all combinations of r elements from arr.
2. Inside generate_combinations, the backtrack function is defined as a nested function. It is a recursive function that generates combinations.
3. The backtrack function takes three arguments: remaining, current_combination, and start_index.
4. The remaining parameter represents the elements that are yet to be considered for inclusion in the current combination.
5. The current_combination parameter is a list that stores the elements currently being considered for the combination.
6. The start_index parameter keeps track of where to start considering elements from the remaining list.
7. Inside the backtrack function, we check if the size of the current_combination is equal to r. If so, we have a valid combination, and we append it to the combinations list.
8. We then iterate through the elements in the remaining list, adding each element to the current_combination and recursively calling backtrack with the updated parameters.
9. After each recursive call, we remove the last element from the current_combination to backtrack and consider other combinations.
10. Finally, we call generate_combinations with the input list and size r to generate the combinations and return them as a list of tuples.

This approach allows you to generate combinations without using the itertools module by implementing a recursive algorithm.