Сначала вы должны написать функцию, которая даст вам n-ю перестановку элементов в списке. Затем вы можете объединить перестановки подсписка 0..7 с перестановками подсписка 8 ... 26.
Функция для получения n-й перестановки может быть определена с использованием переменной базы, состоящей из факториалов. Например, первые элементы списка размера N будут иметь размер 0 * base, 1 * base, 2 * base, ... Таким образом, вы можете определить индекс первого элемента путем вычисления значения base (N-1 )! и деление позиции на эту базу. Остальная часть этого деления - это позиция второго элемента в N-1 оставшихся элементов. Вы можете go выполнять этот процесс рекурсивно, пока не дойдете до последнего элемента.
Например:
from math import factorial
def nthPermute(A,n):
if not A: return tuple()
i,j = divmod(n,factorial(len(A)-1))
return (A[i],)+nthPermute(A[:i]+A[i+1:],j)
output:
for i in range(24):
print(i,nthPermute("ABCD",i))
0 ('A', 'B', 'C', 'D')
1 ('A', 'B', 'D', 'C')
2 ('A', 'C', 'B', 'D')
3 ('A', 'C', 'D', 'B')
4 ('A', 'D', 'B', 'C')
5 ('A', 'D', 'C', 'B')
6 ('B', 'A', 'C', 'D')
7 ('B', 'A', 'D', 'C')
8 ('B', 'C', 'A', 'D')
9 ('B', 'C', 'D', 'A')
10 ('B', 'D', 'A', 'C')
11 ('B', 'D', 'C', 'A')
12 ('C', 'A', 'B', 'D')
13 ('C', 'A', 'D', 'B')
14 ('C', 'B', 'A', 'D')
15 ('C', 'B', 'D', 'A')
16 ('C', 'D', 'A', 'B')
17 ('C', 'D', 'B', 'A')
18 ('D', 'A', 'B', 'C')
19 ('D', 'A', 'C', 'B')
20 ('D', 'B', 'A', 'C')
21 ('D', 'B', 'C', 'A')
22 ('D', 'C', 'A', 'B')
23 ('D', 'C', 'B', 'A')
Порядок перестановки следуют за порядком элементов в списке. Если ваш список отсортирован, вы сможете использовать алгоритм двоичного поиска, чтобы найти индекс заданной перестановки:
def indexOfPermute(A,P):
lo,hi = 0,factorial(len(A))-1
while lo<=hi:
mid = (lo+hi)//2
p = nthPermute(A,mid)
if p<P: lo = mid+1
elif p>P: hi = mid-1
else: return mid
i = indexOfPermute("ABCD",tuple('BCAD'))
print(i)
# 8
Применяя тот же принцип к вашим перестановкам из двух частей, вы можете создать функцию для получите n-е значение ваших ограниченных перестановок из 27 элементов.
def nthPerm_8_19(A,n):
i,j = divmod(n,factorial(19))
return nthPermute(A[:8],i)+nthPermute(A[8:],j)
output:
A = "12345678ABCDEFGHIJKLMNOPQRS"
for g in range(0,factorial(19)*7,factorial(19)):
for i in range(g,g+4):
print(i,"".join(nthPerm_8_19(A,i)))
0 12345678ABCDEFGHIJKLMNOPQRS
1 12345678ABCDEFGHIJKLMNOPQSR
2 12345678ABCDEFGHIJKLMNOPRQS
3 12345678ABCDEFGHIJKLMNOPRSQ
121645100408832000 12345687ABCDEFGHIJKLMNOPQRS
121645100408832001 12345687ABCDEFGHIJKLMNOPQSR
121645100408832002 12345687ABCDEFGHIJKLMNOPRQS
121645100408832003 12345687ABCDEFGHIJKLMNOPRSQ
243290200817664000 12345768ABCDEFGHIJKLMNOPQRS
243290200817664001 12345768ABCDEFGHIJKLMNOPQSR
243290200817664002 12345768ABCDEFGHIJKLMNOPRQS
243290200817664003 12345768ABCDEFGHIJKLMNOPRSQ
364935301226496000 12345786ABCDEFGHIJKLMNOPQRS
364935301226496001 12345786ABCDEFGHIJKLMNOPQSR
364935301226496002 12345786ABCDEFGHIJKLMNOPRQS
364935301226496003 12345786ABCDEFGHIJKLMNOPRSQ
486580401635328000 12345867ABCDEFGHIJKLMNOPQRS
486580401635328001 12345867ABCDEFGHIJKLMNOPQSR
486580401635328002 12345867ABCDEFGHIJKLMNOPRQS
486580401635328003 12345867ABCDEFGHIJKLMNOPRSQ
608225502044160000 12345876ABCDEFGHIJKLMNOPQRS
608225502044160001 12345876ABCDEFGHIJKLMNOPQSR
608225502044160002 12345876ABCDEFGHIJKLMNOPRQS
608225502044160003 12345876ABCDEFGHIJKLMNOPRSQ
729870602452992000 12346578ABCDEFGHIJKLMNOPQRS
729870602452992001 12346578ABCDEFGHIJKLMNOPQSR
729870602452992002 12346578ABCDEFGHIJKLMNOPRQS
729870602452992003 12346578ABCDEFGHIJKLMNOPRSQ
При этом вы можете использовать функцию nthPerm_8_19 (), как если бы у вас был очень длинный список содержит все 4,904,730,448,484,106,240,000 перестановок ваших элементов.
Чтобы реализовать «возобновляемый» процесс, вам нужно всего лишь записать позицию в списке виртуальных перестановок и продолжить с него после возобновления. Вы также можете использовать эту позицию для «расчленения» вычислений для параллельной обработки.
Схема индексирования также позволит вам «пропустить» часть перестановок. Например, если вы попадаете в точку, где хотите пропустить перестановки до следующего значения в позиции 11, вы можете обновить свой индекс, добавив дополнение по модулю base (26-11)! :
i = 851515702861824002
s = "".join(nthPerm_8_19(A,i)) # '12346587ABCDEFGHIJKLMNOPRQS'[11] = 'D'
base = factorial(26-11)
i += base - i % base
s = "".join(nthPerm_8_19(A,i)) # '12346587ABCEDFGHIJKLMNOPQRS'[11] = 'E'
[РЕДАКТИРОВАТЬ]
дальнейшая разбивка (в ответ на комментарий):
def nthPerm_8_10_9(A,n):
i,j = divmod(n,factorial(10)*factorial(9))
j,k = divmod(j,factorial(9))
return nthPermute(A[:8],i) + nthPermute(A[8:18],j) + nthPermute(A[18:],k)
Это можно обобщить непосредственно в Функция nthPermute () выглядит следующим образом:
def nthPermute(A,n,chunks=None):
if not A: return tuple()
if chunks is None:
if n>=factorial(len(A)): return None
i,j = divmod(n,factorial(len(A)-1))
return (A[i],)+nthPermute(A[:i]+A[i+1:],j)
result = tuple()
for size in reversed(chunks):
base = factorial(size)
n,i = divmod(n,base)
A,a = A[:-size],A[-size:]
result = nthPermute(a,i) + result
return result if n==0 else None
, а также в обратной функции для получения индекса перестановки (если элементы отсортированы внутри чанков):
def indexOfPermute(A,P,chunks=None):
lo,hi = 0,1
for c in chunks or [len(A)]: hi *= factorial(c)
hi -= 1
while lo<=hi:
mid = (lo+hi)//2
p = nthPermute(A,mid,chunks)
if p<P: lo = mid+1
elif p>P: hi = mid-1
else: return mid
, что позволило бы играть с чанком так, как вам нравится:
P = nthPermute(A,121645100408832000,[8,19])
print("".join(P),indexOfPermute(A,P,[8,19]))
# 12345687ABCDEFGHIJKLMNOPQRS 121645100408832000
P = nthPermute(A,26547069911040000,[8,10,9])
print("".join(P),indexOfPermute(A,P,[8,10,9]))
# 51234678ABCDEFGHIJKLMNOPQRS 26547069911040000
P = nthPermute(A,67722117120000,[6,6,9,6])
print("".join(P),indexOfPermute(A,P,[6,6,9,6]))
# 41235678ABCDEFGHIJKLMNOPQRS 67722117120000