Как сгенерировать все перестановки в списке?

Это решение реализует генератор, чтобы избежать хранения всех перестановок в памяти:

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

Для этого есть функция в стандартная библиотека: itertools.permutations.

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

Если по какой-то причине вы хотите реализовать это самостоятельно или просто хотите узнать, как это работает, вот один хороший подход, взятый из http://code.activestate.com/recipes/252178/:

def all_perms(elements):
    if len(elements) <=1:
        yield elements
    else:
        for perm in all_perms(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:]

Несколько альтернативных подходов перечислены в документации itertools.permutations. Вот один из них:

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

И еще один, основанный на 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)

И в Python 2.6 и далее:

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

(возвращается как генератор. Используйте list(permutations(l)) для возврата в виде списка.)

Следующий код представляет собой перестановку заданного списка на месте, реализованную как генератор. Поскольку он возвращает только ссылки на список, список не следует изменять вне генератора. Решение нерекурсивное, поэтому использует мало памяти. Также хорошо работать с несколькими копиями элементов в списке ввода.

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

Следующий код ТОЛЬКО с Python 2.6 и выше

Сначала импортируйте itertools:

import itertools

Перестановка (порядок имеет значение):

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)]

Комбинация (порядок НЕ имеет значения):

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

Декартово произведение (с несколькими итерациями):

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)]

Декартово произведение (с одним итератором и самим собой):

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)]

На мой взгляд, вполне очевидный способ:

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

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

Выход:

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

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])

называется как:

permutations('abc')

Действительно, можно перебирать первый элемент каждой перестановки, как в ответе цвенна. Однако более эффективно написать это решение следующим образом:

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

Это решение примерно на 30% быстрее, по-видимому, благодаря рекурсии, заканчивающейся на len(elements) <= 1 вместо 0. Он также намного более эффективен с точки зрения памяти, поскольку использует функцию генератора (через yield), как в решении Риккардо Рейеса.

#!/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])

Выход:

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

Поскольку я меняю местами содержимое списка, в качестве входных данных требуется изменяемый тип последовательности. Например. perm(list("ball")) будет работать, а perm("ball") - нет, потому что вы не можете изменить строку.

Эта реализация Python основана на алгоритме, представленном в книге Компьютерные алгоритмы Горовица, Сахни и Раджасекерана.

Обратите внимание, что этот алгоритм имеет временную сложность n factorial, где n - длина входного списка.

Распечатайте результаты на ходу:

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()    

Пример:

permutation([1,2,3])

Выход:

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

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)

В функциональном стиле

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)])

Результат:

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

Вот алгоритм, который работает со списком без создания новых промежуточных списков, аналогично решению Бер на 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

Вы можете попробовать этот код здесь: http://repl.it/J9v

Я использовал алгоритм, основанный на факториальная система счисления. Для списка длины n вы можете собрать каждый элемент перестановки за элементом, выбирая из элементов, оставшихся на каждом этапе. У вас есть n вариантов для первого элемента, n-1 для второго и только один для последнего, поэтому вы можете использовать цифры числа в факториальной системе счисления в качестве индексов. Таким образом, числа от 0 до n! -1 соответствуют всем возможным перестановкам в лексикографическом порядке.

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))

выход:

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

Этот метод нерекурсивен, но на моем компьютере он немного медленнее, и xrange выдает ошибку, когда n! слишком велик для преобразования в длинное целое число C (для меня n = 13). Этого было достаточно, когда мне это было нужно, но это далеко не перестановки itertools.

Это вдохновлено реализацией Haskell, использующей понимание списков:

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

Красота рекурсии:

>>> 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']

Этот алгоритм является наиболее эффективным, он избегает передачи массивов и манипуляций при рекурсивных вызовах, работает в 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()

Использование:

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)

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:]))

Что касается производительности, то решение numpy, вдохновленное Knuth, (стр. 22):

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, :]

Копирование больших блоков памяти экономит время - это в 20 раз быстрее, чем 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

для Python мы можем использовать itertools и импортировать как перестановки, так и комбинации, чтобы решить вашу проблему

from itertools import product, permutations
A = ([1,2,3])
print (list(permutations(sorted(A),2)))

Сгенерируйте все возможные перестановки

