How do I generate all permutations of a list?

Question

How do I generate all the permutations of a list? For example:

permutations([])
[]
permutations([1])
[1]
permutations([1, 2])
[1, 2]
[2, 1]
permutations([1, 2, 3])
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

Answer 1

Use itertools.permutations from the standard library:

import itertools
list(itertools.permutations([1, 2, 3]))

---

A demonstration of how itertools.permutations might be implemented:

def permutations(elements):
 if len(elements) <= 1:
 yield elements
 return
 for perm in permutations(elements[1:]):
 for i in range(len(elements)):
 # nb elements[0:1] works in both string and list contexts
 yield perm[:i] + elements[0:1] + perm[i:]

A couple of alternative approaches are listed in the documentation of itertools.permutations. Here's one:

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 = range(n)
 cycles = 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

And another, based on itertools.product:

def permutations(iterable, r=None):
 pool = tuple(iterable)
 n = len(pool)
 r = n if r is None else r
 for indices in product(range(n), repeat=r):
 if len(set(indices)) == r:
 yield tuple(pool[i] for i in indices)

• Boris Gorelik: This and other recursive solutions have a potential hazard of eating up all the RAM if the permutated list is big enough
• dbr: They also reach the recursion limit (and die) with large lists
• Jagtesh Chadha: bgbg, dbr: Its using a generator, so the function itself won't eat up memory. Its left to you on how to consume the iterator returned by all_perms (say you could write each iteration to disk and not worry about memory). I know this post is old but I'm writing this for the benefit of everyone who reads it now. Also now, the best way would be to use itertools.permutations() as pointed out by many.
• cdunn2001: Not just a generator. It's using nested generators, which each yield to the previous one up the call stack, in case that's not clear. It uses O(n) memory, which is good.
• Eric O. Lebigot: PS: I fixed it, with for i in range(len(elements)) instead of for i in range(len(elements)+1). In fact, the singled-out element elements[0:1] can be in len(elements) different positions, in the result, not len(elements)+1.

Answer 2

For Python 2.6 onwards:

import itertools
itertools.permutations([1, 2, 3])

This returns as a generator. Use list(permutations(xs)) to return as a list.

• toto_tico: Notice that there exists an r parameter, e.g. itertools.permutations([1,2,3], r=2), which will generate all possible permutations selecting 2 elements: [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]

Answer 3

First, import itertools:

import itertools

Permutation (order matters):

print(list(itertools.permutations([1,2,3,4], 2)))
[(1, 2), (1, 3), (1, 4),
(2, 1), (2, 3), (2, 4),
(3, 1), (3, 2), (3, 4),
(4, 1), (4, 2), (4, 3)]

Combination (order does NOT matter):

print(list(itertools.combinations('123', 2)))
[('1', '2'), ('1', '3'), ('2', '3')]

Cartesian product (with several iterables):

print(list(itertools.product([1,2,3], [4,5,6])))
[(1, 4), (1, 5), (1, 6),
(2, 4), (2, 5), (2, 6),
(3, 4), (3, 5), (3, 6)]

Cartesian product (with one iterable and itself):

print(list(itertools.product([1,2], repeat=3)))
[(1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 2, 2),
(2, 1, 1), (2, 1, 2), (2, 2, 1), (2, 2, 2)]

• Pramod: +1! Docs link: docs.python.org/2/library/itertools.html#itertools.permutations

Answer 4

def permutations(head, tail=''):
 if len(head) == 0:
 print(tail)
 else:
 for i in range(len(head)):
 permutations(head[:i] + head[i+1:], tail + head[i])

called as:

permutations('abc')

• bugmenot123: Why print tail and then return None? Why not return tail instead? Why not return anything anyways?
• Alex Moore-Niemi: @bugmenot123 you probably want all of the final tails rather than just tail, this is done easily by adding a perms=[] parameter to the function, appending to it on every print and having a final return perms

Answer 5

#!/usr/bin/env python
def perm(a, k=0):
 if k == len(a):
 print a
 else:
 for i in xrange(k, len(a)):
 a[k], a[i] = a[i] ,a[k]
 perm(a, k+1)
 a[k], a[i] = a[i], a[k]
perm([1,2,3])

Output:

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 2, 1]
[3, 1, 2]

As I'm swapping the content of the list it's required a mutable sequence type as input. E.g. perm(list("ball")) will work and perm("ball") won't because you can't change a string.

