算法生成＆QUOT;防灰＆QUOT;从n个k个元素按需组合 [英] Algorithm for generating "anti-Gray" on-demand combinations of k elements from n

问题描述

我想实现一个算法来获得k个元素的所有组合出一套n个元素，其中连续两个组合之间的差异最大化的（一种使反向灰色codeS）。换言之，该组合要责令避免从连续出现两次的元素，并且从而没有元件被不必要地鉴别

I'm trying to implement an algorithm to get all combinations of k elements out of a set of n elements where the difference between two consecutive combinations are maximized (so kind of reverse Gray codes). In other words, the combinations should be ordered to avoid elements from appearing twice in a row, and so that no element is unnecessarily discriminated.

理想地，该算法也将不会$ P $对 - 计算所有组合，并将它们存储到存储器，而是提供的组合上的需求。 我寻觅广泛，这和发现了一些详细的解答，如 http://stackoverflow.com/a/127856/1226020，但我似乎无法适用于此。此外，许多在这个问题的答案链接的文章支付的内容。

Ideally, the algorithm would also NOT pre-calculate all combinations and store them into memory, but rather deliver combinations on demand. I have searched extensively for this and found a few detailed answers such as http://stackoverflow.com/a/127856/1226020, but I can't seem to apply this. Also, many of the articles linked in that answer are paid content.

要说明我的意思：

从一组[0，1，2，3，4]，发现两种元素的所有组合。 用一个简单的算法，试图增加最右边的元素，直到不再可能，然后向左移动，递增previous位数等，我得到如下结果：

From a set of [0, 1, 2, 3, 4], find all combinations of two elements. Using a simple algorithm that tries to increment the right-most element until no longer possible, then moving left, incrementing the previous digit etc, I get the following results:

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

我产生这样的结果与下面的Java code：

I produce this result with the following Java code:

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));
        }
    }

}

这是不是我想要的，因为我希望每个连续的组合是尽可能不同的previous之一。目前，元素1出现四次在一排，然后永远不再。对于此特定实例，一种解决方案将是：

This is not what I want, because I want each consecutive combination to be as different as possible from the previous one. Currently, element "1" appears four times in a row, and then never again. For this particular example, one solution would be:

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

我确实设法完成此结果对于该特定生成情况下，通过施加组合后的分拣algoritm，但这并不满足我的按需组合代的要求，因为整个集的组合，必须在一旦产生，然后分类并保存在存储器。我不知道它适用于任意的k和n值，无论是。最后，我是pretty的肯定它不是最有效的方式排序算法通过一系列的组合，试图找到一个共享的previous组合没有元素基本循环。我也算是保留了命中计数的每一个元素，并用它来总是包含最低的组合命中计数的下一个组合的表。 我的有些经验的结论是，将有可能避免从完全出现在两个连续的组合如果n> 2k个元素。否则，它应该至少能够避免出现在一个行等的两倍以上的元素

I have indeed managed to accomplish this result for this particular case by applying a sorting algoritm after the combinations are generated, but this does not fulfill my requirement of on-demand combination generation as the entire set of combinations has to be generated at once, then sorted and kept in memory. I'm not sure it works for arbitrary k and n values either. And finally, I'm pretty sure it's not the most efficient way as the sorting algorithm basically loops through the set of combinations trying to find one sharing no elements with the previous combination. I also considered keeping a table of "hit counts" for each element and use that to always get the next combination containing the lowest combined hit count. My somewhat empirical conclusion is that it will be possible to avoid elements from completely appearing in two consecutive combinations if n > 2k. Otherwise, it should at least be possible to avoid elements from appearing more than twice in a row etc.

您可以比较这个问题是什么来实现对于k = 2使用的足球比赛等标准循环方案，但我需要为k的任意值的解决方案。我们可以想象这是某种游戏的比赛，我们有n个球员是对所有其他球员的发挥一组比赛，每场比赛保持ķ球员。玩家应尽量不用打两连胜，同时也应该不必等待过长两场比赛出场的。

You could compare this problem to what is achieved for k = 2 using a standard round-robin scheme for football games etc, but I need a solution for arbitrary values of k. We can imagine this to be a tournament of some sort of game where we have n players that are to play against all other players in a set of games, each game holding k players. Players should as far as possible not have to play two games in a row, but should also not have to wait unnecessarily long between two game appearances.

在如何解决这个无论是与一个可靠的排序算法后生成，或任何指针 - preferably - ！点播，将是真棒

Any pointers on how to solve this either with a reliable sorting algorithm post generation, or - preferably - on-demand, would be awesome!

请注意：我们通常假设是n＆LT; = 50，K＆LT; = 5

Note: Let's typically assume that n <= 50, k <= 5

感谢

推荐答案

虽然我真的AP preciate从@tucuxi和@大卫艾森斯塔特的努力，我发现了哈密顿方法的一些问题，即它并没有求解n和k的某些价值观和某些元素进行了不必要的歧视。

While I really appreciate the efforts from @tucuxi and @David Eisenstadt, I found some issues with the Hamiltonian approach, namely that it didn't solve for certain values of n and k and certain elements were also unnecessarily discriminated.

我决定给我的问题列出一去（打伯爵表）的思想，它似乎给pretty的好成绩。此溶液然而也要求其不履行按需奖金要求后生成的排序。对于合理的氮，钾，这应该是可行的，但。

I decided to give the ideas listed in my question a go (hit count table) and it seems to give pretty good results. This solution however also requires a post-generation sorting which does not fulfill the on-demand bonus requirement. For reasonable n and k this should be feasible though.

诚然，我发现，我的算法的有时的似乎有利于导致连续出现的一个元素，它大概可以调整组合。但截至目前，我的算法可能不如tucuxi的为特异性。但它确实present每一个N，K的解决方案，似乎不太区分元素。

Admittedly, I've found that my algorithm sometimes seems to favour combinations that result in consecutive appearances for one element, which can probably be tuned. But as of now, my algorithm might be inferior to tucuxi's for specifically. It does however present a solution for every n, k and seems to discriminate elements less.

我的code如下所示。

My code is listed below.

再次感谢。

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));
        }
    }

}

结果：

Results for :

[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]

结果：

Results for :

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

这篇关于算法生成＆QUOT;防灰＆QUOT;从n个k个元素按需组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！