从n中生成k个元素的“反灰色”按需组合的算法

Question

我正在尝试实现一种算法，从一组 n 个元素中获取 k 个元素的所有组合，其中两个连续组合之间的差异最大化（类似于反向格雷码）。换句话说，应该对组合进行排序以避免元素连续出现两次，这样就不会不必要地歧视任何元素。

理想情况下，该算法也不会预先计算所有组合并将它们存储到内存中，而是按需提供组合。我对此进行了广泛的搜索，并找到了一些详细的答案，例如/sf/answers/8949951/，但我似乎无法应用它。此外，该答案中链接的许多文章都是付费内容。

为了说明我的意思：

从一组 [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

谢谢

Answer 1

虽然我非常感谢 @tucuxi 和 @David Eisenstadt 的努力，但我发现哈密顿方法存在一些问题，即它没有解决 n 和 k 的某些值，并且某些元素也受到了不必要的歧视。

我决定尝试一下我的问题中列出的想法（点击计数表），它似乎给出了相当不错的结果。然而，该解决方案还需要生成后排序，这不能满足按需奖金要求。对于合理的 n 和 k 这应该是可行的。

不可否认，我发现我的算法有时似乎更倾向于导致一个元素连续出现的组合，这可能是可以调整的。但到目前为止，我的算法可能不如 tucuxi 的具体来说。然而，它确实为每个 n、k 提供了一个解决方案，并且似乎对元素的区分较少。

下面列出了我的代码。

再次感谢。

public class CombinationGenerator {
    private final int N;
    private final int K;
    private final int[] mCurrentCombination;

    public CombinationGenerator(int n, int k) {
        N = n;
        K = k;
        mCurrentCombination = new int[k];

        setElementSequence(0, 0);
        mCurrentCombination[K - 1]--; // fool the first iteration
    }

    private void setElementSequence(int startPos, int startValue) {
        for (int i = startPos; i < K; i++) {
            mCurrentCombination[i] = i + startValue - startPos;
        }
    }

    public int[] getNextCombination() {
        for (int i = K - 1; i >= 0; i--) {
            if (mCurrentCombination[i] < i + N - K) {
                setElementSequence(i, mCurrentCombination[i] + 1);
                return mCurrentCombination.clone();
            }
        }

        return null;
    }   
}

public class CombinationSorter {
    private final int N;
    private final int K;

    public CombinationSorter(int n, int k) {
        N = n;
        K = k;
    }

    public List<int[]> getSortedCombinations(List<int[]> combinations) {
        List<int[]> sortedCombinations = new LinkedList<int[]>();
        int[] combination = null;
        int[] hitCounts = new int[N]; // how many times each element has been
                                      // used so far

        // Note that this modifies (empties) the input list
        while (!combinations.isEmpty()) {
            int index = findNextCombination(combinations, hitCounts, combination);
            combination = combinations.remove(index);
            sortedCombinations.add(combination);

            addHitCounts(combination, hitCounts);
        }

        return sortedCombinations;
    }

    private int findNextCombination(List<int[]> combinations, int[] hitCounts,
            int[] previousCombination) {
        int lowestHitCount = Integer.MAX_VALUE;
        int foundIndex = 0;

        // From the remaining combinations, find the one with the least used
        // elements
        for (int i = 0; i < combinations.size(); i++) {
            int[] comb = combinations.get(i);
            int hitCount = getHitCount(comb, hitCounts);

            if (hitCount < lowestHitCount) {
                lowestHitCount = hitCount;
                foundIndex = i;
            } else if (hitCount == lowestHitCount
                    && previousCombination != null
                    && getNrCommonElements(comb, previousCombination) < getNrCommonElements(
                            combinations.get(foundIndex), previousCombination)) {
                // prefer this combination if hit count is equal but it's more
                // different from the previous combination in our sorted list
                // than what's been found so far (avoids consecutive element
                // appearances)
                foundIndex = i;
            }
        }

        return foundIndex;
    }

    private int getHitCount(int[] combination, int[] hitCounts) {
        int hitCount = 0;

        for (int i = 0; i < K; i++) {
            hitCount += hitCounts[combination[i]];
        }

        return hitCount;
    }

    private void addHitCounts(int[] combination, int[] hitCounts) {
        for (int i = 0; i < K; i++) {
            hitCounts[combination[i]]++;
        }
    }

    private int getNrCommonElements(int[] c1, int[] c2) {
        int count = 0;

        for (int i = 0; i < K; i++) {
            for (int j = 0; j < K; j++) {
                if (c1[i] == c2[j]) {
                    count++;
                }
            }
        }
        return count;
    }
}

public class Test {
    public static void main(String[] args) {
        final int n = 7;
        final int k = 3;

        CombinationGenerator cg = new CombinationGenerator(n, k);
        List<int[]> combinations = new LinkedList<int[]>();
        int[] nc;

        while ((nc = cg.getNextCombination()) != null) {
            combinations.add(nc);
        }

        for (int[] c : combinations) {
            System.out.println(Arrays.toString(c));
        }

        System.out.println("Sorting...");

        CombinationSorter cs = new CombinationSorter(n, k);
        List<int[]> sortedCombinations = cs.getSortedCombinations(combinations);

        for (int[] sc : sortedCombinations) {
            System.out.println(Arrays.toString(sc));
        }
    }

}

结果:

[0, 1, 2, 3]
[0, 4, 5, 6]
[1, 2, 3, 4]
[0, 1, 5, 6]
[2, 3, 4, 5]
[0, 1, 2, 6]
[3, 4, 5, 6]
[0, 1, 2, 4]
[0, 3, 5, 6]
[1, 2, 4, 5]
[0, 1, 3, 6]
[2, 4, 5, 6]
[0, 1, 3, 4]
[2, 3, 5, 6]
[0, 1, 4, 5]
[0, 2, 3, 6]
[1, 3, 4, 5]
[0, 2, 4, 6]
[1, 2, 3, 5]
[0, 1, 4, 6]
[0, 2, 3, 5]
[1, 2, 4, 6]
[1, 3, 5, 6]
[0, 2, 3, 4]
[1, 2, 5, 6]
[0, 3, 4, 5]
[1, 2, 3, 6]
[0, 2, 4, 5]
[1, 3, 4, 6]
[0, 2, 5, 6]
[0, 1, 3, 5]
[2, 3, 4, 6]
[1, 4, 5, 6]
[0, 1, 2, 5]
[0, 3, 4, 6]

结果:

[0, 1]
[2, 3]
[0, 4]
[1, 2]
[3, 4]
[0, 2]
[1, 3]
[2, 4]
[0, 3]
[1, 4]