Вы можете сделать это, сначала создав и заполнив двумерный массив, который я назову NVT для «числа действительных хвостов», чтобы записать количество действительных «хвостов», которые начинаются с определенная позиция с заданным значением. Например, NVT [4] [6] = 3, потому что комбинация, имеющая 6 в позиции # 4, может закончиться тремя различными способами: (…, 6, 7), (…, 6, 8 ) и (…, 6, 9).
- Чтобы заполнить NVT , начните с NVT [ n ] […], что является просто строкой всех 1 с. Затем вернитесь на прежние позиции; например, NVT [2] [5] = NVT [3] [6] + NVT [3] [7] + NVT [3] [8], поскольку «хвост», начинающийся с позиции № 3 со значением 5, будет состоять из этих 5 плюс «хвост», начинающийся с позиции № 4 со значением 6, 7 или 8.
- Обратите внимание, что нам все равно, есть ли на самом деле правильный способ достичь данного хвоста. Например, NVT [4] [1] = 3 из-за допустимых хвостов (1, 2), (1, 3) и (1, 4), даже если нет заполните комбинаций вида (…, 1, _).
Как только вы это сделаете, вы можете вычислить ранг комбинации C следующим образом:
- Для позиции # 1 подсчитать все действительные хвосты, начиная с позиции # 1, со значением меньше C [1]. Например, если C начинается с 3, то это будет NVT [1] [1] + NVT [1] [2], представляя все комбинации которые начинаются с 1 или 2.
- Затем сделайте то же самое для всех последующих позиций. Они будут представлять комбинации, которые начинаются так же, как C , вплоть до заданной позиции, но затем имеют меньшее значение в этой позиции.
- Например, если C (1, 3, 5, 8, 9), получается
0 +
( НВТ [2] [1] + НВТ [2] [2]) +
( NVT [3] [1] + NVT [3] [2] + NVT [3] [3] + NVT [3] [4]) +
( NVT [4] [1] + NVT [4] [2] + NVT [4] [3] + NVT [4] [4] + NVT [4] [5] + NVT [4] [6] + NVT [4] [7]) +
( NVT [5] [1] + NVT [5] [2] + NVT [5] [3] + NVT [5] [4] + NVT [5] [5] + NVT [5] [6] + NVT [5] [7] + НВТ [5] [8]).
И наоборот, вы можете найти комбинацию C с данным рангом r следующим образом:
- Создать временную переменную rr для "оставшегося ранга", изначально равную r .
- Чтобы найти C [1] - значение в позиции # 1 - подсчитывать действительные хвосты, начиная с позиции # 1, начиная с наименьшего возможного значения (а именно 1), останавливаясь, как только это превысит р-р . Например, поскольку NVT [1] [1] = 66 и NVT [1] [2] = 27, комбинация с рангом 75 должна начинаться с 2 (потому что 75 ≥ 66 и 75 <66 + 27). Затем вычтите эту сумму из <em>rr (в этом случае оставив 75 минус 66 = 9).
- Затем сделайте то же самое для всех последующих позиций, не забывая при этом о наименьшем возможном значении с учетом того, что было в предыдущей позиции. Продолжая наш пример с r = 75, C [1] = 2 и rr = 9, мы знаем, что C [2 ] ≥ 3; и так как NVT [2] [3] = 23> rr , мы сразу обнаруживаем, что C [2] = 3.
Анализ сложности:
- Space:
- NVT требуется O ( nk ) пробел.
- Возвращение комбинации в виде массива длины - k по своей природе требует O ( k ) пробела; но если мы возвращаем комбинацию по одному значению за раз (вызывая обратный вызов или печатая на консоль или что-то еще), то само вычисление фактически не зависит от этого массива и требует только O (1 ) дополнительное место.
- Помимо тТаким образом, все остальное может управляться в O (1) пространстве;нам не нужны никакие рекурсии или временные массивы или что-либо.
- Время:
- Заполнение NVT занимает O ( нкд ) время.(Примечание: если d больше n , тогда мы можем просто установить d равным n .)
- Учитывая NVT , вычисление ранга данной комбинации занимает наихудший случай O ( nk ).
- Учитывая NVT, вычисление комбинации с данным рангом занимает наихудший случай O ( nk ).
Замечание по реализации: детали вышеупомянутого немного сложны;было бы легко получить ошибочную ошибку, смешать две переменные или еще что-то, если у вас нет конкретных данных для просмотра.Поскольку в вашем примере только 168 допустимых комбинаций, я рекомендую сгенерировать их все, чтобы вы могли ссылаться на них во время отладки.
Возможная дополнительная оптимизация: если вы ожидаете n быть достаточно большим, и вы ожидаете сделать много запросов для "ранжирования" и "отмены" комбинаций, тогда вам может быть полезно создать второй массив, который я назову NVTLT для "числа"допустимых хвостов меньше чем ", чтобы записать количество действительных" хвостов ", которые начинаются в определенной позиции со значением меньше данного значения.Например, NVTLT [3] [5] = NVT [3] [1] + NVT [3] [2] + NVT [3] [3] + NVT [3] [4] или, если хотите, NVTLT [3] [5] = NVTLT [3] [4] + NVT [3] [4].(Вы можете сделать это как преобразование на месте, полностью перезаписав NVT , так что это проход O ( nk ) без дополнительного пробела.) Использование NVTLT вместо NVT для ваших запросов позволит вам выполнять бинарный поиск по значениям, а не линейный поиск, давая наихудший случай O ( k * 1251)* log n ) время вместо O ( nk ) время.Обратите внимание, что эта оптимизация еще сложнее, чем приведенная выше, поэтому, даже если вы собираетесь выполнить эту оптимизацию, я рекомендую начать с вышеупомянутой, заставить ее работать идеально и только затем добавить эту оптимизацию.