Home/

...

/

Introduction

Introduction

Real-world problems

The following are a few real-world problems that can be solved using the Subsets pattern.

Generate movie viewing orders

We want to offer marathons for our viewers. Each marathon will have a fixed set of movies catering to a specific taste. For a given marathon, different viewing orders of the movies will yield different user satisfaction results. We want to experiment (A/B testing) with different viewing orders of the same marathon.

Your task is to generate all the possible permutations of movies in a given marathon.

Let’s look at an example to understand this better:

Movie combinations of a genre

Suppose we have nn different movie genres like Action, Comedy, Family, Horror, and so on. In each genre, we have 00 to kk movies. We need to screen several movies of different genres in a specific sequence. For example, in the morning, we may want to feature a Family program, followed by a Comedy. Late at night, we may want to show Horror movies followed by Action movies. At prime time, we may want to use some other sequence.

Our task is to implement an algorithm that creates a combination of movies chosen from the given set of genres in a specific sequence.

Let’s say we have the following genres with the defined sequence of movies in each genre:

If we have the movies given in the example above and the input to our algorithm is ["Family", "Action"], then it should return the following list containing all of the possible combinations of a Family movie followed by an Action movie, chosen from the available data.

["Frozen;Iron Man;","Frozen;Wonder Woman;","Frozen;Avengers;","Kung fu Panda;Iron Man;","Kung fu Panda;Wonder Woman;","Kung fu Panda;Avengers;","Ice Age;Iron Man;","Ice Age;Wonder Woman;","Ice Age;Avengers;"]

Note: We add a semicolon (;) just to separate the movie names.

Dry-run templates

The following is the implementation of the solution provided for the String Permutations by changing case (medium) problem:

Press + to interact
Python 3.5
def find_letter_case_string_permutations(str):
  permutations = []
  permutations.append(str)
  # process every character of the string one by one
  for i in range(len(str)):
    if str[i].isalpha():  # only process characters, skip digits
      # we will take all existing permutations and change the letter case appropriately
      n = len(permutations)
      for j in range(n):
        chs = list(permutations[j])
        # if the current character is in upper case, change it to lower case or vice versa
        chs[i] = chs[i].swapcase()
        permutations.append(''.join(chs))
  return permutations
def main():
  print("String permutations are: " +
        str(find_letter_case_string_permutations("ad52")))
  print("String permutations are: " +
        str(find_letter_case_string_permutations("ab7c")))
main()

Students may be encouraged to run through the provided solution with the following sample inputs:

Sample input #1

str: a123b

Iteration No.

Line No.

str[i]

chs

permutations

-

3

-

-

['a123b']

1

6

a

-

['a123b']

1

10

a

a123b

['a123b']

1

12

a

A123b

['a123b']

1

13

a

A123b

['a123b', 'A123b']

2

6

1

-

['a123b', 'A123b']

3

6

2

-

['a123b', 'A123b']

4

6

3

-

['a123b', 'A123b']

5

6

b

-

['a123b', 'A123b']

5

10

b

a123b

['a123b', 'A123b']

5

12

b

a123B

['a123b', 'A123b']

5

13

b

a123B

['a123b', 'A123b', 'a123B']

5

10

b

A123b

['a123b', 'A123b', 'a123B']

5

12

b

A123B

['a123b', 'A123b', 'a123B']

5

13

b

A123B

['a123b', 'A123b', 'a123B', 'A123B']

Sample input #2

str: wxy1z

Students may be encouraged to complete the dry-run with this input:

Iteration No.

Line No.

str[i]

chs

permutations

-

3

-

-

[wxy1z]

1

6

w


[wxy1z]

1

10

w

wxy1z

[wxy1z]

1

12

w

Wxy1z

[wxy1z]

1

13

w

Wxy1z

['wxy1z', 'Wxy1z']

2

6

x

-

['wxy1z', 'Wxy1z']

2

10

x

wxy1z

['wxy1z', 'Wxy1z']

2

12

x

wXy1z

['wxy1z', 'Wxy1z']

2

13

x

wXy1z

['wxy1z', 'Wxy1z', 'wXy1z']

...

...

...

...

...

Trace generation

Press + to interact
Python 3.5
def find_letter_case_string_permutations(str):
  permutations = []
  permutations.append(str)
  print("Adding original string to list of permutations: ",permutations)
  # process every character of the string one by one
  for i in range(len(str)):
    print("Iteration: ",i+1)
    if str[i].isalpha():  # only process characters, skip digits
      print("\tGenerating permutations for the character: ",str[i])
      # we will take all existing permutations and change the letter case appropriately
      n = len(permutations)
      print("\tGenerating",n,"new permutation(s) using existing set of permutations: ",permutations)
      for j in range(n):
        print("\tIteration: ",j+1)
        chs = list(permutations[j])
        print("\t\tUsing permutation: ",permutations[j])
        # if the current character is in upper case, change it to lower case or vice versa
        chs[i] = chs[i].swapcase()
        print("\t\tgenerated permutation: ",''.join(chs))
        permutations.append(''.join(chs))
        print("\t\tList of permutations after adding newly generated permutation: ",permutations)
    else:
      print("\tSkipping digit: ",str[i])
  return permutations
def main():
  strs = ["a123b","wxy1z"]
  for s in strs:
    print("Finding permutations by changing case in the string:",s)
    permutations = find_letter_case_string_permutations(s)
    print("String permutations are: ",permutations)
    print("-"*100+"\n")
main()