Нахождение ранга перестановки положением G в
перестановок в примере в lexicographical order; первая перестановка имеет все B слева, а G - справа; другие перестановки выполняются путем постепенного перемещения G влево. (По аналогии с возрастающей последовательности двоичных чисел: 0011, 0101, 0110, 1001, 1010, 1100)
Чтобы подсчитать, как далеко в этом процессе данная перестановка, обратите внимание на символы по одному слева right: всякий раз, когда вы сталкиваетесь с G, количество перестановок, необходимых для его перемещения, есть (N выберите K), где N - количество позиций справа от текущей позиции, а K - количество слева G, включая ток Г.
123456 ← позиции
BBGGGG ← Оценка 0 (или 1)
BGBGGG ← ранга 1 (или 2)
BGGBGG ← ранга 2 (или 3)
BGGGBG ← Оценка 3 (или 4)
BGGGGB ← Оценка 4 (или 5)
GBBGGG ← Оценка 5 (или 6)
GBGBGG ← ранга 6 (или 7)
GBGGBG ← ранга 7 (или 8)
. для GBGGBG в вашем примере есть 4 G в 6 возможных положениях, а первый G находится в позиции 1, поэтому мы рассчитываем (6-1 выбираем 4) = 5; второй G находится в положении 3, поэтому мы добавляем (6-3 выбираем 3) = 1; третий G находится в положении 4, поэтому мы добавляем (6-4 выбираем 2) = 1; последний G находится в позиции 6, поэтому он находится в исходном положении и может быть проигнорирован. Это добавляет до 7, что означает, что перестановка имеет ранг 7 (или 8, если вы начинаете считать с 1, как и в вопросе).
Расчет (N выбирать K) с треугольником Паскаля
Вы можете использовать, например, Pascal's Triangle для расчета (N выберите K). Это треугольный массив, где каждое число является суммой двух чисел над ним:
K=0 K=1 K=2 K=3 K=4 K=5 K=6
N=0 1
N=1 1 1
N=2 1 2 1
N=3 1 3 3 1
N=4 1 4 6 4 1
N=5 1 5 10 10 5 1
N=6 1 6 15 20 15 6 1
Пример кода
Ниже простая реализация Javascript.Запустите фрагмент кода, чтобы увидеть несколько примеров. Время выполнения линейно зависит от количества стульев, а не от количества возможных перестановок, которое может быть огромным. (обновление: код теперь перебирает символы из справа налево, так что не нужно подсчитать количество G сначала.)
function permutationRank(perm) {
var chairs = perm.length, girls = 0, rank = 1; // count permutations from 1
var triangle = PascalsTriangle(chairs - 1); // triangle[n][k] = (n choose k)
for (var i = 1; i <= chairs; i++) {
if (perm.charAt(chairs - i) == 'G' && ++girls < i) {
rank += triangle[i - 1][girls];
}
}
return rank;
function PascalsTriangle(size) {
var tri = [[1]];
for (var n = 1; n <= size; n++) {
tri[n] = [1];
for (var k = 1; k < n; k++) {
tri[n][k] = tri[n - 1][k - 1] + tri[n - 1][k];
}
tri[n][n] = 1;
}
return tri;
}
}
document.write(permutationRank("BBGGGG") + "<BR>");
document.write(permutationRank("GBGGBG") + "<BR>");
document.write(permutationRank("GGGGBB") + "<BR>");
document.write(permutationRank("GGBGBBGBBBGBBBBGGGGGBBBBBGGGGBGGGBGGBGBB"));
Inverse алгоритм: сгенерировать перестановку
Этот алгоритм будет делать обратное: учитывая количество B, количество G и ранг перестановки, он вернет перестановку. Опять же, это делается без необходимости создания всех перестановок. (примечание: я не включил какую-либо проверку достоверности входных данных)
function permutationGenerator(boys, girls, rank) {
var chairs = boys + girls, perm = "";
var triangle = PascalsTriangle(chairs - 1); // triangle[n][k] = (n choose k)
for (var i = chairs; i > 0; i--) {
if (i > girls) {
var choose = triangle[i - 1][girls];
if (rank > choose) { // > if counting from 1, >= if counting from 0
rank -= choose;
perm += 'G';
--girls;
}
else perm += 'B';
}
else perm += 'G'; // only girls left
}
return perm;
function PascalsTriangle(size) {
var tri = [[1]];
for (var n = 1; n <= size; n++) {
tri[n] = [1];
for (var k = 1; k < n; k++) {
tri[n][k] = tri[n - 1][k - 1] + tri[n - 1][k];
}
tri[n][n] = 1;
}
return tri;
}
}
document.write(permutationGenerator(2, 4, 1) + "<BR>");
document.write(permutationGenerator(2, 4, 8) + "<BR>");
document.write(permutationGenerator(2, 4, 15) + "<BR>");
document.write(permutationGenerator(20, 20, 114581417274));
Вы гарантировано, что стулья будут начинаться с минимальной лексикографическом представлении каждая итерация итерация увеличит представление на 1? – NathanOliver
@NathanOliver Да, я могу это гарантировать, но я также могу изменить способ увеличения позиций, если есть более эффективный способ расчета позиции выбранной комбинации. – Nicolo
Если вы найдете ответ на этот вопрос, я бы с удовольствием его увидел. Несколько лет назад я хотел получить то же самое для оптимизатора стратегии блэкджека. –