Post History

66%

+2 −0

Python 3, 191 bytes lambda p:[c for c in chain(*[C(p,r)for r in range(len(p)+1)])if all(all(i==(sum(p.values())/2>=sum(p[n]for n in d))for d in C(c,len(c)-i))for i in[0,1])] from itertools imp...

posted 3y ago by Moshi‭ · edited 3y ago by Moshi‭

Answer

#2: Post edited by

Moshi‭ · 2021-10-04T23:08:57Z (about 3 years ago)
Added explanation

Copy Link

Raw

Markdown

# [Python 3], 191 bytes
```python
lambda p:[c for c in chain(*[C(p,r)for r in range(len(p)+1)])if all(all(i==(sum(p.values())/2>=sum(p[n]for n in d))for d in C(c,len(c)-i))for i in[0,1])]
from itertools import*;C=combinations
```
[Try it online!][TIO-kud95h9i]
[Python 3]: https://docs.python.org/3/
[TIO-kud95h9i]: https://tio.run/##lVBBTsMwEDw3r1jlUrsEaAqpUFC4RLwi5OA6SbtSYlu2WwmhXnkAT@QjIZuKkiJx4GBrZ3Z2djXm1e@0uuub7KVvRbepBJi0kNBoCxJQgdwJVGxR5MxElhNtibZCbWvW1ooZfhXzkmMDom0ZPcwy5vYdMzcH0e5rxzi/XT1lI1WokjwUeVR89KuozpmMyE3yazzRONDFMopLXgaN1R2gr63XunWAndHWLx7zTOpug0p41Mr1vnbeQQZFMHs7RsMXKqF0mMIqOcEDElhGED53QjoC8Z@d5aUF9UZVnExU8erXorPqfqJ6GOptXaEf6vXFQLz@78DPHdNrk8lAcgzKIKAIKRAKdwwmDWbGovKMEP8G88/3j3kEzYk907z/Ag "Python 3 – Try It Online"

# [Python 3], 191 bytes
```python
lambda p:[c for c in chain(*[C(p,r)for r in range(len(p)+1)])if all(all(i==(sum(p.values())/2>=sum(p[n]for n in d))for d in C(c,len(c)-i))for i in[0,1])]
from itertools import*;C=combinations
```
[Try it online!][TIO-kud95h9i]
Yay for quadruple nested list compressions...
## Explanation
First we take the powerset:
```
lambda p:[c for c in chain(*[C(p,r)for r in range(len(p)+1)])
```
Then we filter.
```python
if all(all(i==(sum(p.values())/2>=sum(p[n]for n in d))for d in C(c,len(c)-i))
for i in[0,1])]
from itertools import*;C=combinations # Imports and aliases
```
There's a neat little trick: we want to have the set sum greater than `s/2` (the average), while having the `n-1` sized subsets' sums less than or equal to `s/2`. By realizing that the full set is equal to the `n` sized subset, we can combine both of them:
```text
n subset > s/2 and n-1 subset <= s/2
```
is equivalent to
```text
(n subset <= s/2) == 0 and (n-1 subset <= s/2) == 1
```
is equivalent to
```text
(n-i subset <= s/2) == i) for i in [0,1]
```
[Python 3]: https://docs.python.org/3/
[TIO-kud95h9i]: https://tio.run/##lVBBTsMwEDw3r1jlUrsEaAqpUFC4RLwi5OA6SbtSYlu2WwmhXnkAT@QjIZuKkiJx4GBrZ3Z2djXm1e@0uuub7KVvRbepBJi0kNBoCxJQgdwJVGxR5MxElhNtibZCbWvW1ooZfhXzkmMDom0ZPcwy5vYdMzcH0e5rxzi/XT1lI1WokjwUeVR89KuozpmMyE3yazzRONDFMopLXgaN1R2gr63XunWAndHWLx7zTOpug0p41Mr1vnbeQQZFMHs7RsMXKqF0mMIqOcEDElhGED53QjoC8Z@d5aUF9UZVnExU8erXorPqfqJ6GOptXaEf6vXFQLz@78DPHdNrk8lAcgzKIKAIKRAKdwwmDWbGovKMEP8G88/3j3kEzYk907z/Ag "Python 3 – Try It Online"

#1: Initial revision by

Moshi‭ · 2021-10-04T22:57:41Z (about 3 years ago)

Copy Link

Raw

Markdown

# [Python 3], 191 bytes

```python
lambda p:[c for c in chain(*[C(p,r)for r in range(len(p)+1)])if all(all(i==(sum(p.values())/2>=sum(p[n]for n in d))for d in C(c,len(c)-i))for i in[0,1])]
from itertools import*;C=combinations
```

[Try it online!][TIO-kud95h9i]

[Python 3]: https://docs.python.org/3/
[TIO-kud95h9i]: https://tio.run/##lVBBTsMwEDw3r1jlUrsEaAqpUFC4RLwi5OA6SbtSYlu2WwmhXnkAT@QjIZuKkiJx4GBrZ3Z2djXm1e@0uuub7KVvRbepBJi0kNBoCxJQgdwJVGxR5MxElhNtibZCbWvW1ooZfhXzkmMDom0ZPcwy5vYdMzcH0e5rxzi/XT1lI1WokjwUeVR89KuozpmMyE3yazzRONDFMopLXgaN1R2gr63XunWAndHWLx7zTOpug0p41Mr1vnbeQQZFMHs7RsMXKqF0mMIqOcEDElhGED53QjoC8Z@d5aUF9UZVnExU8erXorPqfqJ6GOptXaEf6vXFQLz@78DPHdNrk8lAcgzKIKAIKRAKdwwmDWbGovKMEP8G88/3j3kEzYk907z/Ag "Python 3 – Try It Online"

Communities

Post History