Я использую 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

Тестовые случаи:

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

Я вижу, что внутри этих рекурсивных функций происходит итерация много, а не совсем рекурсия чистый ...

поэтому для тех из вас, кто не может соблюдать даже один цикл, вот грубое, совершенно ненужное полностью рекурсивное решение

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])

Другое решение:

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])

Мое решение Python:

def permutes(input,offset):
    if ( len(input) == offset ):
        return [''.join(input)]

    result=[]        
    for i in range( offset, len(input) ):
         input[offset], input[i] = input[i], input[offset]
         result = result + permutes(input,offset+1)
         input[offset], input[i] = input[i], input[offset]
    return result

# input is a "string"
# return value is a list of strings
def permutations(input):
    return permutes( list(input), 0 )

# Main Program
print( permutations("wxyz") )

def permutation(word, first_char=None):
    if word == None or len(word) == 0: return []
    if len(word) == 1: return [word]

    result = []
    first_char = word[0]
    for sub_word in permutation(word[1:], first_char):
        result += insert(first_char, sub_word)
    return sorted(result)

def insert(ch, sub_word):
    arr = [ch + sub_word]
    for i in range(len(sub_word)):
        arr.append(sub_word[i:] + ch + sub_word[:i])
    return arr


assert permutation(None) == []
assert permutation('') == []
assert permutation('1')  == ['1']
assert permutation('12') == ['12', '21']

print permutation('abc')

Вывод: ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

Чтобы сэкономить вам часы поиска и экспериментов, вот решение для нерекурсивных перестановок в Python, которое также работает с Numba (начиная с версии 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]]

Чтобы составить впечатление о производительности:

%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

Поэтому используйте эту версию только в том случае, если вам нужно вызвать ее из функции njitted, иначе предпочтите реализацию itertools.

Использование Counter

from collections import Counter

def permutations(nums):
    ans = [[]]
    cache = Counter(nums)

    for idx, x in enumerate(nums):
        result = []
        for items in ans:
            cache1 = Counter(items)
            for id, n in enumerate(nums):
                if cache[n] != cache1[n] and items + [n] not in result:
                    result.append(items + [n])

        ans = result
    return ans
permutations([1, 2, 2])
> [[1, 2, 2], [2, 1, 2], [2, 2, 1]]

ДРУГОЙ ПОДХОД (без библиотек)

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

Вход может быть строкой или списком

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

Отказ от ответственности: бесформенный плагин от автора пакета. :)

Пакет рысак отличается от большинства реализаций тем, что он генерирует псевдосписки, которые на самом деле не содержат перестановок, а скорее описывают сопоставления между перестановками и соответствующими позициями в упорядочении, что позволяет работать с очень большими «списками» перестановок, как показано в эта демонстрация, который выполняет довольно мгновенные операции и поиск в псевдосписке, «содержащем» все перестановки букв в алфавите, без использования большего объема памяти или обработки, чем типичная веб-страница.

В любом случае, чтобы сгенерировать список перестановок, мы можем сделать следующее.

import trotter

my_permutations = trotter.Permutations(3, [1, 2, 3])

print(my_permutations)

for p in my_permutations:
    print(p)

Выход:

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]

Штатная реализация (без выхода - все сделаю в памяти):

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

Реализация доходности:

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]

Основная идея состоит в том, чтобы перебрать все элементы в массиве для 1-й позиции, а затем во 2-й позиции перебрать все остальные элементы без выбранного элемента для 1-й позиции и т. д. Вы можете сделать это с помощью рекурсия, где критерий остановки - получение массива из 1 элемента - и в этом случае вы возвращаете этот массив.

def permuteArray (arr):

    arraySize = len(arr)

    permutedList = []

    if arraySize == 1:
        return [arr]

    i = 0

    for item in arr:

        for elem in permuteArray(arr[:i] + arr[i + 1:]):
            permutedList.append([item] + elem)

        i = i + 1    

    return permutedList

Я намеревался не исчерпать все возможности новой линейки, чтобы сделать ее в некоторой степени уникальной.

В любом случае мы могли бы использовать библиотеку симпатичный, а также поддержку перестановок мультимножества

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]]

Ответ очень вдохновлен Получить все перестановки массива numpy

