在特定的索引中与某些元素的排列组合

问题描述 投票：1回答：3

是否可以找到一个列表(n=27)的所有排列组合，并限制元素x0到x7只能在任何位置，只要它在排列组合的索引0到7中？

keys = [x0, x1, x2, x3, x4, x5, x6, x7 ... x26]

[x1, x2, x3, x4, x5, x6, x7, x0 ... x26] #is okay
[x0, x1, x2, x3, x4, x5, x6, x8, x7 ... x26] #is NOT okay

我需要它从第n次排列开始就可以 "恢复"，因为会有很多排列，我无法在一次运行中测试所有排列。它可能必须是一个生成器（某种形式），这样我就可以在生成时测试每一个排列组合，否则它将很快地消耗内存。

如果有任何建议，我们会非常感激。

我考虑过的解决方案。

permitted = [x0, x1, x2, x3, x4, x5, x6, x7]

for p in itertools.permutations(keys):
   if p[0] not in permitted:
      continue
   if p[1] not in permitted:
      continue
   ...
   # if it passes all the limitations, test this permutation
   test(p)

问题是我不能生成所有的排列组合 然后在一次未解释的运行中测试它们。

我从这个答案中尝试的另一个方法是 此处:

from math import factorial

def ith_permutation(i, seq, r=None):
    li = list(seq)
    length = len(li)

    if r is None:
        r = length
    res = []
    current_factorial = factorial(length) // factorial(length - r)

    if current_factorial <= i:
        raise ValueError('out of range')

    for x in range(length, length-r, -1):
        current_factorial //= x
        div, mod = divmod(i, current_factorial)
        i = mod
        res.append(li[div])
        del(li[div])

    return res


for i in range(0, factorial(len(keys))-1):
   p = ith_permutation(i, keys)
   test(p)

原则上和上面的一样，但我又要经历1.08e+28次排列组合！这是不可能的。这是不可能的。

python algorithm permutation
3个回答
1
投票

首先，你必须写一个函数，它将给你一个列表中元素的第n次排列。 然后你可以将0...7子列表的排列组合与8...26子列表的排列组合。

获取第n次排列的函数可以使用由阶乘组成的变量基来定义。 例如，一个N大小的列表的第一个元素将在0*基数，1*基数，2*基数，...。 所以你可以通过计算基数的值（N-1）来确定第一个元素的索引！并将位置除以该基数。 该除数的剩余部分就是第二个元素在N-1个剩余元素中的位置。 你可以递归地经历这个过程，直到你得到最后一个元素。

例如

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)

输出：

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

将同样的原理应用于你的两部分排列组合 你可以创建一个函数来获取27个元素的约束排列组合的第n个值。

def nthPerm_8_19(A,n):
    i,j = divmod(n,factorial(19))
    return nthPermute(A[:8],i)+nthPermute(A[8:],j)

输出。

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的下一个值，你可以通过添加基数(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
0
投票

请注意，你要找的是下列元素的排列组合： x0,...,x7 叠加 x8,...,x26. 所以，一个双循环将做雅。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.