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

Перестановки и комбинации набора элементов в 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')

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

Этот модуль очень эффективен и работает очень быстро, чтобы найти все возможные комбинации. Но функции модуля itertools – не единственный возможный метод, который мы можем использовать для поиска комбинаций.

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

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

• итерационный метод;
• метод рекурсии.

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

Поиск с помощью метода итерации

Чтобы реализовать итеративный подход в программе, мы должны импортировать библиотеку numpy, чтобы использовать ее функции.

Пример:

 
# Import numpy module in program 
import numpy as np 
# Default function to use iterative approach 
def RecurCombo(iterArray, num): 
 char = tuple(iterArray) # converting input string into a tuple 
 m = len(char) # length of string or tuple 
 if num > m: # checking if length of combinations is more than length of string 
   return 
 index = np.arange(num) # using numpy arrange() function 
 # Yielding the first sequence 
 yield tuple(char[i] for i in index) 
 # Using while loop with true condition 
 while True: 
  # iterating over the tuple we made using reversed for loop 
  for a in reversed(range(num)): 
     if index[a] != a + m - num: 
         break 
     else: 
              return 
  index[a] += 1 
  # another for loop iteration 
  for b in range(a + 1, num): 
   index[b] = index[b - 1] + 1 
  yield tuple(char[a] for a in index) # yielding possible combinations from given string 
# Taking an input string from user 
inputArray = input("Enter an input string to find combinations: ") 
# Printing different combinations as result in output 
print("All possible combinations of three letter sets from the string given by you is: ") 
print([x for x in RecurCombo(inputArray, 3)]) 

Выход:

Enter an input string to find combinations: JavaTpoint 
All possible combinations of three letter sets from the string given by you is:  
[('J', 'a', 'v'),('J', 'a', 'a'),('J', 'a', 'T'),('J', 'a', 'p'),('J', 'a', 'o'),('J', 'a', 'i'),('J', 'a', 'n'),('J', 'a', 't')] 

Объяснение:

Мы использовали метод итерации в приведенной выше программе, чтобы найти комбинации из входной строки.

Во-первых, мы использовали функцию Python по умолчанию с входной строкой и длиной комбинационного набора в качестве параметра. Затем мы преобразовали входную строку в кортеж. Также мы проверили, не превышает ли требуемая длина комбинации длину строки.

После этого мы использовали функцию order() numpy, чтобы установить индекс для кортежа. Мы собираемся перебирать кортеж с индексной переменной.

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

Затем мы взяли строку ввода от пользователя. В последнем действии мы вернули комбинации трех наборов из входной строки.

Использование метода рекурсии

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

 
# Default Python function to use recursive approach 
def RecurCombo(array, num):  
    if num == 0:  
        return [[]] # if length for combination is 0 
    l =[] # list to printed in result 
    # Using for loop to implement recursive approach 
    for j in range(0, len(array)):  
        emptyArray = array[j] # define an empty array to print list of sets 
        recurList = array[j + 1:] 
        # Recursion method on list defined in function 
        for x in RecurCombo(recurList, num-1):  
            l.append([emptyArray]+x) # appending list 
    return l # list as result of recursion 
if __name__=="__main__": 
    # Taking an input string from user 
    inputArray = input("Enter an input string to find combinations: ") 
    # Printing different combinations as result in output 
    print("All possible combinations of three letter sets from the string given by you is: ") 
    print(RecurCombo([a for a in inputArray], 3)) 

Выход:

Enter an input string to find combinations: Python 
All possible combinations of three letter sets from the string given by you is:  
[['P', 'y', 't'], ['P', 'y', 'h'], ['P', 'y', 'o'], ['P', 'y', 'n'], ['P', 't', 'h'], ['P', 't', 'o'], ['P', 't', 'n'], ['P', 'h', 'o'], ['P', 'h', 'n'], ['P', 'o', 'n'], ['y', 't', 'h'], ['y', 't', 'o'], ['y', 't', 'n'], ['y', 'h', 'o'], ['y', 'h', 'n'], ['y', 'o', 'n'], ['t', 'h', 'o'], ['t', 'h', 'n'], ['t', 'o', 'n'], ['h', 'o', 'n']] 

