Как найти все перестановки строки python

why do you not simple do:

from itertools import permutations
perms = [''.join(p) for p in permutations(['s','t','a','c','k'])]
print perms
print len(perms)
print len(set(perms))

you get no duplicate as you can see :

 ['stack', 'stakc', 'stcak', 'stcka', 'stkac', 'stkca', 'satck', 'satkc', 
'sactk', 'sackt', 'saktc', 'sakct', 'sctak', 'sctka', 'scatk', 'scakt', 'sckta',
 'sckat', 'sktac', 'sktca', 'skatc', 'skact', 'skcta', 'skcat', 'tsack', 
'tsakc', 'tscak', 'tscka', 'tskac', 'tskca', 'tasck', 'taskc', 'tacsk', 'tacks', 
'taksc', 'takcs', 'tcsak', 'tcska', 'tcask', 'tcaks', 'tcksa', 'tckas', 'tksac', 
'tksca', 'tkasc', 'tkacs', 'tkcsa', 'tkcas', 'astck', 'astkc', 'asctk', 'asckt', 
'asktc', 'askct', 'atsck', 'atskc', 'atcsk', 'atcks', 'atksc', 'atkcs', 'acstk', 
'acskt', 'actsk', 'actks', 'ackst', 'ackts', 'akstc', 'aksct', 'aktsc', 'aktcs', 
'akcst', 'akcts', 'cstak', 'cstka', 'csatk', 'csakt', 'cskta', 'cskat', 'ctsak', 
'ctska', 'ctask', 'ctaks', 'ctksa', 'ctkas', 'castk', 'caskt', 'catsk', 'catks', 
'cakst', 'cakts', 'cksta', 'cksat', 'cktsa', 'cktas', 'ckast', 'ckats', 'kstac', 
'kstca', 'ksatc', 'ksact', 'kscta', 'kscat', 'ktsac', 'ktsca', 'ktasc', 'ktacs', 
'ktcsa', 'ktcas', 'kastc', 'kasct', 'katsc', 'katcs', 'kacst', 'kacts', 'kcsta', 
'kcsat', 'kctsa', 'kctas', 'kcast', 'kcats']
    120
    120
    [Finished in 0.3s]

В этом посте мы увидим, как перечислить все перестановки строки в Python.

Например, строка ABC имеет 6 перестановок, т.е. ABC, ACB, BAC, BCA, CBA, CAB.

Потренируйтесь в этой проблеме

В Python мы можем использовать встроенный модуль itertools чтобы получить перестановки элементов в списке, используя permutations() функция.

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

1. Рекурсивная реализация

Идея состоит в том, чтобы преобразовать данную строку в массив символов и на месте генерировать все его перестановки, используя Backtracking.

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

Скачать  Выполнить код

результат:

ABC
ACB
BAC
BCA
CBA
CAB

 
Вот еще одна реализация на Python, которая не преобразует строку в массив символов.

Скачать  Выполнить код

результат:

ABC
ACB
BAC
BCA
CBA
CAB

2. Итеративная реализация

Идея состоит в том, чтобы сохранить частично сгенерированные перестановки, а затем использовать эти частичные перестановки для создания окончательных перестановок в дальнейших итерациях. Вот как будет выглядеть код:

Скачать  Выполнить код

результат:

[‘CAB’, ‘ACB’, ‘ABC’, ‘CBA’, ‘BCA’, ‘BAC’]

 
Временная сложность приведенных выше решений равна O(n.n!) так как есть n! перестановки для строки длины n, и каждая перестановка занимает O(n) время.

Перестановки и комбинации набора элементов в Python – это различные расположения элементов набора:

• Комбинация – это набор элементов, порядок которых не имеет значения.
• Перестановка – это расположение набора, в котором порядок имеет значение.

Рассмотрим набор как:

{A, B, C}

Перестановки вышеуказанного набора следующие:

('A', 'B', 'C')
('A', 'C', 'B')
('B', 'A', 'C')
('B', 'C', 'A')
('C', 'A', 'B')
('C', 'B', 'A')

Комбинации вышеуказанного набора, когда два элемента взяты вместе, следующие:

('A', 'B')
('A', 'C')
('B', 'C')

В этом руководстве мы узнаем, как получить перестановки и комбинации группы элементов в Python. Мы рассмотрим наборы символов и цифр.

Мы будем использовать методы combinations() и permutations() в модуле itertools.

Перестановки числовых данных

Чтобы использовать метод permutations() в модуле itertools, нам сначала нужно импортировать модуль.

import itertools

Теперь давайте определим набор чисел.

val = [1, 2, 3, 4]

Теперь, чтобы получить список перестановок, воспользуемся методом permutations().

perm_set = itertools.permutations(val)

Строка кода выше дает объект itertools. Чтобы напечатать различные перестановки, мы будем перебирать этот объект.

for i in perm_set:
    print(i)

Мы получаем результат как:

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

Полный код этого раздела приведен ниже:

import itertools
 
val = [1, 2, 3, 4]
 
perm_set = itertools.permutations(val)
 
