Set Exercises 2

Nelson

3/2/2020

library(reticulate)
## Warning: package 'reticulate' was built under R version 3.5.3

Review

Consider Problem 4 on page 48 of the finite mathematics text. Write the code which generates all 256 possible strings which can be made using the letters of “STOP”. Place them in a list named “words”. Print the list and its length.

Answer

words = []
for l1 in "STOP":
    for l2 in "STOP":
        for l3 in "STOP":
            for l4 in "STOP":
                word = l1 + l2 + l3 + l4
                words.append(word)
print(words)
## ['SSSS', 'SSST', 'SSSO', 'SSSP', 'SSTS', 'SSTT', 'SSTO', 'SSTP', 'SSOS', 'SSOT', 'SSOO', 'SSOP', 'SSPS', 'SSPT', 'SSPO', 'SSPP', 'STSS', 'STST', 'STSO', 'STSP', 'STTS', 'STTT', 'STTO', 'STTP', 'STOS', 'STOT', 'STOO', 'STOP', 'STPS', 'STPT', 'STPO', 'STPP', 'SOSS', 'SOST', 'SOSO', 'SOSP', 'SOTS', 'SOTT', 'SOTO', 'SOTP', 'SOOS', 'SOOT', 'SOOO', 'SOOP', 'SOPS', 'SOPT', 'SOPO', 'SOPP', 'SPSS', 'SPST', 'SPSO', 'SPSP', 'SPTS', 'SPTT', 'SPTO', 'SPTP', 'SPOS', 'SPOT', 'SPOO', 'SPOP', 'SPPS', 'SPPT', 'SPPO', 'SPPP', 'TSSS', 'TSST', 'TSSO', 'TSSP', 'TSTS', 'TSTT', 'TSTO', 'TSTP', 'TSOS', 'TSOT', 'TSOO', 'TSOP', 'TSPS', 'TSPT', 'TSPO', 'TSPP', 'TTSS', 'TTST', 'TTSO', 'TTSP', 'TTTS', 'TTTT', 'TTTO', 'TTTP', 'TTOS', 'TTOT', 'TTOO', 'TTOP', 'TTPS', 'TTPT', 'TTPO', 'TTPP', 'TOSS', 'TOST', 'TOSO', 'TOSP', 'TOTS', 'TOTT', 'TOTO', 'TOTP', 'TOOS', 'TOOT', 'TOOO', 'TOOP', 'TOPS', 'TOPT', 'TOPO', 'TOPP', 'TPSS', 'TPST', 'TPSO', 'TPSP', 'TPTS', 'TPTT', 'TPTO', 'TPTP', 'TPOS', 'TPOT', 'TPOO', 'TPOP', 'TPPS', 'TPPT', 'TPPO', 'TPPP', 'OSSS', 'OSST', 'OSSO', 'OSSP', 'OSTS', 'OSTT', 'OSTO', 'OSTP', 'OSOS', 'OSOT', 'OSOO', 'OSOP', 'OSPS', 'OSPT', 'OSPO', 'OSPP', 'OTSS', 'OTST', 'OTSO', 'OTSP', 'OTTS', 'OTTT', 'OTTO', 'OTTP', 'OTOS', 'OTOT', 'OTOO', 'OTOP', 'OTPS', 'OTPT', 'OTPO', 'OTPP', 'OOSS', 'OOST', 'OOSO', 'OOSP', 'OOTS', 'OOTT', 'OOTO', 'OOTP', 'OOOS', 'OOOT', 'OOOO', 'OOOP', 'OOPS', 'OOPT', 'OOPO', 'OOPP', 'OPSS', 'OPST', 'OPSO', 'OPSP', 'OPTS', 'OPTT', 'OPTO', 'OPTP', 'OPOS', 'OPOT', 'OPOO', 'OPOP', 'OPPS', 'OPPT', 'OPPO', 'OPPP', 'PSSS', 'PSST', 'PSSO', 'PSSP', 'PSTS', 'PSTT', 'PSTO', 'PSTP', 'PSOS', 'PSOT', 'PSOO', 'PSOP', 'PSPS', 'PSPT', 'PSPO', 'PSPP', 'PTSS', 'PTST', 'PTSO', 'PTSP', 'PTTS', 'PTTT', 'PTTO', 'PTTP', 'PTOS', 'PTOT', 'PTOO', 'PTOP', 'PTPS', 'PTPT', 'PTPO', 'PTPP', 'POSS', 'POST', 'POSO', 'POSP', 'POTS', 'POTT', 'POTO', 'POTP', 'POOS', 'POOT', 'POOO', 'POOP', 'POPS', 'POPT', 'POPO', 'POPP', 'PPSS', 'PPST', 'PPSO', 'PPSP', 'PPTS', 'PPTT', 'PPTO', 'PPTP', 'PPOS', 'PPOT', 'PPOO', 'PPOP', 'PPPS', 'PPPT', 'PPPO', 'PPPP']
print(len(words))
## 256

Avoid Repetition 1

The author’s hint indicated that there were only 24 strings. This follows from a constraint we did not impose in the code above. The constraint is that a letter can occur only once in a string.

There are at least two ways we could modify the code above to impose this constraint.

One method is to check each string generated by the crude algorithm and see if it satisfies the constraint before appending it to the list. Write code to impose the constraint this way and call the resulting list “words1”. Print the list and its length.

Answer

words1 = []
for l1 in "STOP":
    for l2 in "STOP":
        for l3 in "STOP":
            for l4 in "STOP":
                word = l1 + l2 + l3 + l4
                
                # Checking code
                count = 0
                for i in "STOP":
                    if i in word:
                        count = count + 1
                if count == 4:
                    words1.append(word)
print(words1)
## ['STOP', 'STPO', 'SOTP', 'SOPT', 'SPTO', 'SPOT', 'TSOP', 'TSPO', 'TOSP', 'TOPS', 'TPSO', 'TPOS', 'OSTP', 'OSPT', 'OTSP', 'OTPS', 'OPST', 'OPTS', 'PSTO', 'PSOT', 'PTSO', 'PTOS', 'POST', 'POTS']
print(len(words1))
## 24

Avoid Repetition 2

An alternative method is to reduce the set of letters available to successive levels of the nested for loops. Write code which uses this method and use it to produce a list named words2. Print this list and its length.

words2 = []
wset = set(list("STOP"))
for l1 in wset:
    for l2 in wset - {l1}:
        for l3 in wset - {l1, l2}:
            for l4 in wset - {l1, l2, l3}:
                word = l1 + l2 + l3 + l4
                words2.append(word)
print(words2)
## ['TPSO', 'TPOS', 'TSPO', 'TSOP', 'TOPS', 'TOSP', 'PTSO', 'PTOS', 'PSTO', 'PSOT', 'POTS', 'POST', 'STPO', 'STOP', 'SPTO', 'SPOT', 'SOTP', 'SOPT', 'OTPS', 'OTSP', 'OPTS', 'OPST', 'OSTP', 'OSPT']
print(len(words2))
## 24

Comparison

Both of these methods seem to have worked. Are the two lists really equivalent? Write code to answer this question.

Answer

set(words1) == set(words2)
## True