У меня есть «n» количество строк в качестве входных данных, которые я разделяю на возможные подпоследовательности в список, как показано ниже

Если входные данные: aa, b, aa

Я создаю список, подобный приведенному ниже (каждый список имеет подпоследовательности строки):

 aList = [['a', 'a', 'aa'], ['b'], ['a', 'a', 'aa']]
 

Я хотел бы найти комбинации палиндромов по спискам в aList.
Например, возможными палиндромами для этого будут 5 — aba, aba, aba, aba, aabaa

Это может быть достигнуто с помощью алгоритма грубой силы с использованием приведенного ниже кода:

 d = []
def isPalindrome(x):
    if x == x[::-1]: return True
    else: return False
for I in itertools.product(*aList):
    a = (''.join(I))
    if isPalindrome(a):
        if a not in d: 
            d.append(a)
        count  = 1
 

Но этот подход приводит к таймауту, когда количество строк и длина строки больше.

Есть ли лучший подход к проблеме?

Вторая версия

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

Обратите внимание, что ваша функция isPalindrome() может быть упрощена до одного выражения, поэтому я удалил ее и просто выполнил тест в строке, чтобы избежать накладных расходов на ненужный вызов функции.

 import itertools

aList = [['a', 'a', 'aa'], ['b'], ['a', 'a', 'aa']]

d = []
seen = set()
for I in itertools.product(*aList):
    if I not in seen:
        seen.add(I)
        a = ''.join(I)
        if a == a[::-1]:
            d.append(a)

print('d: {}'.format(d))
 

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

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

Например, допустим, что ваше пространство такое

 [["a","b","c"], ... , ["b","c","d"]]
 

Мы можем видеть, что если вы выбираете «a» в качестве первого выбора, в последней группе нет «a», и это исключает все возможные решения, которые можно было бы попробовать другим способом.

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

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

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

Это должно привести к значительной ранней обрезке в дереве поиска. Таким образом, вы не выполнили бы полное декартово произведение комбинаций.

Я также написал функцию для получения всех подстрок из заданного слова, которые у вас, вероятно, уже были:

 def allsubstr(str):
    return [str[i:j 1] for i in range(len(str)) for j in range(i, len(str))]

def getpalindromes_trincot(aList):

    def collectLeft(common, needle, i, j):
        if i > j:
            return [common   needle   common[::-1]] if needle == needle[::-1] else []
        results = []
        for seq in aRevList[j]:
            if seq.startswith(needle):
                results  = collectRight(common needle, seq[len(needle):], i, j-1)
            elif needle.startswith(seq):
                results  = collectLeft(common seq, needle[len(seq):], i, j-1)
        return results

    def collectRight(common, needle, i, j):
        if i > j:
            return [common   needle   common[::-1]] if needle == needle[::-1] else []
        results = []
        for seq in aList[i]:
            if seq.startswith(needle):
                results  = collectLeft(common needle, seq[len(needle):], i 1, j)
            elif needle.startswith(seq):
                results  = collectRight(common seq, needle[len(seq):], i 1, j)
        return results

    aRevList = [[seq[::-1] for seq in seqs] for seqs in aList]
    return collectRight('', '', 0, len(aList)-1)

# sample input and call:
input = ['already', 'days', 'every', 'year', 'later'];
aList = [allsubstr(word) for word in input]
result = getpalindromes_trincot(aList)
 

Я провел сравнение времени с решением, опубликованным Мартино. Для примеров данных, которые я использовал, это решение примерно в 100 раз быстрее:

Посмотрите, как он выполняется на repl.it

Еще одна оптимизация

Некоторая выгода также может быть найдена в том, чтобы не повторять поиск, когда в первом массиве есть несколько записей с одной и той же строкой, как 'a' в вашем примере данных. Результаты, включающие вторую 'a' , очевидно, будут такими же, как и для первой. Я не кодировал эту оптимизацию, но это может быть идеей для еще большего повышения производительности.