Как найти комбинацию символов

Статьи / 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))

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

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

You’re going to have to be more specific on exactly WHAT you want your function to get. There are many different definitions of “combinations” and you haven’t specified whether you want ordered or unordered combinations.

Mathematically, if you have n elements and want a LIST of k of them (ordered with repeats), that gives you

n ^ k

combinations. (6 ^ 4 = 1296 combinations in your original example, which is a lot!). However, if you have n elements and want a MULTISET of k of them (unordered with repeats), that gives you

(n + k - 1)! / (k! * (n - 1)!)

combinations and is a much harder enumeration.

If k is small, you can generate the first one with a limited number of for loops but this becomes cumbersome very quickly as k grows. This strongly hints at the need for a RECURSIVE method:

public static String[] getAllLists(String[] elements, int lengthOfList)
{
    //initialize our returned list with the number of elements calculated above
    String[] allLists = new String[(int)Math.pow(elements.length, lengthOfList)];

    //lists of length 1 are just the original elements
    if(lengthOfList == 1) return elements; 
    else
    {
        //the recursion--get all lists of length 3, length 2, all the way up to 1
        String[] allSublists = getAllLists(elements, lengthOfList - 1);

        //append the sublists to each element
        int arrayIndex = 0;

        for(int i = 0; i < elements.length; i++)
        {
            for(int j = 0; j < allSublists.length; j++)
            {
                //add the newly appended combination to the list
                allLists[arrayIndex] = elements[i] + allSublists[j];
                arrayIndex++;
            }
        }

        return allLists;
    }
}

Not only will this method generate all the lists, but it will enumerate them in order. That is, the output will be

aaaa
aaab
aaac
aaa1
aaa2
aaa3
aaba
aabb
aabc
aab1
...
3323
333a
333b
333c
3331
3332
3333

using your original input. It can also generate any length of words (be very careful with this! Just with words of length 8 I wound up with 1,679,616 combinations!).

If the method confuses you (it’s a recursive method, so it’s a bit hard to follow) or if you want a solution to the second combination problem, feel free to ask. Also, this method is somewhat inefficient because it recalculates the combinations for all the sublists, so it’s not viable for really long lists. If you really wanted efficiency you would store the already-calculated tuples in a global list.

С подстановочными знаками можно поэкспериментировать. Все они перечислены на странице поддержки MS Office в разделе о работе с Word.

Если ввести в форму поиска пять вопросительных знаков “?????”, то система выдаст очень плачевную картину, потому что во-первых, без указания границ слова результат выделит слова с этими пятью знаками в середине слова и во-вторых, среди вопросительных знаков могут быть пробелы. Даже если по краям установить угловые скобки “<?????>”, то избежать попадания пробела в середину слова не удастся. Так что поиск с вопросительными знаками отметаем.

Тогда нужно брать подстановочные знаки.

Границы слова отметить нужно обязательно – “<” и “>”. Далее можно попробовать ввести любой символ в диапазоне от “а” до “я” пять раз. Получим вот такую формулу: “<[а-я][а-я][а-я][а-я][а-я]>”.

Есть и более экономичный вариант, если указать количество символов (кроме пробелов) после заданного знака с помощью фигурных скобок. А этот заданный знак в диапазоне от “а” до “я”. (Если указать просто знак, то количество этих повторяющихся знаков будет 5 и нет гарантий, что в тексте есть слово с одинаковыми пятью буквами). И не забудем про границы слова

Итак, формула – “<[а-я]{5}>”. Количество букв в слове будет равно 5, а буква может быть любой в диапазоне от “а” до “я”.