This Python implementation is inspired by the algorithm presented in the book Computer Algorithms by Horowitz, Sahni and Rajasekeran.

• Konstantinos Monachopoulos: I assume k is the length or permutations. For k = 2 outputs [1, 2, 3]. Shouldn't it be (1, 2) (1, 3) (2, 1) (2, 3) (3, 1) (3, 2) ??
• sf8193: k is the index of the element you want to swap
• Pathros: NameError: name 'xrange' is not defined
• mLstudent33: 7 years later, how would I return a list of lists of all the permuted lists? Also, can this be done iteratively?
• Aditya: this is done easily by adding a perms=[] parameter to the function, appending to it on every print and having a final return perms

Answer 6

This solution implements a generator, to avoid holding all the permutations on memory:

def permutations (orig_list):
 if not isinstance(orig_list, list):
 orig_list = list(orig_list)
 yield orig_list
 if len(orig_list) == 1:
 return
 for n in sorted(orig_list):
 new_list = orig_list[:]
 pos = new_list.index(n)
 del(new_list[pos])
 new_list.insert(0, n)
 for resto in permutations(new_list[1:]):
 if new_list[:1] + resto <> orig_list:
 yield new_list[:1] + resto

Answer 7

Regular implementation (no yield - will do everything in memory):

def getPermutations(array):
 if len(array) == 1:
 return [array]
 permutations = []
 for i in range(len(array)): 
 # get all perm's of subarray w/o current item
 perms = getPermutations(array[:i] + array[i+1:]) 
 for p in perms:
 permutations.append([array[i], *p])
 return permutations

Yield implementation:

def getPermutations(array):
 if len(array) == 1:
 yield array
 else:
 for i in range(len(array)):
 perms = getPermutations(array[:i] + array[i+1:])
 for p in perms:
 yield [array[i], *p]

The basic idea is to go over all the elements in the array for the 1st position, and then in 2nd position go over all the rest of the elements without the chosen element for the 1st, etc. You can do this with recursion, where the stop criteria is getting to an array of 1 element - in which case you return that array.

enter image description here

• RK1: This does not work for me _> ValueError: operands could not be broadcast together with shapes (0,) (2,) , for this line: perms = getPermutations(array[:i] + array[i+1:])
• Maverick Meerkat: @RK1 what was the input?
• RK1: I'm passing in a numpy array _> getPermutations(np.array([1, 2, 3])), I see it works for a list, just got confused as the func arg is array :)
• Maverick Meerkat: @RK1 glad it works :-) list is a keyword in python, so it's usually not a good idea to call your parameter a keyword, as it will "shadow" it. So I use the word array, as this is the actual functionality of the list that I'm using - their array like manner. I guess if I would write documentation I would clarify it. Also I believe that basic "interview" questions should be solved without external packages, like numpy.
• RK1: Haha that's true, yeah was trying to use it with numba and got greedy with speed so tried to use it exclusively with numpy arrays

Answer 8

In a functional style

def addperm(x,l):
 return [ l[0:i] + [x] + l[i:] for i in range(len(l)+1) ]
def perm(l):
 if len(l) == 0:
 return [[]]
 return [x for y in perm(l[1:]) for x in addperm(l[0],y) ]
print perm([ i for i in range(3)])

The result:

[[0, 1, 2], [1, 0, 2], [1, 2, 0], [0, 2, 1], [2, 0, 1], [2, 1, 0]]

Answer 9

The following code is an in-place permutation of a given list, implemented as a generator. Since it only returns references to the list, the list should not be modified outside the generator. The solution is non-recursive, so uses low memory. Work well also with multiple copies of elements in the input list.

def permute_in_place(a):
 a.sort()
 yield list(a)
 if len(a) <= 1:
 return
 first = 0
 last = len(a)
 while 1:
 i = last - 1
 while 1:
 i = i - 1
 if a[i] < a[i+1]:
 j = last - 1
 while not (a[i] < a[j]):
 j = j - 1
 a[i], a[j] = a[j], a[i] # swap the values
 r = a[i+1:last]
 r.reverse()
 a[i+1:last] = r
 yield list(a)
 break
 if i == first:
 a.reverse()
 return
if __name__ == '__main__':
 for n in range(5):
 for a in permute_in_place(range(1, n+1)):
 print a
 print
 for a in permute_in_place([0, 0, 1, 1, 1]):
 print a
 print

