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

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

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

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

Если я правильно понял, вам нужны размещения без повторений. Их можно сгенерировать, например, так:

static void Main(string[] args)
{
    var chars = new HashSet<char>(new [] { 'a', 'b', 'c', 'd' });
    foreach (var s in GetAllPermutations(chars, 3)) // 3 -- длина
        Console.WriteLine(s);
}

static IEnumerable<string> GetAllPermutations(HashSet<char> chars, int n)
{
    if (n == 0)
        yield return "";
    foreach (var c in chars.ToList())
    {
        chars.Remove(c);
        foreach (var s in AddAllFrom(chars, n - 1))
            yield return c + s;
        chars.Add(c);
    }
}

Результат:

abc
abd
acd
acb
adb
adc
bcd
bca
bda
bdc
bac
bad
cda
cdb
cab
cad
cbd
cba
dab
dac
dbc
dba
dca
dcb

Поскольку функция GetAllPermutations возвращает ленивый энумератор, вы можете получить только часть результатов, применив LINQ-операторы наподобие .Take(10). Но моя функция не является чистой: во время энумерации изменяется состояние множества chars. (Этот же эффект не даст обходить одну и ту же последовательность дважды одновременно.) Для того, чтобы сделать функцию чистой, необходимо инкапсулировать изменяемые данные. Получается следующее:

static void Main(string[] args)
{
    var chars = new[] { 'a', 'b', 'c', 'd' };
    var seq = GetAllPermutations(chars, 3).Take(10);
    foreach (var s in seq) // 3 -- длина
        Console.WriteLine(s);
}

static IEnumerable<string> GetAllPermutations(IEnumerable<char> chars, int n)
{
    HashSet<char> curr = new HashSet<char>(chars);
    foreach (var s in GetAllPermutationsRec(n))
        yield return s;
}

static IEnumerable<string> GetAllPermutationsRec(int n, HashSet<char> curr) // not pure!
{
    if (n == 0)
        yield return "";
    foreach (var c in curr.ToList())
    {
        curr.Remove(c);
        foreach (var s in GetAllPermutationsRec(n - 1))
            yield return c + s;
        curr.Add(c);
    }
}

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

Задача: перебрать все возможные сочетания букв латинского алфавита, длинной от 1 до 3 символов

Решение:
На первый взгляд самым простым выходом было бы сделать рекурсивный вызов, в данном частном случае когда идет речь о строках не более 3 символов, такое решение будет самое быстрое в реализации, примеров с рекурсией я приводить не стану, но варианты с рекурсией не всегда подходят в меру своего ресурсопотребления.
Самым простым вариантом без рекурсии, если задача очень проста и не требует универсальности решения, являются вложенные циклы. Этот вариант прост в реализации, когда речь идет о переборе, например строк длиной не более 2-3 символов, 3 вложенных цикла портят читаемость кода, а если нам нужно не 3 а 30 символов, 30 вложений %)
И, наконец, мы дошли до начинки, как можно перебрать все варианты сочетания всех букв, расширим задачу до всех букв с учетом регистра и все цифры (a-zA-Z0-9).
«Все гениальное — просто», среди читателей этой статьи найдется не мало людей, которым будет достаточно назвать один термин, который лег в основу реализации данного алгоритма, но есть и такие, которым нужно все разжевать, поэтому я приведу код, который это делает на языке программирования PHP, а термин этот «Системы счисления»
«Системы счисления» — почти идеально подходят для перебора таких последовательностей, за исключением того, что система счисления воспринимается как число, в результате этого выпадают значения с первым нулевым элементом, т.е если рассматривать десятичную систему счисления, то после 99 идет 100 101 101…, а в строковом представлении после 99 должно идти 000 001 002. Ну и, наконец, сам алгоритм:

// Формируем рабочую систему (a-zA-Z0-9)
$work = array(0,1,2,3,4,5,6,7,8,9);
// буквы нижнего регистра
for($i = 97; $i <= 122; $i++){
    $work[] = chr($i);
}
// буквы верхнего регистра
for($i = 65; $i <= 90; $i++){
    $work[] = chr($i);
}
     
// проверим, что получилось, если нужно
//print_r($work);

// Теперь можно приступать к решению нашего примера
// перебор будет в одном цикле, без рекурсии, и перебирать мы будем не буквы, а цифры

// параметры перебора
$min_length = 1;
$max_length = 3; // поставим 3, чтобы хватило памяти для массива $result

// определяем порядковый номер минимального значения длинной строки $min_length
$min = str_to_dec(str_repeat($work[sizeof($work)- 1], $min_length-1), $work)+1;
// определяем порядковый номер максимального значения длинной строки $max_length
$max = str_to_dec(str_repeat($work[sizeof($work)- 1], $max_length), $work);

// предварительно определить количество возможных значений перебора можно следующим образом
// столько же итераций совершит цикл
$size = $max - $min +1;

$result = array();
for($i = $min; $i <= $max; $i++ )
{
    $result[] = dec_to_str($i, $work);
}
     
// $result = массив, содержащий все возможные значения длинной строки от $min_length до $max_length
print_r($result);
     
// для ускорения выполнения всего перебора , цикл от min до max можно разбить на несколько циклов
// и запустить их к примеру с помощью pcntl_fork

// методы
/**
 * переводит строки из системы счисления $work в десятичную систему
 * другими словами находит порядковый номер строки в списке вариаций сочетаний
 * при неизменном массиве $work, каждая последовательность будет иметь свой уникальный порядковый номер
 * и не будет повторяться
 */
function str_to_dec($s, $sys)
{
    $sys = array_flip($sys);
     
    $j = -1;
    $result = 0;
    for($i = strlen($s)-1; $i >= 0; $i--)
    {
        $j++;
        $result += ($sys[$s[$j]]+1) * pow(sizeof($sys), $i);
    }
    return $result;
}
/**
 * переводит число $int (десятичная система) в систему исчисления $work
 */
function dec_to_str($i, $work)
{
    $r = sizeof($work);
    $w = '';
    while($i > 0)
    {
        $t = $i % $r;
        if($t == 0){
            $w .= $work[$r-1];
            $i = $i / $r -1;
        } else {
            $w .= $work[$t-1];
            $i = ($i - $t) / $r;
        }
    }
    return strrev($w);
}

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

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