Python permutations generator using generators

Last update on December 21 2024 07:30:15 (UTC/GMT +8 hours)

Write a Python program to implement a generator function that generates all permutations of a given list of elements.

In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or process of changing the linear order of an ordered set. Permutations differ from combinations, which are selections of some members of a set regardless of order. For example, written as tuples, there are six permutations of the set {1, 2, 3}, namely (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), and (3, 2, 1).

Visual Presentation:

Sample Solution:

Python Code:

def list_permutations(elements):
    if len(elements) <= 1:
        yield elements
    else:
        for p in list_permutations(elements[1:]):
            for i in range(len(elements)):
                yield p[:i] + elements[0:1] + p[i:]

# Accept input from the user
# nums = [1,2] 
# nums = [1,2,3]
nums = [1,2,3,4]
print("Original list of elements:",nums)

# Generate and print all permutations
print("All permutations:")
for p in list_permutations(nums):
    print(p)

Sample Output:

Original list of elements: [1, 2]
All permutations:
[1, 2]
[2, 1]

Original list of elements: [1, 2, 3]
All permutations:
[1, 2, 3]
[2, 1, 3]
[2, 3, 1]
[1, 3, 2]
[3, 1, 2]
[3, 2, 1]

Original list of elements: [1, 2, 3, 4]
All permutations:
[1, 2, 3, 4]
[2, 1, 3, 4]
[2, 3, 1, 4]
[2, 3, 4, 1]
[1, 3, 2, 4]
[3, 1, 2, 4]
[3, 2, 1, 4]
[3, 2, 4, 1]
[1, 3, 4, 2]
[3, 1, 4, 2]
[3, 4, 1, 2]
[3, 4, 2, 1]
[1, 2, 4, 3]
[2, 1, 4, 3]
[2, 4, 1, 3]
[2, 4, 3, 1]
[1, 4, 2, 3]
[4, 1, 2, 3]
[4, 2, 1, 3]
[4, 2, 3, 1]
[1, 4, 3, 2]
[4, 1, 3, 2]
[4, 3, 1, 2]
[4, 3, 2, 1]

Explanation:

In the above exercise,

• The "list_permutations()" function is defined as a generator function that takes a list of elements as input.
• The base case is checked using the condition if len(elements) <= 1. If the list length is less than or equal to 1, it means there is only one element or no elements, so the function yields the list itself.
• In the recursive case, the function iterates over all permutations of the sublist elements[1:] by calling list_permutations() recursively.
• For each permutation "p" in the recursive call, the function iterates over the indices of the original list using range(len(elements)).
• Within the inner loop, the function yields the permutation by combining the element at index i of the original list (elements[0:1]) with the remaining elements of the permutation (p[:i] + p[i+1:]).
• The outer loop continues generating permutations by yielding all possible combinations of the element at index i with the remaining elements.

Flowchart:

Python Code Editor:

Contribute your code and comments through Disqus.

Previous: Python Fibonacci generator using generators.
Next: Python combinations generator using generators.