Answer 10

A quite obvious way in my opinion might be also:

def permutList(l):
 if not l:
 return [[]]
 res = []
 for e in l:
 temp = l[:]
 temp.remove(e)
 res.extend([[e] + r for r in permutList(temp)])
 return res

Answer 11

list2Perm = [1, 2.0, 'three']
listPerm = [[a, b, c]
 for a in list2Perm
 for b in list2Perm
 for c in list2Perm
 if ( a != b and b != c and a != c )
 ]
print listPerm

Output:

[
 [1, 2.0, 'three'], 
 [1, 'three', 2.0], 
 [2.0, 1, 'three'], 
 [2.0, 'three', 1], 
 ['three', 1, 2.0], 
 ['three', 2.0, 1]
]

• James: While it technically produces the desired output, you're solving something that could be O(n lg n) in O(n^n) - "slightly" inefficient for large sets.
• Eric O. Lebigot: @James: I am a little confused by the O(n log n) that you give: the number of permutations is n!, which is already much larger than O(n log n); so, I can't see how a solution could be O(n log n). However, it is true that this solution is in O(n^n), which is much larger than n!, as is clear from Stirling's approximation.

Answer 12

I used an algorithm based on the factorial number system- For a list of length n, you can assemble each permutation item by item, selecting from the items left at each stage. You have n choices for the first item, n-1 for the second, and only one for the last, so you can use the digits of a number in the factorial number system as the indices. This way the numbers 0 through n!-1 correspond to all possible permutations in lexicographic order.

from math import factorial
def permutations(l):
 permutations=[]
 length=len(l)
 for x in xrange(factorial(length)):
 available=list(l)
 newPermutation=[]
 for radix in xrange(length, 0, -1):
 placeValue=factorial(radix-1)
 index=x/placeValue
 newPermutation.append(available.pop(index))
 x-=index*placeValue
 permutations.append(newPermutation)
 return permutations
permutations(range(3))

output:

[[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]

This method is non-recursive, but it is slightly slower on my computer and xrange raises an error when n! is too large to be converted to a C long integer (n=13 for me). It was enough when I needed it, but it's no itertools.permutations by a long shot.

• Hannele: Hi, welcome to Stack Overflow. Although posting the brute force method has its merits, if you don't think your solution is better than the accepted solution, you probably shouldn't post it (especially on an old question that already has so many answers).
• Jay Taylor: I was actually looking for a brute-force non-library approach, so thanks!
• user3347814: I found it useful too!

Answer 13

Note that this algorithm has an n factorial time complexity, where n is the length of the input list

Print the results on the run:

global result
result = [] 
def permutation(li):
if li == [] or li == None:
 return
if len(li) == 1:
 result.append(li[0])
 print result
 result.pop()
 return
for i in range(0,len(li)):
 result.append(li[i])
 permutation(li[:i] + li[i+1:])
 result.pop() 

Example:

permutation([1,2,3])

Output:

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

Answer 14

One can indeed iterate over the first element of each permutation, as in tzwenn's answer. It is however more efficient to write this solution this way:

def all_perms(elements):
 if len(elements) <= 1:
 yield elements # Only permutation possible = no permutation
 else:
 # Iteration over the first element in the result permutation:
 for (index, first_elmt) in enumerate(elements):
 other_elmts = elements[:index]+elements[index+1:]
 for permutation in all_perms(other_elmts): 
 yield [first_elmt] + permutation

This solution is about 30 % faster, apparently thanks to the recursion ending at len(elements) <= 1 instead of 0. It is also much more memory-efficient, as it uses a generator function (through yield), like in Riccardo Reyes's solution.

Answer 15

This is inspired by the Haskell implementation using list comprehension:

def permutation(list):
 if len(list) == 0:
 return [[]]
 else:
 return [[x] + ys for x in list for ys in permutation(delete(list, x))]
def delete(list, item):
 lc = list[:]
 lc.remove(item)
 return lc

Answer 16

For performance, a numpy solution inspired by Knuth, (p22) :

from numpy import empty, uint8
from math import factorial
def perms(n):
 f = 1
 p = empty((2*n-1, factorial(n)), uint8)
 for i in range(n):
 p[i, :f] = i
 p[i+1:2*i+1, :f] = p[:i, :f] # constitution de blocs
 for j in range(i):
 p[:i+1, f*(j+1):f*(j+2)] = p[j+1:j+i+2, :f] # copie de blocs
 f = f*(i+1)
 return p[:n, :]

Copying large blocs of memory saves time - it's 20x faster than list(itertools.permutations(range(n)) :

In [1]: %timeit -n10 list(permutations(range(10)))
10 loops, best of 3: 815 ms per loop
In [2]: %timeit -n100 perms(10) 
100 loops, best of 3: 40 ms per loop

Answer 17

If you don't want to use the builtin methods such as:

import itertools
list(itertools.permutations([1, 2, 3]))

you can implement permute function yourself

from collections.abc import Iterable
def permute(iterable: Iterable[str]) -> set[str]:
 perms = set()
 if len(iterable) == 1:
 return {*iterable}
 for index, char in enumerate(iterable):
 perms.update([char + perm for perm in permute(iterable[:index] + iterable[index + 1:])])
 return perms
if __name__ == '__main__':
 print(permute('abc'))
 # {'bca', 'abc', 'cab', 'acb', 'cba', 'bac'}
 print(permute(['1', '2', '3']))
 # {'123', '312', '132', '321', '213', '231'}

Answer 18

Disclaimer: shameless plug by package author. :)