Объяснение:

В приведенной выше программе при реализации рекурсивного подхода мы не использовали какой-либо конкретный модуль Python. Как и метод итерации, мы использовали функцию по умолчанию для реализации метода рекурсии в коде.

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

Статьи / Python

Встроенный модуль itertools в Python — простой инструментарий, позволяющий генерировать полный список возможных комбинаций из заданного набора символов. Как с этим работать и справляться — далее в статье.

Что ж, в преддверии Нового года KOTOFF.net вновь расправляет крылья.

И сразу к делу. Рассмотрим всего 3 функции и их различия. 

1. Нахождение всевозможных комбинаций из набора символов

Допустим, у нас есть некий алфавит из трёх букв (А, Б, В), и из него необходимо составить максимальное количество трёхзначных слов (комбинаций). Причём в данном случае буквы могут повторяться. Алфавит короткий, однако у нас получится составить целых 27 слов. На каждую позицию приходится по 3 варианта букв, соответственно, общее количество комбинаций можно посчитать так: n^k (n — количество доступных символов в степени k — длина конечной комбинации). Для нашего случая: 3³ = 27

Теперь импортирую itertools и сгенерирую всё то, что выше считали руками, но теперь уже с помощью функции product():

from itertools import product


for i in product('АБВ', repeat=3):
    print(''.join(i), end=' ')

Функция принимает два параметра (набор символов и длина конечного объекта). С помощью join() получили строковое представление полученной комбинации.

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

Можно добавить в цикл некий фильтр (условие). Например, сделаю так, чтобы комбинируемые слова начинались только с «X» и заканчивались на «YZY»:

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

from itertools import product
import re


chars = '0123456789АВЕКМНОРСТУХ'
reg = '[АВЕКМНОРСТУХ]{1}d{3}[АВЕКМНОРСТУХ]{2}'

for i in product(chars, repeat=6):
    if re.fullmatch(reg, ''.join(i)):
        print(''.join(i))

Кстати, если добавить в цикл счётчик, то в итоге получим цифру 1.728.000 (12*10*10*10*12*12). Именно столько номеров формата x000xx можно наклепать для одного региона

2. Перестановка символов в наборе

В отличие от предыдущего примера, теперь мы не можем использовать по несколько раз один и тот же символ. Можем только переставлять их местами. Принцип подсчёта количества комбинаций остаётся тот же: необходимо перемножить количество вариантов символов на каждую позицию слова между собой. Но поскольку по мере составления слова на каждую последующую позицию символов будет оставаться всё меньше и меньше, то и формула также меняется на: n! / (n-k)! (n — количество доступных символов, k — длина слова). Если n = k, то можно использовать упрощённую формулу: n! (факториал числа n).

В питоне для таких целей используется функция permutations(). Принимает тоже два параметра: набор символов и длину генерируемой комбинации:

from itertools import permutations

for i in permutations('АБВ'):
    print(''.join(i))

Из трёх букв будет сгенерировано 6 различных слов с неповторяющимися символами (1! = 1 * 2 * 3 = 6)

Попробуем составить трёхзначные слова в 5-символьном алфавите (5! / (5-3)! = 120 / 2 = 60):

Кстати, если в заданном «алфавите» есть повторяющиеся символы, то они будут повторяться и в комбинациях:

3. Сочетания без повторений

А если нужно составить не комбинации, а отдельные неповторяющиеся сочетания? Например, есть 6 человек. Вопрос: какими способами их можно разбить по парам? Опять же, пользуемся формулой: n! / (n-k)! / k! (n — количество доступных объектов/символов, k — количество сочетаний). Соответственно, существует 6! / (6-2)! / 2! = 720 / 24 / 2 = 15 вариантов разбиения этих 6 персон по парам.

Теперь реализуем эту задачу на питоне с помощью функции combinations(). Принимает она два параметра — список и кол-во сочетаний:

from itertools import combinations

for i in combinations(['Юля', 'Даша', 'Соня', 'Дима', 'Игорь', 'Вадим'], 2):
    print(' - '.join(i))

Результат работы программы будет таков:

На этом, пожалуй, на сегодня всё. С наступающим!