Получить перестановку с указанной степенью по номеру индекса

Ответ 1

Этот ответ менее изящный/эффективный, чем мой другой, но он описывает алгоритм полиномиального времени, который справляется с дополнительными ограничениями на упорядочение перестановок. Я опишу подпрограмму, которая, учитывая префикс перестановки n-элементов и набора градусов, подсчитывает, сколько перестановок имеет этот префикс и степень, принадлежащую множеству. Учитывая эту подпрограмму, мы можем выполнить n-арный поиск перестановки указанного ранга в указанном подмножестве, расширяя известный префикс по одному элементу за раз.

Мы можем визуализировать перестановку n-элементов p как n-вершинный, n-дуговый ориентированный граф, где для каждой вершины v существует дуга от v до p (v). Этот орграф состоит из набора вершинно-дизъюнктных циклов. Например, перестановка 31024 выглядит как

 _______
/       \
\->2->0->3
 __     __
/  |   /  |
1<-/   4<-/ .

Учитывая префикс перестановки, мы можем визуализировать подграф, соответствующий этому префиксу, который будет представлять собой набор вершинно-непересекающихся путей и циклов. Например, префикс 310 выглядит как

2->0->3
 __
/  |
1<-/ .

Я собираюсь описать биекцию между (1) расширениями этого префикса, которые являются перестановками и (2) полными перестановками на связанном множестве элементов. Эта биекция сохраняет на постоянном члене число циклов (число элементов минус степень). Постоянный член - это число циклов в префиксе.

Перестановки, упомянутые в (2), относятся к следующему набору элементов. Начните с исходного набора, удалите все элементы, участвующие в циклах, которые завершены в префиксе, и введите новый элемент для каждого пути. Например, если префикс равен 310, то мы удалим полный цикл 1 и введем новый элемент A для пути 2- > 0- > 3, в результате чего получим множество {4, A}. Теперь, учитывая перестановку в множестве (1), мы получим перестановку в множестве (2), удалив известные циклы и заменив каждый путь своим новым элементом. Например, перестановка 31024 соответствует перестановке 4- > 4, A- > A, а перестановка 31042 соответствует перестановке 4- > A, A- > 4. Я утверждаю (1), что эта карта является биекцией и (2), что она сохраняет степени, как описано ранее.

Определение более или менее (n, k) -го числа Стирлинга первого рода, написанное

[n]
[ ]
[k]

(ASCII art square brackets), является числом n-элементов перестановок степени n - k. Чтобы вычислить количество расширений префикса r-элементов для перестановки n-элементов, count c, количество полных циклов в префиксе. Сумма, для каждой степени d в указанном наборе, число Стирлинга

[  n - r  ]
[         ]
[n - d - c]

первого рода, считая члены с "невозможными" индексами равными нулю (некоторые аналитически мотивированные определения чисел Стирлинга в неожиданных местах отличны от нуля).

Чтобы получить ранг из перестановки, мы снова выполняем n-арный поиск, за исключением этого времени, мы используем перестановку, а не ранг, чтобы вести поиск.

Здесь приведен код Python для обоих (включая тестовую функцию).

import itertools

memostirling1 = {(0, 0): 1}
def stirling1(n, k):
    ans = memostirling1.get((n, k))
    if ans is None:
        if not 1 <= k <= n: return 0
        ans = (n - 1) * stirling1(n - 1, k) + stirling1(n - 1, k - 1)
        memostirling1[(n, k)] = ans
    return ans

def cyclecount(prefix):
    c = 0
    visited = [False] * len(prefix)
    for (i, j) in enumerate(prefix):
        while j < len(prefix) and not visited[j]:
            visited[j] = True
            if j == i:
                c += 1
                break
            j = prefix[j]
    return c

def extcount(n, dset, prefix):
    c = cyclecount(prefix)
    return sum(stirling1(n - len(prefix), n - d - c) for d in dset)

def unrank(n, dset, rnk):
    assert rnk >= 0
    choices = set(range(n))
    prefix = []
    while choices:
        for i in sorted(choices):
            prefix.append(i)
            count = extcount(n, dset, prefix)
            if rnk < count:
                choices.remove(i)
                break
            del prefix[-1]
            rnk -= count
        else:
            assert False
    return tuple(prefix)

def rank(n, dset, perm):
    assert n == len(perm)
    rnk = 0
    prefix = []
    choices = set(range(n))
    for j in perm:
        choices.remove(j)
        for i in sorted(choices):
            if i < j:
                prefix.append(i)
                rnk += extcount(n, dset, prefix)
                del prefix[-1]
        prefix.append(j)
    return rnk

def degree(perm):
    return len(perm) - cyclecount(perm)

def test(n, dset):
    for (rnk, perm) in enumerate(perm for perm in itertools.permutations(range(n)) if degree(perm) in dset):
        assert unrank(n, dset, rnk) == perm
        assert rank(n, dset, perm) == rnk

test(7, {2, 3, 5})