The trotter package is different from most implementations in that it generates pseudo lists that don't actually contain permutations but rather describe mappings between permutations and respective positions in an ordering, making it possible to work with very large 'lists' of permutations, as shown in this demo which performs pretty instantaneous operations and look-ups in a pseudo-list 'containing' all the permutations of the letters in the alphabet, without using more memory or processing than a typical web page.

In any case, to generate a list of permutations, we can do the following.

import trotter
my_permutations = trotter.Permutations(3, [1, 2, 3])
print(my_permutations)
for p in my_permutations:
 print(p)

Output:

A pseudo-list containing 6 3-permutations of [1, 2, 3].
[1, 2, 3]
[1, 3, 2]
[3, 1, 2]
[3, 2, 1]
[2, 3, 1]
[2, 1, 3]

• ecdani: Your package have a limit between 400 - 500 elements.
• Richard Ambler: @ecdani Thanks for your interest in this library! If each atom in the Milky Way galaxy spontaneously turned into a new Milky Way galaxy, and each of the new atoms did that again, we still wouldn't have as many atoms as there are permutations of 500 elements. Having said that, if you up your system's maximum recursion level a bit, the library can easily represent permutations of 1,000 or more elements, and searching and lookup are still pretty instantaneous. If you like, post an issue at the trotter repository page.

Answer 19

The beauty of recursion:

>>> import copy
>>> def perm(prefix,rest):
... for e in rest:
... new_rest=copy.copy(rest)
... new_prefix=copy.copy(prefix)
... new_prefix.append(e)
... new_rest.remove(e)
... if len(new_rest) == 0:
... print new_prefix + new_rest
... continue
... perm(new_prefix,new_rest)
... 
>>> perm([],['a','b','c','d'])
['a', 'b', 'c', 'd']
['a', 'b', 'd', 'c']
['a', 'c', 'b', 'd']
['a', 'c', 'd', 'b']
['a', 'd', 'b', 'c']
['a', 'd', 'c', 'b']
['b', 'a', 'c', 'd']
['b', 'a', 'd', 'c']
['b', 'c', 'a', 'd']
['b', 'c', 'd', 'a']
['b', 'd', 'a', 'c']
['b', 'd', 'c', 'a']
['c', 'a', 'b', 'd']
['c', 'a', 'd', 'b']
['c', 'b', 'a', 'd']
['c', 'b', 'd', 'a']
['c', 'd', 'a', 'b']
['c', 'd', 'b', 'a']
['d', 'a', 'b', 'c']
['d', 'a', 'c', 'b']
['d', 'b', 'a', 'c']
['d', 'b', 'c', 'a']
['d', 'c', 'a', 'b']
['d', 'c', 'b', 'a']

Answer 20

ANOTHER APPROACH (without libs)

def permutation(input):
 if len(input) == 1:
 return input if isinstance(input, list) else [input]
 result = []
 for i in range(len(input)):
 first = input[i]
 rest = input[:i] + input[i + 1:]
 rest_permutation = permutation(rest)
 for p in rest_permutation:
 result.append(first + p)
 return result

Input can be a string or a list

print(permutation('abcd'))
print(permutation(['a', 'b', 'c', 'd']))

