Генерация перестановок списка чисел в Python

Question

Имеется список c повторяющимися элементами, например [1,1,1,0]. Нужно сгенерировать все возможные варианты перестановок данного списка без повторений и без использования библиотек. Для данного списка результатом было бы следующее:

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

Как это можно реализовать без помощи библиотек по типу itertools ?

Answer 1

Например как-то так:

def permutations(iterable):
    if len(iterable) == 1:
        yield (iterable[0], )
    else:
        for perm in permutations(iterable[1:]):
            for i in range(len(iterable)):
                yield perm[:i] + (iterable[0], ) + perm[i:]

def unique_permutations(iterable):
    return list(set(permutations(iterable)))
                
print(list(map(list, unique_permutations([1,1,1,0]))))
print([''.join(x) for x in unique_permutations("вова")])

Результат:

[[1, 1, 0, 1], [0, 1, 1, 1], [1, 1, 1, 0], [1, 0, 1, 1]]
['овва', 'ввао', 'ваво', 'авов', 'аовв', 'воав', 'ваов', 'оавв', 'авво', 'вова', 'овав', 'ввоа']

Answer 2

Итеративный подход:

s = [ 1, 2, 3, 4]
p = [ 0 for _ in s ]
i = 1
res = []

while i < len(s):
    if p[i] < i:
        j = 0 if i % 2 == 0 else p[i]
        s[i], s[j] = s[j], s[i]
        p[i] += 1
        i = 1
        if s not in res: 
            res.append(list(s))
    else:
        p[i] = 0
        i += 1

res  # [[1, 1, 1, 0], [0, 1, 1, 1], [1, 0, 1, 1], [1, 1, 0, 1]]

Или же всё-таки:

import itertools

list(set(itertools.permutations([1, 1, 1, 0])))
# [(1, 1, 0, 1), (1, 1, 1, 0), (0, 1, 1, 1), (1, 0, 1, 1)]

Answer 3

В стандартной библиотеке C++ есть функция std::next_permutation. Она по перестановке в массиве строит следующую в лексикографическом порядке. Время построения в среднем константное, дополнительная память тоже константная. Повторяющиеся элементы обрабатываются автоматически. Генератор перестановок ниже основан на этой функции:

import sys


def next_permutation(a):

    def swap(i, j):
        a[i], a[j] = a[j], a[i]

    def reverse_tail(i):
        j = len(a) - 1
        while i < j:
            swap(i, j)
            i += 1
            j -= 1

    if len(a) <= 1:
        return False

    i = len(a) - 1
 
    while True:
        i1 = i
        i -= 1
        if a[i] < a[i1]:
            i2 = len(a)
            while True:
                i2 -= 1
                if a[i] < a[i2]:
                    break
            swap(i, i2)
            reverse_tail(i1)
            return True

        if i == 0:
            reverse_tail(0)
            return False


def permutations(a):
    a = sorted(list(a))
    yield a
    while next_permutation(a):
        yield a


for p in permutations(map(int, sys.argv[1:])):
    print(p)

$ python permutations.py 0 1 2 3
0 1 2 3
0 1 3 2
0 2 1 3
0 2 3 1
0 3 1 2
0 3 2 1
1 0 2 3
1 0 3 2
1 2 0 3
1 2 3 0
1 3 0 2
1 3 2 0
2 0 1 3
2 0 3 1
2 1 0 3
2 1 3 0
2 3 0 1
2 3 1 0
3 0 1 2
3 0 2 1
3 1 0 2
3 1 2 0
3 2 0 1
3 2 1 0

$ python permutations.py 0 1 1 1
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0

БЛОГ НА HUSL

Генерация перестановок списка чисел в Python

Ответы (3 шт):