I'm not sure how best to word this question, but given the word pineapple, and given it's syllables in an array like ["pine", "ap", "ple"], I need to find all the possible ways the word can be split by it's syllables. The function would produce the following result:

[["pineapple"], ["pine", "apple"], ["pine", "ap", "ple"], ["pineap", "ple"]]

I believe I've come across a very similar leetcode/algoexpert type question before, but can't seem to remember exactly what it was.

Note: the syllables must be in order so [“pineple”, “ap”] is not valid.

CodePudding user response：

Given N syllables of the word, there are N-1 positions between syllables. For each such position, you can decide whether to split the word there or join them together. There are 2^N-1 ways to make those choices, and each one will product a different partition of the word.

Here's a simple iterative way to make those choices by counting from 0 to 2^N-1 and using each bit in the current count to decide one split:

def splits(syls):
    if len(syls) < 2:
        return syls
    for count in range(1<<(len(syls)-1)):
        list = [syls[0]]
        for pos in range(1,len(syls)):
            if (count & (1<<(pos-1))) == 0:
                list[-1] =syls[pos]
            else:
                list.append(syls[pos])
        print(list)

splits(["pine", "ap", "ple"])

Output:

['pineapple']
['pine', 'apple']    
['pineap', 'ple']    
['pine', 'ap', 'ple']

CodePudding user response：

In python the spelling is ["pine", "ap", "ple"], but in TeX it would be spelled pine-ap-ple, same thing. The vector of three syllables suggests a vector of two punctuation marks, where the mark could be "-" hyphen or "" empty.

This is identical to a bit vector of length two. So we need merely count.

0. 00 --> "", "", or pineapple
1. 01 --> "", "-", or pineap-ple
2. 10 --> "-", "", or pine-apple
3. 11 --> "-", "-", or pine-ap-ple

You can see that with

for i in range(2 ** 2):
    print(f'{i:02b}')

Then it's just a matter of assembling the corresponding list.