Блог

итак, возник вопрос, который я не смог решить в основном из-за вычислительной мощности или ее отсутствия. Было интересно, как закодировать это, чтобы я действительно мог запустить его на своем компьютере. Суть вопросов такова:

Допустим, у вас есть строка 'xyz' , и вы хотите найти все уникальные перестановки этой строки. Затем вы сортируете их и находите индекс 'xyz' из уникальных перестановок. Это казалось достаточно простым, но затем, когда вы получаете действительно длинную строку, мой компьютер сдается. Какой математический способ обойти это, который, как я предполагаю, приведет меня к коду, который действительно может работать на моем ноутбуке.

 from itertools import permutations

def find_rank(n):
    perms = [''.join(p) for p in permutations(n)]
    perms = sorted(set(perms))
    loc = perms.index(n)
    return loc
  

Но если я хочу запустить этот код в строке длиной 100 букв, это слишком много для моего компьютера.

Эту проблему можно легко решить, сначала упростив ее и подумав рекурсивно.

Итак, давайте сначала предположим, что все элементы во входной последовательности уникальны, тогда набор «уникальных» перестановок — это просто набор перестановок.

Теперь, чтобы найти ранг последовательности a_1, a_2, a_3, ..., a_n в ее наборе перестановок, мы можем:

1. Отсортируйте последовательность для получения b_1, b_2, ..., b_n . Эта перестановка по определению имеет ранг 0 .

2. Теперь мы сравниваем a_1 и b_1 . Если они совпадают, мы можем просто удалить их из проблемы: ранг a_1, a_2, ..., a_n будет таким же, как и ранг just a_2, ..., a_n .

3. В противном b_1 < a_1 случае, но тогда все перестановки, начинающиеся с b_1 , будут меньше, чем a_1, a_2, ..., a_n . Количество таких перестановок легко вычислить, это просто (n-1)! = (n-1)*(n-2)*(n-3)*...*1 .

   Но тогда мы можем продолжить рассмотрение нашей последовательности b_1, ..., b_n . Если b_2 < a_1 , опять же, все перестановки, начинающиеся с b_2 , будут меньше. Поэтому мы должны (n-1)! снова добавить к нашему рангу.

   Мы делаем это до тех пор, пока не найдем индекс j where b_j == a_j , а затем окажемся в точке 2.

Это может быть реализовано довольно легко:

 import math

def permutation_rank(seq):
    ref = sorted(seq)
    if ref == seq:
        return 0
    else:
        rank = 0
        f = math.factorial(len(seq)-1)
        for x in ref:
            if x < seq[0]:
                rank  = f
            else:
                rank  = permutation_rank(seq[1:]) if seq[1:] else 0
                return rank
  

Решение довольно быстрое:

 In [24]: import string
    ...: import random
    ...: seq = list(string.ascii_lowercase)
    ...: random.shuffle(seq)
    ...: print(*seq)
    ...: print(permutation_rank(seq))
    ...: 
r q n c d w s k a z b e m g u f i o l t j x p h y v
273956214557578232851005079
  

