# Best split with conditions

Given this sort of dataset:

ID Score1 P1 Flag
id1 0.01 0.2 False
id2 0.99 0.9 True
... ... ... ...

The limitations of each variable are:

• ID: identifier if each object, unique in the table
• Score1: A number between 0 and 1, that represent the value of the object
• P1: probability of call, betwen 0 and 1
• Flag: should the object be in group <b?

I want to split the dataset in 2 groups (A and B) given the rules:

• The sum of P1 on group A should be at least n
• The sum of P1 on group B should be at least m
• The diference between the average Score1 in the two groups should be minimal
• The average of Score1 on all the selected (group A + group B) should be maximum
• We don't have to select all the rows
• Rows with Flag = True can not be in group A

How can I do this in a smart/fast way?

There is no efficient algorithm to do what you want, unless P=NP. In fact, there is no efficient algorithm to even decide whether a feasible partition of the dataset into two groups exists.

You can see this by reducing from the partition problem: Given a (multi-)set of positive numbers $$X=\{x_1, x_2, \dots, x_n\}$$ we want to decide whether there exists a subsets $$S$$ of $$X$$ such that $$\sum_{s \in S} s= \frac{1}{2} \sum_{x \in X} x$$. Without loss of generality we can assume that $$0 < x_i \le 1$$ (by simply dividing all $$x_i$$ by $$\max_{i=1, \dots, n} x_i$$).

Then, for each $$x_i \in X$$ you can create a row in your dataset with:

• ID = $$i$$;
• Score = $$0$$;
• P1 = $$x_i$$;
• Flag = false.

Finally, pick $$n = m = \frac{1}{2}\sum_{x \in X} x$$.

A feasible parition into two groups $$A$$ a and $$B$$ induces a subset $$S$$ such that $$\sum_{s \in S} s= \frac{1}{2} \sum_{x \in X} x$$. Specifically if $$i_1, i_2, \dots, i_k$$ are the IDs of the rows selected into $$A$$, you can define $$S = \{x_{i_1}, x_{i_2}, \dots, x_{i_k}\}$$.

Conversely, given a set $$S = \{x_{i_1}, x_{i_2}, \dots, x_{i_k}\}$$ such that $$\sum_{s \in S} s= \frac{1}{2} \sum_{x \in X} x$$, you can select $$A$$ as the set of rows with IDs in $$\{i_1, i_2, \dots, i_k\}$$ and $$B$$ as the set of rows not in $$A$$.