How would one write an efficient algorithm for determining whether a set of words can be arranged into a palindrome sentence?

Question

There's no end to the leetcode questions about finding palindrome pairs and how to determine if a given string is a palindrome, but I can't seen to find any discussion about sentence palindrome testing for unordered words. (Every word must be used in the palindrome for the function to return true)

For instance, on the input:

["stop", "nine", "rum", "myriad", "put", "up", "rum", "dairymen", "murmur", "in", "pots"]

the function would return True, and on:

["sit", "on", "potato", "pan", "otis"]

it would return False.

A naive solution in Python would be to useitertools.permutations(words, len(words)) to check every possible solution, but as word count grows, I believe this is at least O(n!*c) with n words and c characters.

Heap's algorithm doesn't seem to particularly lend itself well to the problem, because a way of generating half of the permutations and short circuiting all the "children" permutations that have the same outer configuration when the first and last words don't start palindromic, doesn't really make itself obvious.

However with the Steinhaus–Johnson–Trotter algorithm, it seems there is a nice delineation at the halfway point in which the permutations repeat essentially in reverse. However I can't think of a way to efficiently "short circuit" cases we don't need to check past that. Perhaps there is some way to skip inversion numbers based off of what cases can be ruled out?

Edit: Here's an example that would be quite hard to crack:

['1', '10', '11', '100', '101', '110', '111', '1000', '1001', '1010', '1011', '1100', '1101', '1110', '1111', '10000', '10001', '10010', '10011', '10100', '10101', '10110', '10111', '11000', '11001', '11010', '11011', '11100', '11101', '11110', '11111', '100000', '100001', '100010', '100011', '100100', '100101', '100110', '100111', '101000', '101001', '101010', '101011', '101100', '101101', '101110', '101111', '110000', '110001', '110010', '110011', '110100', '110101', '110110', '110111', '111000', '111001', '111010', '111011', '111100', '111101', '111110', '111111', '1000000', '1000001', '1000010', '1000011', '1000100', '1000101', '1000110', '1000111', '1001000', '1001001', '1001010', '1001011', '1001100', '1001101', '1001110', '1001111', '1010000', '1010001', '1010010', '1010011', '1010100', '1010101', '1010110', '1010111', '1011000', '1011001', '1011010', '1011011', '1011100', '1011101', '1011110', '1011111', '1100000', '1100001', '1100010', '1100011', '1100100']

As there are about 10^157 permutations. But more reasonably:

['1', '10', '11', '100', '101', '110', '111', '1000', '1001', '1010', '1011', '1100', '1101', '1110', '1111', '10000', '10001', '10010', '10011', '10100', '10101', '10110', '10111']

would return False but

['1', '10', '11', '100', '101', '110', '111', '1000', '1001', '1010', '1011', '1100', '1101', '1110', '1111', '10000', '10001', '10010', '10011', '10100', '10101', '10110']

would return True, as this palindrome exists:

["1000", "1100", "110", "10100", "10011", "11", "1010", "1101", "1011", "1110", "10000", "10", "1111", "10110", "1", "10101", "111", "100", "10010", "101", "1001", "10001"]

Answer 1

This one does some preprocessing of prefixes, which helps matching as we build from the outer ends in, adding to the side that has less characters. The idea is that each proper prefix of the middle (which belongs to either the right or left side) must match a whole word to be added to the other side; or that the complete middle must be a prefix of the word we'll add to the other side.

Python code. Can find the palindromes of the "reasonable" True example, but the trouble is affirming that a palindrome cannot be found.

Python code:

import collections

LOG = False

def is_palindrome(w):
    return w == w[::-1]

def in_index_set(idx, index_set):
    return bool((1 << idx) & index_set)

