Summary:

Let's say that I have got a bag of letters (a multiset), how many unique sets can I make at the same time? Multiple of the same letter can exist in the bag of letters and each instance can only be used once. (once a set as been made, the letter instances that compose it cannot be used again). Order of characters in the set does not matter.

There are two cases I am interested in.

1. The bag contains one of each letter
2. The bag contains the same amounts (a constant k > 1) of each letter.

I know that for case 1, I can make a maximum total of n unique sets (each set has only one letter) where n is the amount of different letters in the bag. How would I approach case 2? I need an algorithm to give me the list of sets when it is maximized.

Case 2 example:

Given: {a, a, a, a, b, b} Answer: [{a}, {b}, {ab}]. {a,a} is an invalid set (has duplicates) and so is not included.

Given: {a, a, b} Answer: [{a}, {b}]. {a} is the remainder. It is invalid because {a} already exists in the list.

Motivation:

In the popular video game Minecraft, there is a device called an encoder that takes an item and encodes it to a unique redstone code for use in encoded storage systems. It works by doing the equivalent of a contains(item) operation on multiple containers. Depending on which containers contain the item, different 'codes' are generated. However, since the largest container in the game (a double chest) has only 54 slots, it can only hold up to 54 different items. As a smaller encoder with less chests is desired, the encoder must be smart about how it maps the codes to fully leverage all the inventory spaces in the machine with a small footprint.

This application is equivalent to case 2a of the above. Consider each chest as a character, and a code as a set. Since each chest has 54 slots we model this situation with a bag of letters with 54 duplicate letters of each character. Given n chests, we would have n * 54 letters in the bag. The goal is to find the maximum amount of unique sets possible from a certain number of chests n.

CodePudding user response：

Is there a counterexample to the following greedy algorithm? First we build nCr(n, 1), then nCr(n, 2), then nCr(n, 3)...etc. until we run out of letters.

Each set constructed is necessarily distinct from the previous ones, and since we're growing by one element each time, we exhaust the possibilities for each set size, consuming as little letters as possible.

CodePudding user response：

1. Convert the bag of letters to a Set - unique elements

2. Use combinations or find out the combinations by using loops

   l = list(input().split())
   cl = list(set(l)) 
   for i in range(len(cl)):
      for j in range(i 1,len(cl) 1):
         print(cl[i:j])