理想情况下,该算法还不会预先计算并将所有组合存储到内存中,而是按需提供组合。 我已经广泛搜索了这个问题,并找到了一些详细的答案,例如https://dev59.com/9nVC5IYBdhLWcg3w-mVO#127856,但我似乎无法应用它。此外,那篇答案中链接的许多文章都是付费内容。
为了说明我的意思:
从[0, 1, 2, 3, 4]的集合中找到所有由两个元素组成的组合。 使用一个简单的算法,该算法尝试递增最右侧的元素,直到不再可能,然后向左移动,递增前一个数字等等,我得到以下结果:
[0, 1]
[0, 2]
[0, 3]
[0, 4]
[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]
我使用以下Java代码生成此结果:
public class CombinationGenerator {
private final int mNrElements;
private final int[] mCurrentCombination;
public CombinationGenerator(int n, int k) {
mNrElements = n;
mCurrentCombination = new int[k];
initElements(0, 0);
// fake initial state in order not to miss first combination below
mCurrentCombination[mCurrentCombination.length - 1]--;
}
private void initElements(int startPos, int startValue) {
for (int i = startPos; i < mCurrentCombination.length; i++) {
mCurrentCombination[i] = i + startValue - startPos;
}
}
public int[] getNextCombination() {
for (int i = 0; i < mCurrentCombination.length; i++) {
int pos = mCurrentCombination.length - 1 - i;
if (mCurrentCombination[pos] < mNrElements - 1 - i) {
initElements(pos, mCurrentCombination[pos] + 1);
return mCurrentCombination;
}
}
return null;
}
public static void main(String[] args) {
CombinationGenerator cg = new CombinationGenerator(5, 2);
int[] c;
while ((c = cg.getNextCombination()) != null) {
System.out.println(Arrays.toString(c));
}
}
}
我希望每个连续的组合都尽可能与前一个不同,这并不是我想要的。目前,元素“1”连续出现了四次,然后再也没有出现。对于这个特定的例子,一种解决方案是:
[0, 1]
[2, 3]
[0, 4]
[1, 2]
[3, 4]
[0, 2]
[1, 3]
[2, 4]
[0, 3]
[1, 4]
我确实成功地为这个特定的案例实现了此结果,方法是在生成组合后应用排序算法,但这并不能满足我的要求,因为整个组合集必须一次性生成,然后进行排序并保留在内存中。我不确定它是否适用于任意的k和n值。最后,我非常确定这不是最有效的方法,因为排序算法基本上循环遍历组合集,试图找到一个与前一个组合不共享元素的组合。我还考虑过为每个元素保留一个“命中计数”的表,并使用它来始终获取包含最低组合命中计数的下一个组合。
我的某种经验性结论是,如果n>2k,则可能避免元素在两个连续的组合中完全出现。否则,至少应该避免元素连续出现两次等。
你可以将这个问题类比于使用标准循环赛制(例如足球比赛)来实现k = 2的情况,但我需要一种适用于任意k值的解决方案。我们可以将其想象成某种游戏的锦标赛,其中有n名选手要在一组比赛中与所有其他选手对抗,每场比赛有k名选手参加。尽可能让选手不必连续参加两场比赛,但也不应在两次比赛之间等待过长时间。请给出如何使用可靠的排序算法进行后期处理或者最好是按需解决此问题的任何指导!
注意:通常假设n <= 50,k <= 5。
谢谢!