Ответ 2

Перестановки длины n и степени d являются точками, которые могут быть записаны как композиция из k = n - d циклов, которые разбивают n элементов. Число таких перестановок дается номерами Стирлинга первого рода, записанными в квадратных скобках n в квадратных скобках.

Числа Стирлинга первого рода удовлетворяют рекуррентному соотношению

[n]           [n - 1]   [n - 1]
[ ] = (n - 1) [     ] + [     ]
[k]           [  k  ]   [k - 1],

что означает, интуитивно, количество способов разбиения n элементов на k циклов состоит в том, чтобы разбивать n-1 не максимальных элементов на k циклов и сращивать в максимальном элементе одним из n-1 способов или поставить максимум элемент в своем собственном цикле и разбивать n - 1 не максимальных элементов на k - 1 циклы. Работая из таблицы повторяющихся значений, можно проследить решения по линии.

memostirling1 = {(0, 0): 1}
def stirling1(n, k):
    if (n, k) not in memostirling1:
        if not (1 <= k <= n): return 0
        memostirling1[(n, k)] = (n - 1) * stirling1(n - 1, k) + stirling1(n - 1, k - 1)
    return memostirling1[(n, k)]

def unrank(n, d, i):
    k = n - d
    assert 0 <= i <= stirling1(n, k)
    if d == 0:
        return list(range(n))
    threshold = stirling1(n - 1, k - 1)
    if i < threshold:
        perm = unrank(n - 1, d, i)
        perm.append(n - 1)
    else:
        (q, r) = divmod(i - threshold, stirling1(n - 1, k))
        perm = unrank(n - 1, d - 1, r)
        perm.append(perm[q])
        perm[q] = n - 1
    return perm

Ответ 3

Я думаю, что вы ищете вариант расстояние Левенштейна, которое используется для измерения количества изменений между двумя строками. Эффективный способ вычислить это с помощью метода, называемого динамическим программированием - в связанной статье представлен псевдо-алгоритм для "нормального" расстояния Левенштейна. Вам нужно будет адаптировать это для учета того факта, что вместо добавления, удаления или замены символа единственно допустимая операция заключается в обмене элементами в двух положениях.

Относительно вашего второго алгоритма: это не соотношение 1:1 между степенями перестановок и "a", что приводит к перестановке, вместо этого число возможных результатов растет экспоненциально с количеством свопов: для последовательности элементов k k*(k-1)/2 возможные пары индексов, между которыми можно поменять местами. Если мы назовем это число l, после d swaps у вас есть l^d возможные результаты (хотя некоторые из них могут быть одинаковыми, как при первом подкачке 0 < > 1, затем 2 < 3 или первые 2 < 3, то 0 < > 1).

Ответ 4

Я написал этот ответ stackoverflow для аналогичной проблемы: fooobar.com/questions/412729/.... Помогло ли это?

Разница может быть в бит подкачки для генерации perms, но в Python указана функция index-to-perm и perm-to-index.

Позднее я создал эту задачу Rosetta Code, которая была привязана к ссылкам и коду: http://rosettacode.org/wiki/Permutations/Rank_of_a_permutation.

Надеюсь, что это поможет: -)

Ответ 5

Первая часть прямолинейна, если вы полностью работаете на лексикографической стороне вещей. Учитывая мой ответ на другой поток, вы можете перейти от перестановки к факториальному представлению мгновенно. В принципе, вы представляете список {0,1,2,3}, а число, которое мне нужно пройти, - это факториальное представление, поэтому для 1,2,3,4 я продолжаю брать нулевой элемент и получать 000 (0 * 3 + 0 *! 2 + 0 *! 1!).

0,1,2,3, = > 000

1032 = 3! +1!= 8-я перестановка (как 000 - первая перестановка) = > 101

И вы можете выработать степень тривиально, так как каждая транспозиция, которая меняет пару чисел (a, b) a

Итак, 0123 → 1023 - 000 → 100.

если a > b вы заменяете числа, а затем вычитаете один из номера правой руки.

Учитывая два набора/лексиографических чисел, я просто переставляю цифры справа налево, как сортировка пузырьков, считая степень, в которой я нуждаюсь, и строю новое лексиографическое число, когда я иду. Поэтому, чтобы перейти от 0123 к 1032 i, сначала переместите 1 влево, затем нуль находится в правильном положении, а затем я перемещаю 2 в положение, и оба из них имеют пары с номером rh больше, чем левая рука число, поэтому оба добавляют 1, поэтому 101.

