Перестановки с повторениями. Неанаграммный алгоритм - PullRequest
Новая
       73

Перестановки с повторениями. Неанаграммный алгоритм

0 голосов
/ 25 января 2020

ЦЕЛЬ: Я пытаюсь найти максимальную длину списка, состоящего из неанаграмм, длиной N, каждое слово-анаграмма состоит из комбинации из 3 букв: «А», «В» или « C 's.

Например, если N = 5: [AAAAA, AAAAB, ..., AABB C, ..., BABAA, ..., CCCCC].

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

МОЯ ПРОБЛЕМА: Во-первых, я хотел бы знать, как произвести все 3 ^ 5 перестановок. Моя попытка: 

import itertools
print([''.join(p) for p in itertools.combinations_with_replacement('abc', 3)])

>> ['aaaaa', 'aaaab', 'aaaac', 'aaabb', 'aaabc', 'aaacc', 'aabbb', 'aabbc', 'aabcc', 'aaccc', 'abbbb', 'abbbc', 'abbcc', 'abccc', 'acccc', 'bbbbb', 'bbbbc', 'bbbcc', 'bbccc', 'bcccc', 'ccccc']

Ясно, что список слишком длинен.

Я думал о разбиении, например,) 0As, 2Bs, 3Cs - это 0 + 2 + 3. Нахождение исчерпывающе вручную дало ответ 21 в течение минуты в этом примере. Фактически, я упростил процесс, заметив, что номер третьей буквы (скажем, C, без потери общности) зависит от комбинации As и Bs, поэтому я нарисовал таблицу - красный крест представляет недопустимую комбинацию, поскольку sum> = 5: image= 5"> (Кстати, мне интересно, как эта идея распространяется на N> 3; поскольку при взгляде на стол квадрат разрезается пополам ...)

Чтобы перенести этот «алгоритм» на компьютер, я подумал о том, чтобы как-то использовать симметрии - это напоминало мне коды Грея - но я не могу правильно его реализовать.

Есть ли какие-нибудь функции, которые позаботятся об этом эффективно? Тогда мне даже не придется (по крайней мере, явно) вызывать функцию проверки анаграммы для сравнения входных данных.

1 Ответ

3 голосов
/ 25 января 2020

AIM: Я пытаюсь найти максимальную длину списка, состоящего из неанаграмм, длиной N, каждое слово-анаграмма состоит из комбинации из 3 букв: «A's» B или 'C'.

С этой целью ваш подход к генерации всех 3 ** 5 возможных строк и последующей фильтрации анаграмм неэффективен. Требуемое число можно вычислить напрямую, без генерации каких-либо строк:

  • Две строки являются анаграммами тогда и только тогда, когда они имеют одинаковые буквенные частоты. Например, ABCAB является анаграммой AABBC, потому что для обеих строк буквенные частоты равны {'A': 2, 'B': 2, 'C': 1}.
  • Следовательно, максимально возможная длина списка, не содержащего анаграмм, равна числу возможных различных частотные карты, где ключи 'A', 'B', 'C', значения являются неотрицательными целыми числами, а сумма значений равна 5 (так что длина строки равна 5).
  • Это можно вычислить путем подсчета количество способов разбиения неотрицательного целого числа n на k частей, где порядок частей имеет значение, и часть может быть равна 0.

Вот рекурсивное решение: 

from functools import lru_cache

# memoize since there are overlapping subproblems
@lru_cache(maxsize=None)
def count_partitions(n, k):
    if n < 0 or k < 0:
        raise ValueError()
    elif n == 0:
        return 1
    elif k <= 1:
        return k
    else:
        return sum(count_partitions(r, k - 1) for r in range(n + 1))

Пример: 

>>> count_partitions(5, 3)
21

Это согласуется с itertools.combinations_with_replacement, который в этом случае генерирует список из 21 строки, и это согласуется с вашими вычислениями вручную.

На самом деле, мы можем go немного продвинуться, поставив задачу немного иначе: число способов разбиения n на k частей эквивалентно количеству способов вставки k - 1 разделители между n элементами. Результатом размещения разделителей является строка длиной n + k - 1:

  • . В приведенном выше примере разделители будут размещены как AA|BB|C.
  • И наоборот, если мы знаем где два разделителя расположены, например, ..|..|., тогда мы можем заполнить буквами, чтобы получить строку AA|BB|C.

Таким образом, мы можем уменьшить проблему до подсчета числа способов размещение k - 1 символов | в строку длиной n + k - 1. Это просто биномиальный коэффициент binom(n + k - 1, k - 1): 

def binom(n, k):
    if n < 0 or k < 0 or k > n:
        return 0
    k = min(k, n - k)
    result = 1
    for a, b in zip(range(n, n - k, -1), range(1, k + 1)):
        result *= a
        result //= b
    return result

def count_partitions(n, k):
    return binom(n + k - 1, k - 1)
...