snippetpythonMinor

Create a generator that returns every permutation (unique arrangement) of positive integers up to n

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

uniquecreateeveryarrangementgeneratorintegersthatreturnspermutationpositive

Problem

I watched this video from The Unqualified Engineer on YouTube and tried out the challenge. The challenge (or interview question) is to build a generator that returns all the permutations of the positive integers up to \$n\$ (that is, \$1,2,3,\ldots,n\$).

I know about itertools.permutations but want to implement it myself.

def gen_perm(n):
    l=tuple(range(1,n+1))
    yield l
    while True:
        l=increment_lex(l)
        if(not l):
            raise StopIteration
            break
        yield l

def increment_lex(l):
    for i in range(len(l)-1):
        x=len(l)-(i+1)
        y=len(l)-(i+2)
        if l[x] > l[y]:
            m=min([i for i in l[x:] if i > l[y]])
            cl=list(l[x:])
            cl[cl.index(m)] = l[y]
            il=tuple(l[:y] + (m,) + tuple(cl[::-1]))
            return il
    return

for i in gen_perm(3):
    print(i)

This outputs:

(1, 2, 3)
(1, 3, 2)
(2, 1, 3)
(2, 3, 1)
(3, 1, 2)
(3, 2, 1)

In order to extend this to the other direction as well, however I couldn't think of a way to do it without adding two additional functions:

def gen_perm_reverse(n):
    l=tuple(range(n,0,-1))
    yield l
    while True:
        l=decrement_lex(l)
        if not l:
            raise StopIteration
            break
        yield l

def decrement_lex(l):
    for i in range(len(l)-1):
        x=len(l)-(i+1)
        y=len(l)-(i+2)
        if l[x] < l[y]:
            m=max([i for i in l[x:] if i < l[y]])
            cl=list(l[x:])
            cl[cl.index(m)] = l[y]
            il=tuple(l[:y] + (m,) + tuple(cl[::-1]))
            return il
    return

Apologies for the use of l as an identifier. It works nicely on my editor font but not here.

Solution

Style

Readability is impaired because you don't use the space bar enough. Put a space around = for assignments, after ,, around binary operators. Parenthesis are also not required in if statements.

You also use 1-letter variable names which doesn't convey any meaning, which makes it harder to understand the code.
Duplicated work

