How do i create a permutation on Python without using the itertools module nor recursive programming?

Question

I need to create a function without the use of itertools which will create a permutation list of tuples with a given set of anything.

Example:

perm({1,2,3}, 2) should return [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]

This is what i got:

def permutacion(conjunto, k):
    a, b = list(), list()
    for i in conjunto:
        if len(b) < k and i not in b:
            b.append(i)

    b = tuple(b)
    a.append(b)
    return a

I know this doesn't do anything, it will add the first combination and nothing else.

You can see permutations equivalent python code on the itertools doc page. — John
– John, Commented Apr 27, 2014 at 2:44
Check out permutations at rosettacode.org. Granted, for python, it uses itertools, but for low-level languages, it gives the algorithm that you could easily port to python. — mtadd
– mtadd, Commented Apr 27, 2014 at 2:52

rushilwiz · Accepted Answer · 2020-09-13 17:53:34Z

As mentioned by @John in the comments, the code for itertools.permutations is:

def permutations(iterable, r=None):
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = list(range(n))
    cycles = list(range(n, n-r, -1))
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return

Which works with your example using no external imports or recursive calls:

for x in permutations([1,2,3],2):
    print (x)

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

Escribblings · Accepted Answer · 2019-04-16 21:37:39Z

I have an issue with @Hooked's answer...

Firstly I am a complete novice where py is concerned, but I was looking for something like the above code. I'm currently entering it over at Repl.it

My first issue was the argument

for x in permutations([1,2,3],2):
    print x

which returned the following error

line 26
    print x
          ^
SyntaxError: Missing parentheses in call to 'print'

I fixed this like so

for x in permutations([1,2,3],2):
    print (x)

But now got the error:

line 25, in <module>
    for x in permutations([1,2,3],2):
  File "main.py", line 14, in permutations
    cycles[i] -= 1
TypeError: 'range' object does not support item assignment

Now at this point I have no idea where to go to debug the code. However, I have seen many people point to itertools as having the code in it's documentation. I copied that and it works. This is the code:

def permutations(iterable, r=None):
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = list(range(n))
    cycles = list(range(n, n-r, -1))
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return

It seems that @Hooked's answer is based on Python 2 and yours based on python 3.

Collectives™ on Stack Overflow

How do i create a permutation on Python without using the itertools module nor recursive programming?

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related