Github user facaiy commented on the issue:
https://github.com/apache/spark/pull/19666
Hi, I write a demo with python. I'll be happy if it could be useful.
For N bins, say `[x_1, x_2, ..., x_N]`, since all its splits contain either
`x_1` or not, so we can choose the half splits which doesn't contain x_1 as
left splits.
If I understand it correctly, the left splits are indeed all combinations
of the left bins, `[x_2, x_3, ... x_N]`. The problem can be solved by the
[backtracking algorithm](https://en.wikipedia.org/wiki/Backtracking).
Please correct me if I'm wrong. Thanks very much.
```python
#!/usr/bin/env python
def gen_splits(bins):
if len(bins) == 1:
return bins
results = []
partial_res = []
gen_splits_iter(1, bins, partial_res, results)
return results
def gen_splits_iter(dep, bins, partial_res, results):
if partial_res:
left_splits = partial_res[:]
right_splits = [x for x in bins if x not in left_splits]
results.append("left: {:20}, right: {}".format(str(left_splits),
right_splits))
for m in range(dep, len(bins)):
partial_res.append(bins[m])
gen_splits_iter(m+1, bins, partial_res, results)
partial_res.pop()
if __name__ == "__main__":
print("first example:")
bins = ["a", "b", "c"]
print("bins: {}\n-----".format(bins))
splits = gen_splits(bins)
for s in splits:
print(s)
print("\n\n=============")
print("second example:")
bins = ["a", "b", "c", "d", "e"]
print("bins: {}\n-----".format(bins))
splits = gen_splits(bins)
for s in splits:
print(s)
```
logs:
```bash
~/Downloads â¯â¯â¯ python test.py
first example:
bins: ['a', 'b', 'c']
-----
left: ['b'] , right: ['a', 'c']
left: ['b', 'c'] , right: ['a']
left: ['c'] , right: ['a', 'b']
=============
second example:
bins: ['a', 'b', 'c', 'd', 'e']
-----
left: ['b'] , right: ['a', 'c', 'd', 'e']
left: ['b', 'c'] , right: ['a', 'd', 'e']
left: ['b', 'c', 'd'] , right: ['a', 'e']
left: ['b', 'c', 'd', 'e'], right: ['a']
left: ['b', 'c', 'e'] , right: ['a', 'd']
left: ['b', 'd'] , right: ['a', 'c', 'e']
left: ['b', 'd', 'e'] , right: ['a', 'c']
left: ['b', 'e'] , right: ['a', 'c', 'd']
left: ['c'] , right: ['a', 'b', 'd', 'e']
left: ['c', 'd'] , right: ['a', 'b', 'e']
left: ['c', 'd', 'e'] , right: ['a', 'b']
left: ['c', 'e'] , right: ['a', 'b', 'd']
left: ['d'] , right: ['a', 'b', 'c', 'e']
left: ['d', 'e'] , right: ['a', 'b', 'c']
left: ['e'] , right: ['a', 'b', 'c', 'd']
```
---
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