По вопросу о равных элементах: точка, в которой они вступают в игру, — это (n-1)! количество перестановок, рассматривающих каждый элемент как отличный от других. Если у вас есть последовательность длины n , состоящая из символа s_1, ..., s_k , и символ s_j появляется c_j несколько раз, тогда количество уникальных перестановок равно `(n-1)! / (c_1! * c_2! * … * c_k!).

Это означает, что вместо простого добавления (n-1)! мы должны разделить его на это число, а также мы хотим уменьшить на единицу количество c_t текущего символа, который мы рассматриваем.

Это можно сделать таким образом:

 import math
from collections import Counter
from functools import reduce
from operator import mul

def permutation_rank(seq):
    ref = sorted(seq)
    counts = Counter(ref)

    if ref == seq:
        return 0
    else:
        rank = 0
        f = math.factorial(len(seq)-1)
        for x in sorted(set(ref)):
            if x < seq[0]:
                counts_copy = counts.copy()
                counts_copy[x] -= 1
                rank  = f//(reduce(mul, (math.factorial(c) for c in counts_copy.values()), 1))
            else:
                rank  = permutation_rank(seq[1:]) if seq[1:] else 0
                return rank
  

Я почти уверен, что есть способ избежать копирования словаря counts, но сейчас я устал, поэтому я оставлю это в качестве упражнения для читателя.

Для справки, конечный результат:

 In [44]: for i,x in enumerate(sorted(set(it.permutations('aabc')))):
    ...:     print(i, x, permutation_rank(x))
    ...:     
0 ('a', 'a', 'b', 'c') 0
1 ('a', 'a', 'c', 'b') 1
2 ('a', 'b', 'a', 'c') 2
3 ('a', 'b', 'c', 'a') 3
4 ('a', 'c', 'a', 'b') 4
5 ('a', 'c', 'b', 'a') 5
6 ('b', 'a', 'a', 'c') 6
7 ('b', 'a', 'c', 'a') 7
8 ('b', 'c', 'a', 'a') 8
9 ('c', 'a', 'a', 'b') 9
10 ('c', 'a', 'b', 'a') 10
11 ('c', 'b', 'a', 'a') 11
  

И показать, что это эффективно:

 In [45]: permutation_rank('zuibibzboofpaoibpaybfyab')
Out[45]: 246218968687554178
  

Давайте посмотрим, как можно вычислить индекс строки, не находя все перестановки строки.

s = "cdab". Теперь рассмотрим строку, перед строкой s (в лексическом порядке) будут строки "a***", "b***" . ( * обозначает оставшиеся символы).

Это 2*3! строки. Таким образом, любые строки, начинающиеся с c , будут иметь индекс больше этого.

После "a***" и "b***", начнется строка, начинающаяся с. 'c' Индекс строки s = 2*3! index("dab") .

Теперь рекурсивно найдите индекс для "dab"

Просто для иллюстрации порядок строк выглядит следующим образом :

     a*** --> 3! 
    b*** --> 3!
    ca** --> 2!
    cb** --> 2!
    cdab --> 1  
  

Ниже приведен код python :

 import math

def index(s):
    if(len(s)==1):
        return 1
    first_char = s[0]
    character_greater = 0
    for c in s:
        if(first_char>c):
            character_greater = character_greater 1
    return (character_greater*math.factorial((len(s)-1))   index(s[1:len(s)])    
  

Вот некоторый код Ruby, который я написал, чтобы сделать именно это. Вам нужно будет изменить его, если у вас есть повторяющиеся элементы (и решить, как вы хотите их обрабатывать).

Это позволяет использовать то преимущество, что если у нас есть n элементов, каждый выбор из k элементов будет отображаться точно (n-k)! времена. Например, [a, b, c, d] — если мы посмотрим на все перестановки, (4-1)! = 3! из них будут начинаться с каждого из ‘a’, ‘b’, ‘c’ и ‘d’. В частности, первые 3! будут начинаться с ‘a’, следующие 3! с b и так далее. Затем вы выполняете рекурсию по оставшимся элементам.

   def get_perm_id(arr)
    arr_len = arr.length
    raise "get_perm_id requires an array of unique elts" if arr_len != arr.uniq.length
    arr_sorted = arr.sort
    perm_num = 0
    0.upto(arr_len - 2) do |i|
      arr_elt = self[i]
      sorted_index = arr_sorted.find_index(arr_elt)
      sorted_right_index = arr_sorted.length - sorted_index - 1
      right_index = arr_len - i - 1
      left_delta = [0, right_index - sorted_right_index].max
      perm_num  = left_delta * (arr_len - i - 1).factorial
      arr_sorted.slice!(sorted_index)
    end
    perm_num
  end