Это касается первой проблемы. Вторая задача намного сложнее, так как числа второй степени распределены неравномерно. Я не вижу ничего лучше, чем получение глобального лексиографического числа (глобальное значение здесь числа без каких-либо исключений) нужной вам перестановки, например. 78 в вашем примере, а затем просмотрите все лексикографические числа и каждый раз, когда вы попадаете на уровень 2, затем добавьте его к своему глобальному лексиографическому номеру, например. 78 → 79, когда вы найдете первый номер степени 2. Obvioulsy, это будет не так быстро. В качестве альтернативы вы можете попробовать создать все числа степени. Учитывая набор из n элементов, есть (n-1) (n-2) числа степени 2, но неясно, что это продолжается, по крайней мере, для меня, что может быть намного меньше работы, чем вычислять все номера до вашей цели. и вы могли бы просто увидеть, какие из них имеют лексиографическое число меньше целевого, и снова добавьте его к своему глобальному лексиографическому номеру.

Я вижу, могу ли я придумать что-то лучшее.

Ответ 6

Это казалось забавным, поэтому я подумал об этом еще немного.

Пусть возьмет пример Дэвид 31042 и найдет его индекс. Сначала мы определяем степень, равную сумме мощностей циклов перестановки, каждый из которых вычитается на 1.

01234
31042

permutation cycles (0342)(1)
degree = (4-1) + (1-1) = 3

def cycles(prefix):
  _cycles = []
  i = j = 0
  visited = set()

  while j < len(prefix):
    if prefix[i] == i:
      _cycles.append({"is":[i],"incomplete": False})
      j = j + 1
      i = i + 1
    elif not i in visited:
      cycle = {"is":[],"incomplete": False}
      cycleStart = -1
      while True:
        if i >= len(prefix):
          for k in range(len(_cycles) - 1,-1,-1):
            if any(i in cycle["is"] for i in _cycles[k]["is"]):
              cycle["is"] = list(set(cycle["is"] + _cycles[k]["is"]))
              del _cycles[k]
          cycle["incomplete"] = True
          _cycles.append(cycle)
          break
        elif cycleStart == i:
          _cycles.append(cycle)
          break
        else:
          if prefix[i] == j + 1:
            j = j + 1
          visited.add(i)
          if cycleStart == -1:
            cycleStart = i
          cycle["is"].append(i)
          i = prefix[i]
    while j in visited:
      j = j + 1
    i = j
  return _cycles

def degree(cycles):
  d = 0
  for i in cycles:
    if i["incomplete"]:
      d = d + len(i["is"])
    else:
      d = d + len(i["is"]) - 1
  return d

Далее мы определяем, сколько перестановок степени 3 начинаются с нуля, одного или двух; используя формулу Дэвида:

number of permutations of n=5,d=3 that start with "0" = S(4,4-3) = 6
number of permutations of n=5,d=3 that start with "1" = S(4,4-2) = 11

[just in case you're wondering, I believe the ones starting with "1" are:
 (01)(234)
 (01)(243)
 (201)(34)
 (301)(24)
 (401)(23)
 (2301)(4)
 (2401)(3)
 (3401)(2)
 (3201)(4)
 (4201)(3)
 (4301)(2) notice what common to all of them?]

number of permutations of n=5,d=3 that start with "2" = S(4,4-2) = 11

Мы задаемся вопросом, может ли быть лексикографически-нижняя перестановка степени 3, которая также начинается с "310". Единственная возможность, похоже, 31024:

01234
31024 ?
permutaiton cycles (032)(4)(1)
degree = (3-1) + (1-1) + (1-1) = 2
since its degree is different, we will not apply 31024 to our calculation

Перестановки степени 3, начинающиеся с "3" и лексикографически ниже 31042, должны начинаться с префикса "30". Их число равно числу способов, которыми мы можем поддерживать "три" до "нуля" и "нуля" перед "одним" в наших циклах перестановки, сохраняя при этом сумму мощностей циклов, каждый из которых вычитается на 1 (т.е. степени), при 3.

(031)(24)
(0321)(4)
(0341)(2)
count = 3

Кажется, что есть 6 + 11 + 11 + 3 = 31 перестановки n = 5, d = 3 до 31042.

def next(prefix,target):
  i = len(prefix) - 1
  if prefix[i] < target[i]:
    prefix[i] = prefix[i] + 1
  elif prefix[i] == target[i]:
    prefix.append(0)
    i = i + 1
  while prefix[i] in prefix[0:i]:
    prefix[i] = prefix[i] + 1
  return prefix

def index(perm,prefix,ix):
  if prefix == perm:
    print ix
  else:
    permD = degree(cycles(perm))
    prefixD = degree(cycles(prefix))
    n = len(perm) - len(prefix)
    k = n - (permD - prefixD)
    if prefix != perm[0:len(prefix)] and permD >= prefixD:
      ix = ix + S[n][k]
    index(perm,next(prefix,perm),ix)

S = [[1]
    ,[0,1]
    ,[0,1,1]
    ,[0,2,3,1]
    ,[0,6,11,6,1]
    ,[0,24,50,35,10,1]]

(Попробуем подтвердить с помощью программы Дэвида (я использую ПК с окнами):

C:\pypy>pypy test.py REM print(index([3,1,0,4,2],[0],0))
31

C:\pypy>pypy davids_rank.py REM print(rank(5,{3},[3,1,0,2,4]))
31