Sequentially select parts of a string similar to ngram

Question

Here is the problem I am trying to solve.

For example there is this string

my_string = 'jan feb mar'

And I want to have sequentially generated items like this in a list. It is always true that the words in a string are splittable with ' '.

my_function(my_string)
output = ['jan', 'jan feb', 'jan mar', 'jan feb mar', 'feb','feb mar','mar']

What I tried is below and it is not what I want.

my_string = "jan feb mar"
words_list = my_string.split(' ')
words = [' '.join(words_list[i:i+n]) for i in range(len(words_list) - n+1)]
words.extend(input_list)

Please help me out here. Thanks.

`itertools.combinations` does [something similar with a different order](https://stackoverflow.com/questions/8371887/making-all-possible-combinations-of-a-list). Do you need to return a generator or is a list acceptable? — ggorlen, May 30 '20 at 04:07
@komatiraju Yes, the order matters when making the strings. for example 'jan' cannot be after 'feb' or 'mar' and 'feb' cannot be after 'mar' so, 'feb mar jan' is not valid in the output list. — minjunkim7767, May 30 '20 at 04:11
Just for info, as you asked me in the other post, I've add an answer, In fact this a classic "All combinations of all length" so I've add it down there — azro, May 30 '20 at 07:42

score 2 · Answer 1 · answered May 30 '20 at 04:51

A nice way to think about these combinations is a counting in binary. Given a list like ['jan', 'feb', 'mar'] you can think of each of your selections as being masked by a binary number. For example 110 would correspond to jan feb. Since you are looking for all the combinations you can simply count from 1 to the number of combinations and use the binary number to mask the selection. This makes for a very succinct solution:

words  = 'jan feb mar'.split()

def all_sets(words):
    l = len(words)
    for n in range(1, 2**l):
        binstring = format(n, f'0{l}b')[::-1]
        yield " ".join([word for flag, word in zip(binstring, words) if int(flag)])

list(all_sets(words))
# ['jan', 'feb', 'jan feb', 'mar', 'jan mar', 'feb mar', 'jan feb mar']

BernieFeynman · Accepted Answer · 2020-05-30T04:17:31.507

1

How about something like this? Just create a lookup for sorting

import itertools 

def my_function(my_string):
    def subsets(s): 
      output = []
      for i in range(1,len(s)+1):
        output +=  list(itertools.combinations(s, i))
      return output



    my_list = my_string.split()
    my_order = {val:ind for ind,val in enumerate(my_list)}
    print(my_order)
    output =  subsets(my_list)
    output = [' '.join(sorted(list(i), key=my_order.get)) for i in output]
    return output
my_string = 'jan feb mar' 
output = my_function(my_string)

print(output)

edited May 30 '20 at 04:17

answered May 30 '20 at 04:07

BernieFeynman

121
7

This works well for my purpose. Thanks a lot! Although when I pass 'jan' only it gave me an empty list while what I need is ['jan'] – minjunkim7767 May 30 '20 at 04:16

score 1 · Answer 3 · answered May 30 '20 at 07:41

What you want is all combinations of all size (1, 2 and 3), combinations keeps order (permutations does the combination in every order)

from itertools import combinations
print(list(combinations(my_string.split(' '), r=1))) # [('jan',), ('feb',), ('mar',)]
print(list(combinations(my_string.split(' '), r=2))) # [('jan', 'feb'), ('jan', 'mar'), ('feb', 'mar')]
print(list(combinations(my_string.split(' '), r=3))) # [('jan', 'feb', 'mar')]

Now you need to do them automatically, so loop on the number of items in the input, and join each word

from itertools import combinations, chain

# pythonic way
def my_function(values):
    items = my_string.split(" ")
    return list(chain([' '.join(c) for i in range(1,1+len(items)) for c in combinations(items, r=i)]))

# loop way
def my_function(values):
    items = my_string.split(" ")
    result = []
    for i in range(1,1+len(items)):
      comb = combinations(items, r=i)
      result.extend(' '.join(c) for c in comb)
    return result

chain is flatten the list of list in one list

`CODE DEMO`

score 0 · Answer 4 · answered May 30 '20 at 04:17

using permutations

from itertools import permutations as per
res = []
my_string = 'jan feb mar'
l = my_string.split()
for i in range(len(l)):
    res.extend(list(per(l, i+1)))

res = [' '.join(i) for i in res]
print(res)

output

['jan', 'feb', 'mar', 'jan feb', 'jan mar', 'feb jan', 'feb mar', 'mar jan', 'mar feb', 'jan feb mar', 'jan mar feb', 'feb jan mar', 'feb mar jan', 'mar jan feb', 'mar feb jan']

score 0 · Answer 5 · answered May 30 '20 at 20:54

Mark's way is best in my opinion, but here's another take on it for good measure. This works with the normal combinations of any length algorithm with a nested loop on the results to reorganize the output according to OP's spec. I'm returning a generator but most of the work is unfortunately up front.

I also moved the string manipulation to the caller. I don't see any reason to return anything but tuples which is a more flexible format than strings for this use case. The caller can always join the tuples as shown below (or do other useful things that serialization might prevent).

import itertools

def all_combs(L):
    combinations = [list(itertools.combinations(L, i + 1)) for i in range(len(L))]

    for i in range(len(L)):
        for j in range(len(combinations) - i):
            for comb in combinations[j][i+i*j:i+j+1]:
                yield comb

if __name__ == "__main__":
    print(list(map(" ".join, all_combs("jan feb mar".split()))))

Output:

['jan', 'jan feb', 'jan mar', 'jan feb mar', 'feb', 'feb mar', 'mar']

Sequentially select parts of a string similar to ngram

5 Answers5

`CODE DEMO`

Linked