拨开荷叶行,寻梦已然成。仙女莲花里,翩翩白鹭情。
IMG-LOGO
主页 文章列表 整数和阵列排列之间的惰性映射而不生成所有排列

整数和阵列排列之间的惰性映射而不生成所有排列

白鹭 - 2022-03-04 2016 0 0

我想在python中生成一组整数阵列和整数值之间的映射,例如对于n=2(阵列的大小)和m=2(阵列项范围),我想要:

{
   0: [0, 0, 0],
   1: [0, 0, 1],
   2: [0, 1, 1],
   3: [1, 0, 0],
   ...
   7: [1, 1, 1]

}

一种方法是使用itertools.product并执行以下操作:

from itertools import product
import numpy as np
n = 2
m = 3
a = list(product(np.arange(n), repeat=3))
a = list(map(lambda l: list(l), a))
b = dict(zip(np.arange(len(a)), a))

并且b将是:

{0: [0, 0, 0], 1: [0, 0, 1], 2: [0, 1, 0], 3: [0, 1, 1], 4: [1, 0, 0], 5: [1, 0, 1], 6: [1, 1, 0], 7: [1, 1, 1]}

我可以有提到的映射,例如

>>> b[1]
[0, 0, 1]

然而,在我的情况n=8,并m=16和存盘这样的字典(8**16条目!)需要超过100 GB。我想知道每次我想访问 b 的每个索引时是否有一种懒惰的方法来生成每个索引而不生成整个字典?

uj5u.com热心网友回复:

您可以制作一个函式而不是完整的地图。您的输出实际上是大小为 m 的阵列,表示以第 n 个符号表示的输入 a 的值。如果您想制作地图,只需在键不存在的情况下将函式的结果保存在地图中。

def f(a, n, m):
    res = []
    while a != 0:
        res = [a % n]   res
        a //= n
        m -= 1
    while m != 0:
        res = [0]   res
        m -= 1
    return res

uj5u.com热心网友回复:

您可以通过采用x//n**(i-1)%n在 m-1 和 0 之间变化的连续for i来生成第 x 个元素

n = 3
m = 4

