Generating all ordered substrings of a string

[Thorsten Kampe]

* girish at it.usyd.edu.au (2006-07-11 10:20 +0000)
>  I want to generate all non-empty substrings of a string of length >=2.
> Also,
> each substring is to be paired with 'string - substring' part and vice
> versa.
>  Thus, ['abc'] gives me [['a', 'bc'], ['bc', 'a'], ['ab', 'c'], ['c',
> 'ab'], ['b', 'ac'], ['ac', 'b']] etc.
>  Similarly, 'abcd' should give me [['a', 'bcd'], ['bcd', 'a'], ['abc',
> 'd'], ['d', 'abc'], ['b', 'acd'], ['acd', 'b'],['c', 'abd'], ['abd', 'c'],
> ['ab', 'cd'], ['cd', 'ab'], ['bc', 'ad'], ['ad', 'bc'], ['ac',
> 'bd'],['bd','ac']]

No, you don't want to generate all substrings, you want to generate
all partions of a given set with length 2:

filter(lambda x: len(x) == 2, part(['abcd']))

I've written an utility that generates all possible partions of a set;
the "pairing" as you call it, is trivial, so you can do it yourself

def part(seq):
    import copy
    partset = [[]]
    for item in seq:
        newpartset = []
        for partition in partset:
            for index in range(len(partition)):
                newpartset.append(copy.deepcopy(partition))
                newpartset[-1][index].append(item)
            partition.append([item])
            newpartset.append(partition)
        partset = newpartset
    return partset