def f(words):
    print(words)
    words_r = collections.defaultdict(list)
    words_l =collections.defaultdict(list)
    prefixes_r = collections.defaultdict(list)
    prefixes_l = collections.defaultdict(list)
    for i, w in enumerate(words):
        words_r[w].append(i)
        words_l["".join(reversed(w))].append(i)
        for j in range(len(w)):
            prefixes_r[w[:j+1]].append(i)
            prefixes_l["".join(reversed(w[-j:]))].append(i)

    results = []
    stack = []

    for w in words_r:
        i = words_r[w][0]
        stack.append(([], [i], 0, len(w), len(words) - 1, 1 << i))
        stack.append(([i], [], len(w), 0, len(words) - 1, 1 << i))

    while (stack):
        left, right, len_l, len_r, count, index_set = stack.pop()

        if LOG:
            print(list(map(lambda x: words[x], left)), list(map(lambda x: words[x], reversed(right))), len_l, len_r, count, index_set)

        diff = len_l - len_r
        if LOG:
            print(f"diff: {diff}")
        middle = ""
        if diff > 0:
            i = len(left) - 1
            while diff > 0:
                to_remove = min(diff, len(words[left[i]]))
                middle = words[left[i]][-to_remove:] + middle
                diff -= to_remove
                i -= 1
        elif diff < 0:
            i = len(right) - 1
            while diff < 0:
                to_remove = min(-diff, len(words[right[i]]))
                middle += words[right[i]][:to_remove]
                diff += to_remove
                i -= 1

        if count == 0 and is_palindrome(middle):
            results.append((left, list(reversed(right))))
            #print(f"palindrome: {list(map(lambda x: words[x], left)), list(map(lambda x: words[x], reversed(right)))}")
            continue

        if LOG:
            print(f"middle: {middle}")

        if len_l == len_r:
            for w in words_r:
                for i in words_r[w]:
                    if in_index_set(i, index_set):
                        continue
                    stack.append((left + [i], right, len_l + len(w), len_r, count - 1, (1 << i) | index_set))
                    stack.append((left, right + [i], len_l, len_r + len(w), count - 1, (1 << i) | index_set))
                    break

        # For each proper prefix of 'middle', match a whole word
        # And each word 'middle' is a prefix of is a match, too

        elif len_l > len_r:
            for i in range(1, len(middle)):
                prefix = middle[:i]
                if LOG:
                    print(f"prefix: {prefix}")
                for j in words_l[prefix]:
                    if in_index_set(j, index_set):
                        continue
                    if LOG:
                        print(f"words_l j: {j} {words[j]}")
                    stack.append((left, right + [j], len_l, len_r + len(words[j]), count - 1, (1 << j) | index_set))
                    break
            for i in prefixes_l[middle]:
                if in_index_set(i, index_set):
                    continue
                stack.append((left, right + [i], len_l, len_r + len(words[i]), count - 1, (1 << i) | index_set))

        else:
            for i in range(1, len(middle)):
                prefix = middle[-i:]
                if LOG:
                    print(f"prefix: {prefix}")
                for j in words_r[prefix[::-1]]:
                    if in_index_set(j, index_set):
                        continue
                    if LOG:
                        print(f"words_r j: {j} {words[j]}")
                    stack.append((left + [j], right, len_l + len(words[j]), len_r, count - 1, (1 << j) | index_set))
                    break
            for i in prefixes_r[middle[::-1]]:
                if in_index_set(i, index_set):
                    continue
                stack.append((left + [i], right, len_l + len(words[i]), len_r, count - 1, (1 << i) | index_set))

    return results

words = ["stop", "nine", "rum", "myriad", "put", "up", "rum", "dairymen", "murmur", "in", "pots"]
#words = ['1', '10', '11', '100', '101', '110', '111', '1000', '1001', '1010', '1011', '1100', '1101', '1110', '1111', '10000', '10001', '10010', '10011', '10100', '10101', '10110']
#words = ['1', '10', '11', '100', '101', '110', '111', '1000', '1001', '1010', '1011', '1100', '1101', '1110', '1111', '10000', '10001', '10010', '10011', '10100', '10101', '10110', '10111']

_f = f(words)
print(_f)
for t in _f:
    print("".join(map(lambda x: words[x], t[0] + t[1])))

Answer 2

Here's an approach to solving this problem.
Note: This approach is based on the following assumptions:

• A palindrome word pair must be formed from two words of same length
• A palindrome sentence can only be formed from whole words from the list

1.  organize the entries in the incoming list into a dictionary where the k = len of words and  the value is a list of words.  Note this can be done in time O(n)  
2.  For each key in the dictionary:
    a. starting with index = 0, compare inverse of the word to contents of index + 1 to           index=len(values) -1
       if a n equality is found:
          return True
       else:
          increment index and repeat a
 3. If all keys have have been searched, return False  

The following is a simple implementation of this approach:

from collections import defaultdict
def isPalindromeSentence(word_list: list[str])-> bool:
    # return True if a palindrome sentence can be formed from word_list
    optsDict = defaultdict(list)
    for wrd in word_list:
        optsDict[len(wrd)].append(wrd)
    for k, vl in optsDict.items():
        if len(vl) > 1:
            for i in range(1, len(vl)):
                if vl[i-1][::-1] in vl[i:]:
                    return True                                      
    return False  

  

Answer 3

Okay, I have been schooled into what constitutes a palindrome sentence and see as @n.m. rightfully pointed out my original solution solved a totally different problem. So Here is a more sophisticated solution to the problem.

If we assume a word list for a palindrome sentence adheres to the following:

1. Words included in the sentence must be in the list without alteration
2. The palindrome is formed by the sequence of letters forming the sentence with capitalization, spaces and punctuation ignored.
3. All words in word_list must be included in the sentence.

then lists such as the following will result in a True result:

['011', '11', '10'] -> '0111110',
['Sit',  'on',  'a',  'potato', 'pan', 'Otis'] -> 'sitonapotatopanotis',
['Ah', 'Satan', 'sees', 'Natasha'] -> 'ahsatanseesnatasha',
['Cigar', 'Toss', 'it', 'in', 'a', 'can', 'It', 'is', 'so', 'tragic'] -> 'cigartossitinacanitissotragic'

From the above we observe the following characteristics:

1. the first letter = the last letter, the second letter = the second from last letter etc.
2. If we select a word option from word_list, we can eliminate from consideration as the last word any word_list entries that don't contain the same letters as the first word when indexed backwards. Note: If the last word selected is shorter than the first word only letters in last word need to be equal, If the last word is longer than the first word, only letters if first word need to equate.

With the above as a guide the algorithm would follow as:

1. select word from word_list to act a the lead phrase
2. create new list try_list which has the selected word removed.
3. create a data container which contains the lead_phrase, an empty tail_phrase, and the remaining words to check.
4. push the data container onto a fifo queue.
5. Once all words in word_list have been pushed onto queue as the lead_phrase.
6. While queue has an entry: a. pop a data container from the queue. b. if the remaining word list is empty:
   • combine the lead phrase with the tail phrase and test for palindrome
   • if a palindrome return true, else drop the data container c. when remaining word_list is not empty
   • determine if we should add a lead phrase or a tail phrase
   • select a candidate word from the list, if it exists.
   • create a new data container which contains the updated lead phrase, tail phrase and the remianing word list
   • push the data container onto the queue
   • repeat step 6
7. If queue is empty, return False

The following code implements the above algorithm

from dataclasses import dataclass, field
from typing import Optional  

def extractItem(inList: list, indx: int) -> list:
    # return inList with item at indx removed
    return inList[:indx]+inList[indx+1:]  

def isPalindrome(wrd_list: list[str]) -> bool:
    # return True if wrd_list can be organized as a palindrome
    for i in range(len(wrd_list)):
        wrd_list[i] = wrd_list[i].lower()
    que = []
    for i in range(len(wrd_list)):
        ps = PaliStruct(frtEnd=wrd_list[i],
                        bckEnd='',
                        toTry=extractItem(wrd_list, i))
        que.append(ps)
    while que:
        ps = que.pop(0)   # pop the que entry
        if ps.toTry:
            for i in range(len(ps.toTry)):
                Lead_Phrase = ps.frtEnd
                Tail_Phrase = ps.bckEnd
                if len(ps.frtEnd) >= len(ps.bckEnd):
                    # Adding to Tail_Phrase
                    Tail_Phrase = ps.toTry[i] + Tail_Phrase
                else:
                    # Adding to Lead_Phrase
                    Lead_Phrase += ps.toTry[i]
                tstIndx = min(len(Lead_Phrase), len(Tail_Phrase))
                if Lead_Phrase[:tstIndx] == Tail_Phrase[::-1][:tstIndx]:
                    # found a candidate
                    px = PaliStruct(frtEnd=Lead_Phrase,
                                    bckEnd=Tail_Phrase,
                                    toTry=extractItem(ps.toTry, i))
                    que.append(px)

        else:
            sntc = ps.frtEnd + ps.bckEnd
            if sntc == sntc[::-1]:   # Test for palindrome solution
                return True
    else:
        return False  

The following tests were used to validate the accuracy of this solution:

tst1 = ['011', '11', '10']
tst1a = ['10', '011', '11']
tst1b = ['10', '011', '11', '010']
tst2 = ['Cigar', 'Toss', 'it', 'in', 'a', 'can', 'It', 'is', 'so', 'tragic']
tst2a = ['tragic', 'so', 'is', 'It', 'can', 'a', 'in', 'it', 'Toss', 'Cigar']
tst2b = ['tragic', 'so', 'is', 'It', 'can', 'a', 'it', 'Toss', 'Cigar']
tst3 = ['Sit',  'on',  'a',  'potato', 'pan', 'Otis']
tst3a = ['potato', 'a', 'on', 'Otis', 'pan', 'Sit']
tst3b = ['potato', 'a', 'on', 'alpha', 'Otis', 'pan', 'Sit']
tst4 = ['Ah', 'Satan', 'sees', 'Natasha']
tst4a = ['Ah', 'Natasha', 'Satan','sees']
tst4b = ['sees', 'Natasha', 'Satan']  

Note all tests of form xxxb produce a False return, while all others produce True returns using the following:

testCases = [tst1, tst1a, tst1b, tst2, tst2a, tst2b, tst3, tst3a, tst3b, tst4, tst4a, tst4b] 
for x, test in enumerate(testCases):
    print(f'Test {x}: Input: {test} -> {isPalindrome(test)}')  

Which produces the following output:

Test 0: Input: ['011', '11', '10'] -> True
Test 1: Input: ['10', '011', '11'] -> True
Test 2: Input: ['10', '011', '11', '010'] -> False
Test 3: Input: ['Cigar', 'Toss', 'it', 'in', 'a', 'can', 'It', 'is', 'so', 'tragic'] -> True
Test 4: Input: ['tragic', 'so', 'is', 'It', 'can', 'a', 'in', 'it', 'Toss', 'Cigar'] -> True
Test 5: Input: ['tragic', 'so', 'is', 'It', 'can', 'a', 'it', 'Toss', 'Cigar'] -> False
Test 6: Input: ['Sit', 'on', 'a', 'potato', 'pan', 'Otis'] -> True
Test 7: Input: ['potato', 'a', 'on', 'Otis', 'pan', 'Sit'] -> True
Test 8: Input: ['potato', 'a', 'on', 'alpha', 'Otis', 'pan', 'Sit'] -> False
Test 9: Input: ['Ah', 'Satan', 'sees', 'Natasha'] -> True
Test 10: Input: ['Ah', 'Natasha', 'Satan', 'sees'] -> True
Test 11: Input: ['sees', 'Natasha', 'Satan'] -> False

Answer 4

With the help of everybody here I had attempted to find a fast solution for the binary counting case (OEIS A291633), but even verifying up to 22 takes quite a while even with some third party libraries. I think I'd need to make even more improvements, but for the time being I've given up on this one, as it's much more difficult than I originally realized!

But here's my code, there may be some bugs, but it returns correct results for my test domain:

import cProfile
import marisa_trie
from bitarray import bitarray


def can_mid(midlen, midstr, midpos):
    if midpos % 2 == 0:  # even
        normal_index = midpos // 2
        i = 0
        while i < midlen - normal_index and i < normal_index:
            if midstr[i + normal_index] != midstr[normal_index - i - 1]:
                return False
            i += 1
        return True
    else:  # odd
        normal_index = (midpos - 1) // 2
        i = 0
        while i < midlen - normal_index - 1 and i < normal_index:
            if midstr[i + normal_index + 1] != midstr[normal_index - i - 1]:
                return False
            i += 1
        return True


def split_mid(midstr, midpos):
    if midpos % 2 == 0:  # even
        normal_index = midpos // 2
        return midstr[normal_index:], midstr[:normal_index], ""
    else:  # odd
        normal_index = (midpos - 1) // 2
        return midstr[normal_index+1:], midstr[:normal_index], midstr[normal_index]