x = 6
[x//n**(i-1)%n for i in range(m, 0, -1)]

输出: [0, 0, 2, 0]

作为函式
def f(x, n, m):
    return [x//n**(i-1)%n for i in range(m, 0, -1)]

f(1, n=2, m=3)
# [0, 0, 1]

f(1234567890, n=8, m=16)
# [0, 0, 0, 0, 0, 1, 1, 1, 4, 5, 4, 0, 1, 3, 2, 2]

uj5u.com热心网友回复:

在您的示例中,您更象是在映射产品而不是排列。

给出的具体示例可以转换为一个函式,该函式将为您提供整数位(无需存盘任何内容):

def bits(n,w=16): return [*map(int,f'{n:0{w}b}')]

bits(5,3)  # [1, 0, 1]
bits(13,8) # [0, 0, 0, 0, 1, 1, 0, 1]

对于更通用的“产品”虚拟串列,您可以创建一个函式来从序列串列中获取第 N 个产品,这些序列将涵盖您的示例及更多内容:

def prodAtIndex(i,L):
    result = []                     # product fed in reversed order           
    for v in reversed(L):           # from least significant to most
        i,p = divmod(i,len(v))      # get digit in current 'base'
        result.insert(0,v[p])       # build product
    return result if i==0 else None # i will end at zero if in range

prodAtIndex(16,[(0,1,2)]*3)      # [1,2,1]
prodAtIndex(13,[(0,1)]*8)        # [0, 0, 0, 0, 1, 1, 0, 1]
prodAtIndex(10,["ABCD",(1,2,3)]) # ['D', 2]

可以创建一个类来更无缝地操作虚拟产品串列:

class Products:

    def __init__(self,*values):
        self.values = values
        
    def __len__(self):
        result = 1
        for s in map(len,self.values): result *= s
        return result

    def __getitem__(self,index):
        if isinstance(index,slice):
            return (self[i] for i in range(len(self))[index])
        if index<0: index  = len(self)
        result = []                        # product fed in reversed order
        for v in reversed(self.values):    # from least significant to most
            index,p = divmod(index,len(v)) # get digit in current 'base'
            result.insert(0,v[p])          # build product
        if index: raise IndexError         # will be zero if in range
        return tuple(result)

    def index(self,P):
        index = 0
        for v,p in zip(self.values,P):
            index *= len(v)
            index  = v.index(p)
        return index

用法:

 p = Products("ABCD",(1,2,3,4,5))

 len(p)             # 20

 p[4]               # ('A', 5)
 p[-4]              # ('D', 2) 

 p.index(['A',5])   # 4 

 for prod in p[3:5]: print(prod)

 ('A', 4)
 ('A', 5)


 # For your example...

 m  = 3
 n  = 2
 b3 = Products(*[range(n)]*m)

 b3[5] # [1, 0, 1]

排列?

如果您确实想象拥有串列一样操作排列但不生成实际串列,则可以创建一个函式,该函式将为您提供“虚拟”串列中的第 N 个排列:

from math import factorial
def permCount(A,k): return factorial(len(A))//factorial(len(A)-k)
def permAtIndex(A,k,index):
    A      = list(A)
    base   = permCount(A,k)
    result = []
    for _ in range(k):                    # for required size
        base  //= len(A)                  # chunk size for position
        i,index = divmod(index,base or 1) # i is value index at position
        result.append(A.pop(i))           # build permutation
    return result 

这将为您提供排列“串列”的大小,并允许您在给定索引处获得排列:

print(permCount([1,2,3,4],4))       # 24
print(permAtIndex([1,2,3,4],4,22))  # [4, 3, 1, 2]

print(permCount(range(15),10))              # 10897286400
print(permAtIndex(range(15),10,5897286400)) # [8,1,10,5,12,0,13,7,14,9]

您还可以创建一个反向函式来为您提供给定排列的索引:

def indexOfPerm(A,k,P):
    A      = list(A)
    base   = permCount(A,k)
    result = 0
    for n in P:            
        base //= len(A)  # chunk size for position
        i = A.index(n)   # index in remaining items
        result  = base*i # position's component of index
        A.pop(i)         # next position on rest of items
    return result

print(indexOfPerm([1,2,3,4],4,[4, 3, 1, 2])) # 22
print(indexOfPerm(range(15),10,[8,1,10,5,12,0,13,7,14,9])) # 5897286400

所有这些都可以变成一个允许操作虚拟排列串列的类:

from math import factorial as fact
class Permutations:

    def __init__(self,values,size):
        self.values = values
        self.size   = size
        
    def __len__(self):
        return fact(len(self.values))//fact(len(self.values)-self.size)

    def __getitem__(self,index):
        if isinstance(index,slice):
            return (self[i] for i in range(len(self))[index])
        A      = list(self.values)
        base   = len(self)
        value  = []
        if index<0: index  = len(self)
        for _ in range(self.size):            # for required size
            base  //= len(A)                  # chunk size for position
            i,index = divmod(index,base or 1) # i is value index at position
            value.append(A.pop(i))            # build permutation
        return tuple(value)

    def index(self,P):
        A      = list(self.values)
        base   = len(self)
        index  = 0
        for n in P:            
            base //= len(A)  # chunk size for position
            i = A.index(n)   # index in remaining items
            index  = base*i  # position's component of index
            A.pop(i)         # next position on rest of items
        return index

用法:

p = Permutations(range(15),10)

print(len(p))                  # 10897286400

print(p[5897286400])           # (8, 1, 10, 5, 12, 0, 13, 7, 14, 9)
print(p[-100])                 # (14, 13, 12, 11, 10, 9, 8, 5, 4, 2)

print(p.index([8, 1, 10, 5, 12, 0, 13, 7, 14, 9])) # 5897286400


for perm in p[100:105]: print(perm)
(0, 1, 2, 3, 4, 5, 6, 9, 10, 13)
(0, 1, 2, 3, 4, 5, 6, 9, 10, 14)
(0, 1, 2, 3, 4, 5, 6, 9, 11, 7)
(0, 1, 2, 3, 4, 5, 6, 9, 11, 8)
(0, 1, 2, 3, 4, 5, 6, 9, 11, 10) 

请注意,在非唯一值串列上使用的这个 Permutations 类将产生重复的排列

标签:

0 评论

发表评论

您的电子邮件地址不会被公开。 必填的字段已做标记 *