for i in perm_set:
    print(i)

Перестановки строки

Далее мы узнаем, как получить перестановки символов в строке.

Мы будем использовать метод permutations(), но на этот раз мы передадим строку в качестве аргумента.

import itertools
 
s = "ABC"

perm_set = itertools.permutations(s)
for val in perm_set:
    print(val)

Вывод :

('A', 'B', 'C')
('A', 'C', 'B')
('B', 'A', 'C')
('B', 'C', 'A')
('C', 'A', 'B')
('C', 'B', 'A')

Перестановки фиксированной длины

Мы можем найти перестановки набора, в котором мы берем только указанное количество элементов в каждой перестановке. Это похоже на nPr в области математики.

Код для поиска перестановок фиксированной длины приведен ниже:

import itertools
 
val = [1, 2, 3, 4]
 
perm_set = itertools.permutations(val,2)
 
for i in perm_set:
    print(i)

Вывод :

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

Комбинации числовых данных

Так же, как метод permutations(), мы можем использовать combinations() также в itertools для получения комбинаций набора.

При вызове combinations() нам нужно передать два аргумента: набор для поиска комбинаций и число, обозначающее длину каждой комбинации.

import itertools
 
val = [1, 2, 3, 4]
 
com_set = itertools.combinations(val, 2)
 
for i in com_set:
    print(i)

Вывод :

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

Комбинации строки

Мы также можем получить комбинации строки. Используйте следующий фрагмент кода:

import itertools
 
s = "ABC"
 
com_set = itertools.combinations(s, 2)
 
for i in com_set:
    print(i)

Вывод :

('A', 'B')
('A', 'C')
('B', 'C')

Комбинации с заменами

В модуле itertools есть еще один метод, который называется комбинациями_with_replacement(). Этот метод также учитывает комбинацию числа с самим собой.

Посмотрим, как это работает.

Для числового набора

import itertools
 
val = [1, 2, 3, 4]
 
com_set = itertools.combinations_with_replacement(val, 2)
 
for i in com_set:
    print(i)

Вывод :

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

Вы можете видеть разницу в выводе выше и выводе для работы нормальной комбинации. Здесь у нас есть такие комбинации, как (1,1) и (2,2), которых нет в обычных комбинациях.

Для строки

import itertools
 
val = "ABCD"
 
com_set = itertools.combinations_with_replacement(val, 2)
 
for i in com_set:
    print(i)

Вывод :

('A', 'A')
('A', 'B')
('A', 'C')
('A', 'D')
('B', 'B')
('B', 'C')
('B', 'D')
('C', 'C')
('C', 'D')
('D', 'D')

1. Используйте функцию itertools.permutations() для возврата всех перестановок строки в Python
2. Создайте определяемую пользователем функцию для возврата всех перестановок для строки в Python

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

Строку, как мы знаем, можно рассматривать как набор отдельных символов.

В этой статье мы постараемся найти все возможные перестановки для заданной строки.

Модуль itertools используется для создания и работы с различными итеративными объектами. Функция permutations() из этого модуля может возвращать все возможные варианты для заданного набора значений.
Он возвращает объект типа itertools, который содержит кортеж, содержащий возможное расположение элементов. Мы можем использовать список для просмотра элементов этого объекта. Мы также можем использовать эту функцию со строкой.

Например,

from itertools import permutations
lst = list(permutations('day'))
print(lst)

Выход:

[('d', 'a', 'y'), ('d', 'y', 'a'), ('a', 'd', 'y'), ('a', 'y', 'd'), ('y', 'd', 'a'), ('y', 'a', 'd')]

Обратите внимание на кортежи, созданные в выходных данных, содержащих расположение символов. Мы можем изменить это на список строк, используя функцию join () и метод понимания списка.

См. Следующий код.

from itertools import permutations
lst = [''.join(p) for p in permutations('day')]
print(lst)

Выход:

['day', 'dya', 'ady', 'ayd', 'yda', 'yad']

Мы объединяем элементы кортежа с помощью функции join() и используем ее для каждого кортежа путем итерации по списку.

Создайте определяемую пользователем функцию для возврата всех перестановок для строки в Python

Мы можем создать простую функцию для поиска всех перестановок строки. Мы создадим рекурсивную функцию. В этом методе мы просто поменяем местами строковые элементы один раз и снова вызовем функцию с новым расположением. Показываем финальные аранжировки.

Мы реализуем вышеуказанную логику в следующем коде.

def string_permutations(s, i, n): 
    if i==n: 
        print(''.join(s) )
    else: 
        for j in range(i,n): 
            s[i], s[j] = s[j], s[i] 
            string_permutations(s, i+1, n) 
            s[i], s[j] = s[j], s[i]  
  
a = "day"
x = len(a) 
s = list(a) 
print(permute(s, 0, x))

Выход:

day
dya
ady
ayd
yad
yda
None

Как видите, указаны начальная и конечная позиции, в которых мы хотим выполнить перестановки. Строка также передается как список символов. Чтобы найти все возможные перестановки, мы устанавливаем начало в 0 и конец как длину строки.