# set_includes (string subsequence-containment) in Python 2

I've implemented C++'s std::includes algorithm in Python, so that I can use it to efficiently implement a Scrabble "can I make this word" function:

def word_can_be_made_from_rack(word, rack):
return set_includes(sorted(rack), sorted(word))


Here's the implementation, with some test cases:

def set_includes(haystack, needle):
j = 0
hn = len(haystack)
for c in needle:
while j != hn and haystack[j] < c:
j += 1
if j == hn:
return False
if haystack[j] > c:
return False
j += 1
return True

assert set_includes('abcdef', 'af')
assert set_includes('abcdef', 'bce')
assert set_includes('abcdef', 'abcdef')
assert set_includes('aaaaa', 'a')
assert set_includes('aaaaa', 'aa')
assert set_includes('aaaaax', 'ax')
assert set_includes('abbbcxx', 'abc')


This is similar to Find if one list is a subsequence of another except that it assumes (and requires) that the two input strings are sorted.

The manual management of index j in this code doesn't feel very Pythonic. Am I missing an easier way to write this algorithm?

itertools one-liners will be accepted as answers, especially if they're more performant. :)

• AFNP. The loop condition j != hn is more idiomatically expressed as an exception:

try:
for c in needle:
while haystack[j] < c:
....
except IndexError:
return False

• No naked loops. Factor the while haystack[j] < c: into a function. Among other benefits, it'd allow

    j = search_character(haystack[j:], c)

• The binary search for c seems more performant than linear. See bisect module.

• AFNP? Do you mean EAFP? – 301_Moved_Permanently Jul 18 '19 at 15:57
• @MathiasEttinger Same (Ask Forgiveness, Not Permission). – vnp Jul 18 '19 at 16:12

I had an idea to just try to make the word by removing all the needed characters from the rack/haystack and see if it works. The idea also follows the "Easier to ask for forgiveness than permission" approach.

def set_includes(haystack, needle):
haystack = list(haystack)
try:
for char in needle:
haystack.remove(char)
return True
except ValueError:
return False


Obviously, this will scale badly for cases where haystack == needle for larger string lengths (noticeable starting at about n >= 500), but it does not need sorting. So you will have to check whether or not this is more efficient for your use case.

Depending on how often the check would return false because needle does contain one or more letters that are not on the rack, sets can maybe help you to take a shortcut:

if set(haystack).issuperset(needle):
# check if there are enough letters to build needle from haystack
...
else:
# haystack does not contain all the letters needed to build needle
return False


Just for fun: We here in Python have iterators, too :-D

def set_includes(haystack, needle):
it1 = iter(haystack)
it2 = iter(needle)
char2 = next(it2)
while True:
try:
char1 = next(it1)
except StopIteration:
return False
if char2 < char1:
return False

if not char1 < char2:
try:
char2 = next(it2)
except StopIteration:
return True


If you move the last try: ... catch ...: a few levels outwards, you can get quite close to the structure of the possible implementation given on cppreference. Don't take this to serious though.

We can do a little bit better:

def set_includes(haystack, needle):
it2 = iter(needle)
char2 = next(it2)
for char1 in haystack:
if char2 < char1:
return False

if not char1 < char2:
try:
char2 = next(it2)
except StopIteration:
return True

return False


Here, at least one of the try: ... catch ...:s is transformed into a proper loop.

## Use str.index()

The lines:

    while j != hn and haystack[j] < c:
j += 1


are basically trying to find the index of c in haystack. So just use str.index():

def set_includes(haystack, needle):
try:
i = -1
for c in needle:
i = haystack.index(c, i+1)

except ValueError:
return False

return True


Or, if you prefer use str.find():

def set_includes(haystack, needle):
i = -1
for c in needle:
i = haystack.find(c, i+1)
if i<0:
return False
return True


### itertools one-liner

from itertools import groupby