• RK1: This does not work for a list with integers, eg. [1, 2, 3] returns [6, 6, 6, 6, 6, 6]
• Tatsu: @RK1, u can try this print(permutation(['1','2','3']))

Answer 21

from __future__ import print_function
def perm(n):
 p = []
 for i in range(0,n+1):
 p.append(i)
 while True:
 for i in range(1,n+1):
 print(p[i], end=' ')
 print("")
 i = n - 1
 found = 0
 while (not found and i>0):
 if p[i]<p[i+1]:
 found = 1
 else:
 i = i - 1
 k = n
 while p[i]>p[k]:
 k = k - 1
 aux = p[i]
 p[i] = p[k]
 p[k] = aux
 for j in range(1,(n-i)/2+1):
 aux = p[i+j]
 p[i+j] = p[n-j+1]
 p[n-j+1] = aux
 if not found:
 break
perm(5)

Answer 22

Here is an algorithm that works on a list without creating new intermediate lists similar to Ber's solution at https://stackoverflow.com/a/108651/184528.

def permute(xs, low=0):
 if low + 1 >= len(xs):
 yield xs
 else:
 for p in permute(xs, low + 1):
 yield p 
 for i in range(low + 1, len(xs)): 
 xs[low], xs[i] = xs[i], xs[low]
 for p in permute(xs, low + 1):
 yield p 
 xs[low], xs[i] = xs[i], xs[low]
for p in permute([1, 2, 3, 4]):
 print p

You can try the code out for yourself here: http://repl.it/J9v

Answer 23

This algorithm is the most effective one, it avoids of array passing and manipulation in recursive calls, works in Python 2, 3:

def permute(items):
 length = len(items)
 def inner(ix=[]):
 do_yield = len(ix) == length - 1
 for i in range(0, length):
 if i in ix: #avoid duplicates
 continue
 if do_yield:
 yield tuple([items[y] for y in ix + [i]])
 else:
 for p in inner(ix + [i]):
 yield p
 return inner()

Usage:

for p in permute((1,2,3)):
 print(p)
(1, 2, 3)
(1, 3, 2)
(2, 1, 3)
(2, 3, 1)
(3, 1, 2)
(3, 2, 1)

Answer 24

def pzip(c, seq):
 result = []
 for item in seq:
 for i in range(len(item)+1):
 result.append(item[i:]+c+item[:i])
 return result
def perm(line):
 seq = [c for c in line]
 if len(seq) <=1 :
 return seq
 else:
 return pzip(seq[0], perm(seq[1:]))

Answer 25

Generate all possible permutations

I'm using python3.4:

def calcperm(arr, size):
 result = set([()])
 for dummy_idx in range(size):
 temp = set()
 for dummy_lst in result:
 for dummy_outcome in arr:
 if dummy_outcome not in dummy_lst:
 new_seq = list(dummy_lst)
 new_seq.append(dummy_outcome)
 temp.add(tuple(new_seq))
 result = temp
 return result

Test Cases:

lst = [1, 2, 3, 4]
#lst = ["yellow", "magenta", "white", "blue"]
seq = 2
final = calcperm(lst, seq)
print(len(final))
print(final)

• SeaDude: This (so far) is the most understandable solution for me (non-math head). I can list chars I want to permutate and this works! What is the logic to add duplicates characters to permutations? Example: def calcperm(arr, size, dupes): where dupes are the allowed numbers of duplicates to allow for each permutation.

Answer 26

I see a lot of iteration going on inside these recursive functions, not exactly pure recursion...

so for those of you who cannot abide by even a single loop, here's a gross, totally unnecessary fully recursive solution

def all_insert(x, e, i=0):
 return [x[0:i]+[e]+x[i:]] + all_insert(x,e,i+1) if i<len(x)+1 else []
def for_each(X, e):
 return all_insert(X[0], e) + for_each(X[1:],e) if X else []
def permute(x):
 return [x] if len(x) < 2 else for_each( permute(x[1:]) , x[0])
perms = permute([1,2,3])

Answer 27

To save you folks possible hours of searching and experimenting, here's the non-recursive permutaions solution in Python which also works with Numba (as of v. 0.41):

@numba.njit()
def permutations(A, k):
 r = [[i for i in range(0)]]
 for i in range(k):
 r = [[a] + b for a in A for b in r if (a in b)==False]
 return r
permutations([1,2,3],3)
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

To give an impression about performance:

