Я пытаюсь реализовать алгоритм для получения всех комбинаций k элементов из набора n элементов, где разница между двумя последовательными комбинациями максимальна (такого рода обратные коды Грея). Другими словами, комбинации должны быть упорядочены таким образом, чтобы элементы не появлялись дважды подряд и чтобы ни один элемент не выделялся без необходимости.
В идеале алгоритм также НЕ будет предварительно вычислять все комбинации и сохранять их в памяти, а будет доставлять комбинации по запросу. Я тщательно искал это и нашел несколько подробных ответов, таких как 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
Спасибо
