从n中生成k个元素的 "anti-Gray"按需组合的算法

Question

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

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

为了说明我的意思:

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

根据@DavidEisenstat 的建议执行快速和肮脏的工作代码:

public static void main(String[] args) {
    ArrayList<int[]> all = new ArrayList<int[]>();
    // output is 0 if distance(i, j) != max, and 1 otherwise
    int[][] m = buildGraph(7, 4, all);
    HamiltonianCycle hc = new HamiltonianCycle();
    int path[] = hc.findHamiltonianCycle(m);
    if (path != null) {
        // I have no proof that such a path will always exist
        for (int i : path) {
            System.out.println(Arrays.toString(all.get(i)));
        }
    }
}

上述代码的输出 (7,4)；距离(作为长度 - size_of_intersection)始终为 3；尝试使用 4 会导致断开连接的图形:

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

缺少的代码位:

// uses JHH's code to build sequences, stores it in 'all'
public static int[][] buildGraph(int n, int k, ArrayList<int[]> all) {
    SequenceGenerator sg = new SequenceGenerator(n, k);
    int[] c;
    while ((c = sg.getNextCombination()) != null) {
        all.add(c.clone());         
    }
    int best = Math.min(n-k, k);
    System.out.println("Best is " + best);
    int matrix[][] = new int[all.size()][];
    for (int i=0; i<matrix.length; i++) {
        matrix[i] = new int[all.size()];
        for (int j=0; j<i; j++) {
            int d = distance(all.get(j), all.get(i));
            matrix[i][j] = matrix[j][i] = (d != best)? 0 : 1;
        }           
    }
    return matrix;
}

距离:(一点也不高效，但与哈密尔顿计算的成本相比相形见绌)

public static int distance(int[] a, int[] b) {
        HashSet<Integer> ha = new HashSet<Integer>();
        HashSet<Integer> hb = new HashSet<Integer>();
        for (int i=0; i<a.length; i++) {
                ha.add(a[i]);
                hb.add(b[i]);
        }
        ha.retainAll(hb);
        return a.length - ha.size();
}

为了找到汉密尔顿，我修改了 http://www.sanfoundry.com/java-program-find-hamiltonian-cycle-unweighted-graph/ 中的代码:

import java.util.Arrays;

public class HamiltonianCycle {

    private int V, pathCount;
    private int[] path;
    private int[] answer;
    private int[][] graph;

    public int[] findHamiltonianCycle(int[][] g) {
        V = g.length;
        path = new int[V];

        Arrays.fill(path, -1);
        graph = g;
        path[0] = 0;
        pathCount = 1;
        if (solve(0)) {
            return path;
        } else {
            return null;
        }
    }

    public boolean solve(int vertex) {
        if (graph[vertex][0] == 1 && pathCount == V) {
            return true;
        }
        if (pathCount == V) {
            return false;
        }

        for (int v = 0; v < V; v++) {
            if (graph[vertex][v] == 1) {
                path[pathCount++] = v;
                graph[vertex][v] = 0;
                graph[v][vertex] = 0;

                if (!isPresent(v)) {
                    if (solve(v)) {
                        answer = path.clone();
                        return true;
                    }
                }

                graph[vertex][v] = 1;
                graph[v][vertex] = 1;
                path[--pathCount] = -1;
            }
        }
        return false;
    }

    public boolean isPresent(int v) {
        for (int i = 0; i < pathCount - 1; i++) {
            if (path[i] == v) {
                return true;
            }
        }
        return false;
    }
}

请注意:对于大量组合，这将非常缓慢...