%timeit permutations(np.arange(5),5)
243 μs ± 11.1 μs per loop (mean ± std. dev. of 7 runs, 1 loop each)
time: 406 ms
%timeit list(itertools.permutations(np.arange(5),5))
15.9 μs ± 8.61 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
time: 12.9 s

So use this version only if you have to call it from njitted function, otherwise prefer itertools implementation.

Answer 28

Anyway we could use sympy library , also support for multiset permutations

import sympy
from sympy.utilities.iterables import multiset_permutations
t = [1,2,3]
p = list(multiset_permutations(t))
print(p)
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Answer is highly inspired by Get all permutations of a numpy array

Answer 29

Another solution:

def permutation(flag, k =1 ):
 N = len(flag)
 for i in xrange(0, N):
 if flag[i] != 0:
 continue
 flag[i] = k 
 if k == N:
 print flag
 permutation(flag, k+1)
 flag[i] = 0
permutation([0, 0, 0])

• Pathros: NameError: name 'xrange' is not defined
• anhldbk: @Pathros well, the code above is for Python 2. For Python 3, please use range(). See stackoverflow.com/questions/17192158/…

Answer 30

This is the asymptotically optimal way O(n*n!) of generating permutations after initial sorting.

There are n! permutations at most and hasNextPermutation(..) runs in O(n) time complexity

In 3 steps,

1. Find largest j such that a[j] can be increased
2. Increase a[j] by smallest feasible amount
3. Find lexicogrpahically least way to extend the new a[0..j]

'''
Lexicographic permutation generation
consider example array state of [1,5,6,4,3,2] for sorted [1,2,3,4,5,6]
after 56432(treat as number) ->nothing larger than 6432(using 6,4,3,2) beginning with 5
so 6 is next larger and 2345(least using numbers other than 6)
so [1, 6,2,3,4,5]
'''
def hasNextPermutation(array, len):
 ' Base Condition '
 if(len ==1):
 return False
 '''
 Set j = last-2 and find first j such that a[j] < a[j+1]
 If no such j(j==-1) then we have visited all permutations
 after this step a[j+1]>=..>=a[len-1] and a[j]<a[j+1]
 a[j]=5 or j=1, 6>5>4>3>2
 '''
 j = len -2
 while (j >= 0 and array[j] >= array[j + 1]):
 j= j-1
 if(j==-1):
 return False
 # print(f"After step 2 for j {j} {array}")
 '''
 decrease l (from n-1 to j) repeatedly until a[j]<a[l]
 Then swap a[j], a[l]
 a[l] is the smallest element > a[j] that can follow a[l]...a[j-1] in permutation
 before swap we have a[j+1]>=..>=a[l-1]>=a[l]>a[j]>=a[l+1]>=..>=a[len-1]
 after swap -> a[j+1]>=..>=a[l-1]>=a[j]>a[l]>=a[l+1]>=..>=a[len-1]
 a[l]=6 or l=2, j=1 just before swap [1, 5, 6, 4, 3, 2] 
 after swap [1, 6, 5, 4, 3, 2] a[l]=5, a[j]=6
 '''
 l = len -1
 while(array[j] >= array[l]):
 l = l-1
 # print(f"After step 3 for l={l}, j={j} before swap {array}")
 array[j], array[l] = array[l], array[j]
 # print(f"After step 3 for l={l} j={j} after swap {array}")
 '''
 Reverse a[j+1...len-1](both inclusive)
 after reversing [1, 6, 2, 3, 4, 5]
 '''
 array[j+1:len] = reversed(array[j+1:len])
 # print(f"After step 4 reversing {array}")
 return True
array = [1,2,4,4,5]
array.sort()
len = len(array)
count =1
print(array)
'''
The algorithm visits every permutation in lexicographic order
generating one by one
'''
while(hasNextPermutation(array, len)):
 print(array)
 count = count +1
# The number of permutations will be n! if no duplicates are present, else less than that
# [1,4,3,3,2] -> 5!/2!=60
print(f"Number of permutations: {count}")

• Chris: Welcome to Stack Overflow. Code dumps without any explanation are rarely helpful. Stack Overflow is about learning, not providing snippets to blindly copy and paste. Please edit your question and explain how it answers the specific question being asked. See How to Answer. This is especially important when answering old questions (this one is over 12 old) with existing answers (this one has 40). How does this answer improve upon what's already here? Note also that the question is about Python. How does an answer in Java help?