A search over every subset
Nested loops suit a candidate made of a fixed number of choices. In many problems a candidate is instead a group of the items, of any size: the apples that go into one bag, the coins used for a payment, the tasks we decide to take on. Such a group is a subset of the items, and items have subsets, because each item is either in the group or out of it. The next problem is a search of this kind.
You have apples with known weights. Divide them into two groups so that the difference between the groups' total weights is as small as possible, and print that difference.
The first input line holds , and the second holds the weights .
Constraints
Sample · Input
5 3 2 7 4 1
Output
1
In the sample the weights add up to 17, an odd number, so the two groups cannot weigh the same and a difference of 1 is the best possible. The groups and reach it.
No simple rule finds the best division in general. Giving each apple in turn to the lighter group, for example, divides the weights 3, 3, 2, 2, 2 into groups of 7 and 5, although against is an even split. The limit says we do not need a rule. A division is fixed by the set of apples in the first group, since the others go to the second, so there are at most divisions, and a program can try every one.
Three apples could be handled by three nested loops, each choosing a group for one apple. But the number of apples is read from the input, and the number of nested loops in a program cannot depend on its input. So we number the subsets instead, and a single loop over the numbers visits every subset.
Number the subsets with bit masks
Number the items from 0 to . A bit mask, or mask for short, is an integer whose binary digits record which items a subset contains: bit of the mask is 1 when item is in the subset and 0 when it is not. Bits are counted from the right, so bit 0 is the last digit of the binary number.
With five items, for example, the subset that holds items 0 and 3 has this mask:
01001, with a 1 under item 3 and under item 0.In a binary number the bit in place counts for , so this mask is the number . In the other direction, every number from 0 to can be written with bits, and its bits say which items are in.
For three items, numbered 0, 1 and 2, the eight numbers from 0 to 7 give these subsets:
| Mask | In binary | Items in the subset |
|---|---|---|
| 0 | 000 | none |
| 1 | 001 | 0 |
| 2 | 010 | 1 |
| 3 | 011 | 0, 1 |
| 4 | 100 | 2 |
| 5 | 101 | 0, 2 |
| 6 | 110 | 1, 2 |
| 7 | 111 | 0, 1, 2 |
Each of the eight subsets is in exactly one row, and the same holds for any number of items: a loop over the numbers from 0 to visits every subset exactly once.
Read one bit of a mask
A program stores the mask as an ordinary integer and works on its bits with three operators:
1 << nshifts the number 1 left by places, which gives . The loop over the masks runs from 0 up to, and not including,1 << n.mask >> ishifts the mask right by places, so that bit of the mask becomes bit 0 of the result.x & 1is bit 0 ofx. The operator&compares two numbers bit by bit and keeps a 1 only where both have a 1, and the number 1 has a 1 in place 0 alone.
Put together, (mask >> i) & 1 is bit of the mask: 1 when item is in the subset and 0 when it is not. For the mask 5, which is 101, it gives 1, 0 and 1 for , so items 0 and 2 are in and item 1 is out. The Bit manipulation lesson covers these operators in full.
Turn each mask into a division of the apples
In Apple Division, bit of the mask says where apple goes: 1 for the first group, 0 for the second. The program only has to add up the first group. If that group weighs and all the apples together weigh , the second group weighs , and the difference between the groups is
The sample has . Two of its 32 masks are drawn below, with apple 0 on the right, under bit 0:
Mask 6 is the division given under the card, against . Every division is in fact visited twice, because exchanging the two groups flips every bit: mask 9, 01001, and mask 22, 10110, are the same division. That doubles the work and cannot change the minimum, so we leave it.
Step through the masks
The demo runs the loop on the sample. Each chip is an apple, drawn under its bit. Next moves to the following mask, and clicking a chip flips its bit. The best difference so far drops to 1 at mask 6 and stays there up to mask 31.
Try every division
The program loops over the masks. For each one it adds up the weights whose bits are 1 and keeps the smallest difference it has seen:
def minimum_difference(weights):
n = len(weights)
total = sum(weights)
best = total
for mask in range(1 << n):
selected = 0
for i in range(n):
if (mask >> i) & 1:
selected += weights[i]
best = min(best, abs(total - 2 * selected))
return best
n = int(input())
weights = list(map(int, input().split()))
print(minimum_difference(weights))On the sample the program prints 1. best starts at the total weight, which is the difference for mask 0, where the first group is empty. The answer is correct because every division has a mask and the loop goes through every mask, so the smallest difference it has seen at the end is the smallest there is.
The cost of the mask loop
- Time
- The inner loop reads bits for each of the masks. For 20 apples that is bit checks.
- Memory
besides the input - The loop keeps the mask, one sum and the best difference. No subset is stored.
A loop written in Python runs roughly simple operations a second, and by that budget bit checks are too many for one second. The budget is rough. On our laptop the program took between 0.7 and 1.0 seconds for 20 apples, depending on the Python version, which is still too close to the one-second limit of CSES to rely on. Submit the same code as PyPy3, which CSES also offers and which runs such loops several times faster.
Worked example
The loop on other inputs
The trace runs the same loop on other lists of weights. With a single apple the best division leaves one group empty. With the weights 4, 1 and 3 the two groups can be equal, and the answer is 0. For seven apples the trace shows only the masks that improve the best difference.
5 items give 2^5 = 32 ways to split them. Mask m puts item i in group A when bit i of m is 1. Every mask is shown.
- total
- 17
Change the example input
Current result: 1
The mask loop is one way to go through every division. A recursive function is another, in which each call decides where one apple goes. In every division apple 0 is either in the first group or in the second, and in both cases the other apples are divided between the groups in some way. So a function that puts apple 0 in the first group and calls itself to divide apples 1 to , and then puts apple 0 in the second group and calls itself again, reaches every division.
Unlike a set of nested loops, the depth of these calls is not written into the program, so the same function works for any number of apples. The later calls need only two facts about the decisions already made: which apple comes next, and the weight of the first group so far. Which apples make up that weight does not matter to them. When no apple is left, the division is complete and the call computes .
The calls form a binary tree in which each level decides one apple. After levels there are calls at the bottom, one for each division, and about calls in all. A call does a fixed amount of work besides calling itself, so the search takes time. The mask loop takes instead, because it adds up the first group again for every mask.
In Python the difference shows: for 20 apples the recursion took about 0.1 seconds on our machine, against 0.7 for the mask loop. The mask loop has an advantage of its own. It gives every subset a number, and the Bitmask DP lesson uses those numbers as indices to store a value for each subset.
A search over every ordering
In a subset only membership matters. In other problems every candidate uses all the items, and the candidates differ in their order: the order in which to visit some places, to run some tasks, or to write some letters. An ordering of the items is called a permutation. The first place can take any of the items, the second any of the that remain, and so on, so different items have permutations. The next problem asks for all of them.
You get a string of lowercase letters. List every different string that uses exactly the same letters, rearranged.
The input is the string on one line. Print the number of different strings, then each string on its own line in alphabetical order.
Constraints
- , where is the length of the string
Sample · Input
aabac
Output
20 aaabc aaacb aabac aabca aacab aacba abaac abaca abcaa acaab acaba acbaa baaac baaca bacaa bcaaa caaab caaba cabaa cbaaa
With at most 8 letters there are at most orderings, so listing them is fast. The sample has a repeated letter, though. The string aabac has 5 letters, and its 5 positions have orderings, but the expected output has only 20 strings, because exchanging two of the a's gives another ordering of the positions and the same string. The three a's can be arranged among themselves in ways, so each string is spelled by 6 orderings. A program that goes through the orderings of the positions has to drop these repeats, and the number of strings that remain is
The strings must be printed in alphabetical order, which is also called lexicographic order. Two strings of the same length are compared at the first place where they differ: aabac comes before aabca because the first three letters agree and the fourth is a in one and c in the other.
List the different strings
Python's itertools.permutations(s) produces every ordering of the positions of s, each as a tuple of letters, so aabac gives 120 tuples. The program joins each tuple into a string and collects the strings in a set, which keeps one copy of each. sorted then puts them in alphabetical order:
def creating_strings(s):
return sorted(set("".join(p) for p in permutations(s)))
strings = creating_strings(input())
print(len(strings))
print("\n".join(strings))On the sample the program prints 20 and then the 20 strings. The set throws away 100 of the 120 orderings here. That waste is acceptable at this size: even 8 letters give only 40,320 tuples.
Orderings as candidates
Creating Strings asks for the orderings themselves. In other problems an ordering is a candidate to check, as a pair or a subset was earlier: the program loops over every ordering of the items, computes something from each, and keeps the best one or counts those that pass.
The loop is for order in permutations(items):, and order is a tuple that holds the items in one order.
A check that reads the whole ordering takes about steps, so the work is . That is about steps for 10 items and for 11, so at about operations a second a search over orderings fits only up to about 10 items. Writing such a search by hand, one place at a time, is part of the Backtracking lesson.
Common subset and permutation mistakes
Starting
bestat 0.- Where it breaks
- For the single weight 5, no division has a difference below 0, so
bestnever changes and the function returns 0 instead of 5. - The fix
- Start from the total weight, which is the difference when one group is empty.
Testing a bit with
(mask & (1 << i)) == 1.- Where it breaks
mask & (1 << i)keeps bit of the mask in its own place, so its value is when the bit is set, and that equals 1 only for . The test sees apple 0 and no other, and the program prints 11 for the sample instead of 1.- The fix
- Compare with 0, as in
(mask & (1 << i)) != 0, or test(mask >> i) & 1.
Counting orderings of positions when the question counts strings.
- Where it breaks
aabachas 120 orderings of its positions and only 20 different strings, so a program that prints every ordering prints each string 6 times.- The fix
- Keep one copy of each string, for example in a set, or use a method that produces each string once.
Recall How many masks does the loop go through for 12 items, and which items are in the subset with mask 37?
It goes through masks, from 0 to 4,095. In binary 37 is 100101, which is , so bits 0, 2 and 5 are set and the subset holds items 0, 2 and 5.