Let $n$ be size of set of items and in $m$ trials $k$ items are selected from the set without replacement. In two different trials the same items can be selected. How should items be selected so that the number of items selected in two different trials have as few items in common as possible? I.e. let $T_x$ be the set of items selected in trial $x$, then select the items in each trial so that the sum of overlap between every pair of selections $$ \sum_{1 \le i < j \le m} | T_i \cap T_j | $$ is minimized. The order in which the items are picked doesn't matter, the only significant thing is whether or not the same item was picked in two different trials.
If $m \le \frac{n}{k}$ then the trivial answer is to select different items in each trial. And the maximizing the sum is easy as well $-$ simply select the same items in every trial.
In the interesting case where $m > \frac{n}{k}$ I think I have a solution but it is only a hunch and I'm unable to prove that the selection algorithm leads to a global minimum. The general idea is that you should attempt to share as few items as possible and attempt to avoid selecting the same set of items as was done in an earlier trial. For simplicity let's assume that $k \mid n$ so that $w=\frac{n}{k} \in \mathbb{N}$. It goes like this:
- Trials are placed in groups of size $w$ such that each selected item during a trial is not found in any other trial in the same group.
- There are $n!$ permutations for distributing the items over $w$ trials such that no item is shared between any two trials. Select items for the trials $T_{11}, T_{12}, \dots, T_{1w}$ in any way you want to form the first group $G_1$. The size of the intersection of any of these trial selections is zero.
- It's now possible to create $w$ trials from the first one by selecting one item from $T_{11}$, one from $T_{12}$, and so on such that no item is shared among these trials. This forms the second group $G_2$, and trials in this group share one item which each trial of the first, i.e. $\forall a,b \,\,\,|T_{1a} \cap T_{2b}| = 1$, but none with items within the group $|T_{xa} \cap T_{xb}| = 0, a \ne b \wedge x \in \{1, 2\}$.
- In fact, it's possible to create $k-1$ groups related to the first one such that each trial within a group share no items, but trials with the related groups share one item. Let us call these $k$ groups a family.
At this point it is possible to start from another permutation in step 2 and create $k$ related groups. These trials within a group share no items among each other, shares 1 item with each trial in the other groups in the family, but shares $0 - k$ items with trials in every group in the first family, and $\frac{k}{w}$ items on average with trials in other families.
Further families of items can be created until you've made $m$ trials in total. In the last family and group you form you want to choose the trials that share the fewest items with earlier trials.
If there are more trials $m$ than $n!$ repeat the above and make duplicates until you've got enough.
How would I go about to prove or disprove that this leads to a minimum? Is it sometimes better to form groups of items that share a few items? Is a brute force greedy algorithm going to end up with the same (or better) result? That make things simpler when $k \nmid m$.