Replicating itertools Combinations and Permutations

This challenge focuses on understanding and reimplementing core functionalities found in Python's itertools module, specifically combinations and permutations. By building these functions from scratch, you'll gain a deeper appreciation for how these powerful tools generate sequences and explore the underlying recursive or iterative logic.

Problem Description

Your task is to implement two Python functions: custom_combinations and custom_permutations. These functions should mimic the behavior of itertools.combinations and itertools.permutations respectively.

custom_combinations(iterable, r): This function should return an iterator that yields tuples of length r from the elements of the iterable. The order of elements within each tuple does not matter, and elements are treated as unique based on their position, not their value. If the same element appears multiple times in the input iterable, it should be treated as distinct occurrences.

custom_permutations(iterable, r=None): This function should return an iterator that yields tuples of length r from the elements of the iterable. The order of elements within each tuple does matter. If r is not specified (i.e., r is None), it defaults to the length of the iterable, meaning all possible permutations of the entire iterable will be generated. Similar to combinations, elements are treated as unique based on their position.

Key Requirements:

• Both functions must return iterators, not lists.
• The order of elements within the input iterable should be preserved in the output tuples, as much as the nature of combinations/permutations allows.
• Handle duplicate elements in the input iterable correctly – treat them as distinct items.

Expected Behavior:

• custom_combinations should generate combinations in lexicographical order based on the input iterable.
• custom_permutations should generate permutations in lexicographical order.

Edge Cases:

• Empty iterable.
• r is 0.
• r is greater than the length of the iterable.
• iterable with duplicate elements.

Examples

Example 1: custom_combinations

Input:
iterable = [1, 2, 3]
r = 2

Output:
(1, 2)
(1, 3)
(2, 3)

Explanation:
These are all possible unique pairs of elements from [1, 2, 3] where the order within the pair doesn't matter.

Example 2: custom_permutations

Input:
iterable = ['a', 'b']
r = 2

Output:
('a', 'b')
('b', 'a')

Explanation:
These are all possible ordered arrangements of length 2 from ['a', 'b'].

Example 3: custom_permutations with r=None

Input:
iterable = [1, 2]
r = None

Output:
(1, 2)
(2, 1)

Explanation:
When r is None, it defaults to the length of the iterable, producing all permutations of the entire iterable.

Example 4: custom_combinations with duplicates

Input:
iterable = [1, 1, 2]
r = 2

Output:
(1, 1)  # The first '1' and the second '1'
(1, 2)  # The first '1' and '2'
(1, 2)  # The second '1' and '2'

Explanation:
Duplicates are treated as distinct. The first (1,1) is from the two '1's. The two (1,2) are from picking one of the '1's and the '2'.

Constraints

• The input iterable will be an iterable (list, tuple, string).
• r will be a non-negative integer or None.
• The length of the iterable will be between 0 and 100 inclusive.
• r will be between 0 and the length of the iterable (or None) inclusive.
• Efficiency is important. Avoid generating intermediate lists that are much larger than necessary. The generated output should be an iterator.

Notes

• Consider using recursion or an iterative approach with careful state management.
• Think about how to handle the indices of elements in the iterable to ensure correct ordering and handling of duplicates.
• You are not allowed to import itertools for the implementation of custom_combinations and custom_permutations. You can use itertools for testing your implementations.
• For permutations, you might find it helpful to first implement a function to generate permutations of the entire list and then adapt it for a specific r.