def test(n):
    if n == 1:
        return True
    lookup = ["{0:b}".format(i) for i in range(n+1)]
    lenlookup = [len("{0:b}".format(i)) for i in range(n+1)]
    revlookup = [lookup[i][::-1] for i in range(n+1)]
    numbers = [i for i in range(1, n+1)]
    tumbers = [(i,) for i in range(1, n+1)]
    strings = [lookup[i] for i in numbers]
    revstrings = [revlookup[i] for i in numbers]
    fmt = "<H"
    trie = marisa_trie.RecordTrie(fmt, zip(strings, tumbers))
    revtrie = marisa_trie.RecordTrie(fmt, zip(revstrings, tumbers))
    used = bitarray(n+1)
    used.setall(0)
    for midnum in numbers:
        for midnum_midpos in range(lenlookup[midnum] * 2 + 1):
            if not can_mid(lenlookup[midnum], lookup[midnum], midnum_midpos):
                continue
            forward, backward, midchar = split_mid(lookup[midnum], midnum_midpos)
            # print("midnum: {}{}{}".format(backward, "|{}|".format(midchar) if len(midchar) else "|", forward))
            used.setall(0)
            used[midnum] = True
            stack = []
            while True:
                forward_len = len(forward)
                backward_len = len(backward)
                if forward_len < backward_len:
                    build_front = True
                    prefix = backward[-forward_len-1:-1-backward_len:-1]
                elif backward_len < forward_len:
                    build_front = False
                    prefix = forward[backward_len:forward_len]
                else:
                    prefix = ""
                    build_front = True

                if build_front:
                    to_try = trie.items(prefix)
                else:
                    to_try = revtrie.items(prefix)

                for record in to_try:
                    if not used[record[1][0]]:
                        used_copy = used.copy()
                        used_copy[record[1][0]] = True
                        if used_copy.count(1) >= n:
                            if build_front:
                                if forward_len + lenlookup[record[1][0]] == backward_len:
                                    return True
                            else:
                                if forward_len == backward_len + lenlookup[record[1][0]]:
                                    return True

                        else:
                            if build_front:
                                stack.append((forward + record[0], backward, used_copy))
                            else:
                                stack.append((forward, lookup[record[1][0]] + backward, used_copy))

                if len(stack) == 0:
                    break
                forward, backward, used = stack.pop()
    return False


def failfast(n):  # lookup table of n such that the binary digit counts are both odd
    if n in [4, 6, 16, 18, 28, 30, 64, 66, 76, 78, 84, 86, 88, 90]:
        return False
    return True


def main():
    startn = 1
    maxn = 100
    for n in range(startn, maxn):
        if failfast(n):
            permutation = test(n)
            if permutation:
                print("found one! {}, {}".format(n, permutation))
            else:
                print(n)
        else:
            print("skipping {}".format(n))


if __name__ == '__main__':
    # cProfile.run("main()")
    main()

I had originally attempted to start at the ends of the palindrome, but that made checking the end conditions (in the middle) quite complicated, as you don't want to check the entire palindrome for correctness, since it is constructed to be correct from the beginning. Looking back, one could do some index arithmetic to grab the remaining "middle chunk" by shaving off a bit from the "other side" and check it for correctness. Or something else clever (and add all sorts of lookaheads).

But the algorithm here is as follows:

1. construct forward and backward tries of the words (storing the integer corresponding to the string in an associated record for lookups)
2. construct a bitarray of size n+1 (0 is left unused as a tradeoff between space and indexing performance) to determine what numbers have been used in the stackframe
3. loop through each word and "possible midpoint" of each word, and attempt to construct a palindrome with that midpoint by:
4. grabbing forward or backward words from the trie depending on which side needs more characters
5. constructing a stack frame from each valid candidate word (taken from the used bitarray and appropriate trie, and pushing them to the stack
6. popping a stackframe (breaking if there are none left, returning false after we've tried every word and pos as the midpoint), and continuing until we have a valid palindrome.

My asymptotic analysis of python programs is a bit lacking (not sure what's going on behind the scenes sometimes), but I think this is maybe >O((mn)!), for m max word length and n number of words.

I think attacking from the outside has a little bit better asymptotic complexity, as you don't have to iterate through every word's midpoint with starting position, but do one check at the end for every O(n!) combinations (although come to think of it, checking the "middle chunk" is O(m), maybe bringing it back to >O((mn)!) again.

And nothing I've seen here seems to break free of the factorial complexity, so rather than learn c and optimize the hell out this O(n!) I've decided to move on for a bit. Perhaps a Monte Carlo solution would be a fun way to search the higher space for solutions (but not necessarily prove that palindromes don't exist for a given n). It seems that solutions are abundant when they exist!