2つの連続した組み合わせの差が最大化されるn要素のセットからk要素のすべての組み合わせを取得するアルゴリズムを実装しようとしています(逆グレイコードのようなものです)。言い換えると、要素が連続して 2 回出現することを避け、要素が不必要に区別されないように、組み合わせを順序付けする必要があります。
理想的には、アルゴリズムはすべての組み合わせを事前に計算してメモリに保存するのではなく、必要に応じて組み合わせを提供します。これを広範囲に検索したところ、https://stackoverflow.com/a/127856/1226020などの詳細な回答がいくつか見つかりましたが、これを適用できないようです。また、その回答にリンクされている記事の多くは有料コンテンツです。
私が何を意味するかを説明するには：
[0, 1, 2, 3, 4] のセットから、2 つの要素のすべての組み合わせを見つけます。一番右の要素を不可能になるまでインクリメントし、左に移動して前の桁をインクリメントするなどの単純なアルゴリズムを使用すると、次の結果が得られます。
[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" は 4 回連続して表示され、その後は表示されません。この特定の例では、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 の場合、要素が 2 つの連続する組み合わせで完全に出現するのを回避できるということです。さもないと、
この問題を、サッカー ゲームなどの標準的なラウンド ロビン スキームを使用して k = 2 で達成されるものと比較できますが、k の任意の値に対する解決策が必要です。これはある種のゲームのトーナメントであると想像できます。n 人のプレイヤーが一連のゲームで他のすべてのプレイヤーと対戦し、各ゲームには k 人のプレイヤーが参加します。プレイヤーはできる限り連続して 2 つのゲームをプレイする必要はありませんが、2 つのゲームの出現の間に不必要に長く待つ必要もないようにする必要があります。
生成後の信頼できる並べ替えアルゴリズム、またはできればオンデマンドでこれを解決する方法についての指針は素晴らしいでしょう!
注: 通常、n <= 50、k <= 5 と仮定しましょう
ありがとう