from typing import List
import time, random

def measure_time(func):
    def wrapper_time(*args, **kwargs):
        start_time = time.perf_counter()
        res = func(*args, **kwargs)
        end_time = time.perf_counter()
        return res, end_time - start_time

    return wrapper_time


class Solution:
    def permute(self, nums: List[int], method: int = 1) -> List[List[int]]:
        perms = []
        perm = []
        if method == 1:
            _, time_perm = self._permute_recur(nums, 0, len(nums) - 1, perms)
        elif method == 2:
            _, time_perm = self._permute_recur_agian(nums, perm, perms)
            print(perm)
        return perms, time_perm

    @measure_time
    def _permute_recur(self, nums: List[int], l: int, r: int, perms: List[List[int]]):
        # base case
        if l == r:
            perms.append(nums.copy())

        for i in range(l, r + 1):
            nums[l], nums[i] = nums[i], nums[l]
            self._permute_recur(nums, l + 1, r , perms)
            nums[l], nums[i] = nums[i], nums[l]

    @measure_time
    def _permute_recur_agian(self, nums: List[int], perm: List[int], perms_list: List[List[int]]):
        """
        The idea is similar to nestedForLoops visualized as a recursion tree.
        """
        if nums:
            for i in range(len(nums)):
                # perm.append(nums[i])  mistake, perm will be filled with all nums's elements.
                # Method1 perm_copy = copy.deepcopy(perm)
                # Method2 add in the parameter list using + (not in place)
                # caveat: list.append is in-place , which is useful for operating on global element perms_list
                # Note that:
                # perms_list pass by reference. shallow copy
                # perm + [nums[i]] pass by value instead of reference.
                self._permute_recur_agian(nums[:i] + nums[i+1:], perm + [nums[i]], perms_list)
        else:
            # Arrive at the last loop, i.e. leaf of the recursion tree.
            perms_list.append(perm)



if __name__ == "__main__":
    array = [random.randint(-10, 10) for _ in range(3)]
    sol = Solution()
    # perms, time_perm = sol.permute(array, 1)
    perms2, time_perm2 = sol.permute(array, 2)
    print(perms2)
    # print(perms, perms2)
    # print(time_perm, time_perm2)
```

на случай, если кому-то понравится этот уродливый однострочник (хотя работает только для строк):

def p(a):
    return a if len(a) == 1 else [[a[i], *j] for i in range(len(a)) for j in p(a[:i] + a[i + 1:])]

import java.util.Arrays;

public class Permutation {

    /* runtime -O(n) for generating nextPermutaion
     * and O(n*n!) for generating all n! permutations with increasing sorted array as start
     * return true, if there exists next lexicographical sequence
     * e.g [1,2,3],3-> true, modifies array to [1,3,2]
     * e.g [3,2,1],3-> false, as it is largest lexicographic possible */
    public static boolean nextPermutation(int[] seq, int len) {
        // 1
        if (len <= 1)
            return false;// no more perm
        // 2: Find last j such that seq[j] <= seq[j+1]. Terminate if no such j exists
        int j = len - 2;
        while (j >= 0 && seq[j] >= seq[j + 1]) {
            --j;
        }
        if (j == -1)
            return false;// no more perm
        // 3: Find last l such that seq[j] <= seq[l], then exchange elements j and l
        int l = len - 1;
        while (seq[j] >= seq[l]) {
            --l;
        }
        swap(seq, j, l);
        // 4: Reverse elements j+1 ... count-1:
        reverseSubArray(seq, j + 1, len - 1);
        // return seq, add store next perm

        return true;
    }
    private static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    private static void reverseSubArray(int[] a, int lo, int hi) {
        while (lo < hi) {
            swap(a, lo, hi);
            ++lo;
            --hi;
        }
    }
    public static void main(String[] args) {
        int[] array = {1,2,3,4,5,6,7};
        int cnt=0;
        do {
            System.out.println(Arrays.toString(array));
            cnt++;
        }while(nextPermutation(array, array.length));
        System.out.println(cnt);//5040=7!
    }
}

Алгоритм генерации всех перестановок (Java). Он генерирует следующую лексикографическую последовательность, модифицирует массив на месте.