gen_perm and gen_perm_reverse are basically the same function with some minor tweaks: the range and the "increment" function to call. Increments functions are the same too, only the comparison (` and min vs max

) change.

You can merge the two of them and parametrize it with a

reverse parameter that default to False

.

import operator

def permutations(n, reverse=False):
    numbers = range(1, n+1)
    permutation = tuple(reversed(numbers) if reverse else numbers)

    yield permutation
    while True:
        permutation = next_permutation(permutation, reverse)
        if not permutation:
            return
        yield permutation

def next_permutation(permutation, reverse=False):
    compare = operator.lt if reverse else operator.gt
    top = max if reverse else min

    max_length = len(permutation) - 1
    for i in range(max_length):
        x = max_length - i
        permutable = permutation[x - 1]
        if compare(permutation[x], permutable):
            m = top(i for i in permutation[x:] if compare(i, permutable))
            cl = list(permutation[x:])
            cl[cl.index(m)] = permutable
            return permutation[:x-1] + (m,) + tuple(cl[::-1])


A couple of changes here:

Instead of raising StopIteration, you can just return from a generator. In any case, having a break after a raise is poor practice since it is unreachable code.

I computed len(permutation) (len(l)) less time in next_permutation and assigned l[y] to a variable to reduce the cost of retrieving it.

I removed the call to tuple when creating the object to be returned since it already it a tuple.

The last return was also unnecessary as it is implicit anyway.




The drawback of this approach is that you now perform much more comparisons to

reverse

 to be able to get the right comparison functions. You can get rid of it either by passing the functions as parameters or by combining both functions:

import operator

def permutations(n, reverse=False):
    numbers = range(1, n+1)
    compare = operator.lt if reverse else operator.gt
    top = max if reverse else min
    permutation = tuple(reversed(numbers) if reverse else numbers)
    max_length = n - 1

    yield permutation
    while True:
        for i in range(max_length):
            x = max_length - i
            permutable = permutation[x - 1]
            if compare(permutation[x], permutable):
                m = top(i for i in permutation[x:] if compare(i, permutable))
                cl = list(permutation[x:])
                cl[cl.index(m)] = permutable
                permutation = permutation[:x-1] + (m,) + tuple(cl[::-1])
                break
        else:
            # We didn't break -> no more permutations available
            return
        yield permutation


Here I used the

for .. else

 construct to detect when we couldn't produce an new permutation and stop the generation accordingly.
Building on my comment

As I said in a comment, the most straighforward way to achieve that in python is by using

itertools.permutation

:

import itertools

def permutations(n):
    return itertools.permutations(range(1, n+1))


the advantage, beside its simplicity of use, is that the reverse version is straighforward too:

def permutations(n, reverse=False):
    numbers = range(1, n+1)
    return itertools.permutations(reversed(numbers) if reverse else numbers)


But being able to use both the forward and reverse iteration had me thinking about defining a class:

import itertools

class Permutations:
    def __init__(self, n):
        self.numbers = range(1, n+1)

    def __iter__(self):
        return itertools.permutations(self.numbers)

    def __reverse__(self):
        return itertools.permutations(reversed(self.numbers))


Usage being:

perm_3 = Permutations(3)
for i in perm_3:
    print(i)
for i in reversed(perm_3):
    print(i)


The advantage here is that, if you really don't wan't to use

itertools

, you can plug in your custom function easily:

``
import operator

class Permutations:
def __init__(self, n):
self.numbers = range(1, n+1)

@staticmethod
def _permutation_helper(permutation, compare, top):
max_length = len(permutation) - 1

yield permutation
while True:
for i in range(max_length):
x = max_length - i
permutable = permutation[x - 1]
if compare(permutation[x], permutable):
m = top(i for i in permutation[x:] if compare(i, permutable))
cl = list(permutation[x:])
cl[cl.index(m)]

Code Snippets

import operator

def permutations(n, reverse=False):
    numbers = range(1, n+1)
    permutation = tuple(reversed(numbers) if reverse else numbers)

    yield permutation
    while True:
        permutation = next_permutation(permutation, reverse)
        if not permutation:
            return
        yield permutation

def next_permutation(permutation, reverse=False):
    compare = operator.lt if reverse else operator.gt
    top = max if reverse else min

    max_length = len(permutation) - 1
    for i in range(max_length):
        x = max_length - i
        permutable = permutation[x - 1]
        if compare(permutation[x], permutable):
            m = top(i for i in permutation[x:] if compare(i, permutable))
            cl = list(permutation[x:])
            cl[cl.index(m)] = permutable
            return permutation[:x-1] + (m,) + tuple(cl[::-1])

import operator

def permutations(n, reverse=False):
    numbers = range(1, n+1)
    compare = operator.lt if reverse else operator.gt
    top = max if reverse else min
    permutation = tuple(reversed(numbers) if reverse else numbers)
    max_length = n - 1

    yield permutation
    while True:
        for i in range(max_length):
            x = max_length - i
            permutable = permutation[x - 1]
            if compare(permutation[x], permutable):
                m = top(i for i in permutation[x:] if compare(i, permutable))
                cl = list(permutation[x:])
                cl[cl.index(m)] = permutable
                permutation = permutation[:x-1] + (m,) + tuple(cl[::-1])
                break
        else:
            # We didn't break -> no more permutations available
            return
        yield permutation

import itertools

def permutations(n):
    return itertools.permutations(range(1, n+1))

def permutations(n, reverse=False):
    numbers = range(1, n+1)
    return itertools.permutations(reversed(numbers) if reverse else numbers)

import itertools

class Permutations:
    def __init__(self, n):
        self.numbers = range(1, n+1)

    def __iter__(self):
        return itertools.permutations(self.numbers)

    def __reverse__(self):
        return itertools.permutations(reversed(self.numbers))

Context

StackExchange Code Review Q#129804, answer score: 4

Revisions (0)

No revisions yet.