Início / user-13395230

Bobby Ocean's questions

Martin Hope
Bobby Ocean
Asked: 2024-04-12 06:23:44 +0800 CST
  • 6

Estou interessado em encontrar uma fórmula simples para determinar a enésima vez que uma determinada contagem de bits ocorre na sequência de números naturais. Especificamente, qual é a relação entre Ke Nna tabela abaixo. Então, por exemplo, qual é o Nde K=123456789123456789123456789, posso dizer que Mé 50, mas qual é o N?

length = 5
for K in range(2**length):
    bits = bin(K)[2:].zfill(length)
    M    = K.bit_count() # numbers of "1"s in the binary sequence
    N    = sum(1 for i in range(K) if M==i.bit_count())
    print(f'{K: <2}',bits,M,N)

'''
K  bits  M N
0  00000 0 0
1  00001 1 0
2  00010 1 1
3  00011 2 0
4  00100 1 2
5  00101 2 1
6  00110 2 2
7  00111 3 0
8  01000 1 3
9  01001 2 3
10 01010 2 4
11 01011 3 1
12 01100 2 5
13 01101 3 2
14 01110 3 3
15 01111 4 0
16 10000 1 4
17 10001 2 6
18 10010 2 7
19 10011 3 4
20 10100 2 8
21 10101 3 5
22 10110 3 6
23 10111 4 1
24 11000 2 9
25 11001 3 7
26 11010 3 8
27 11011 4 2
28 11100 3 9
29 11101 4 3
30 11110 4 4
31 11111 5 0
...
'''

Então, parece que resolvi metade disso. Parece que

N = (K-sum(2**i for i in range(M)).bit_count()

em qualquer momento N<=M. Isto parece ser porque,

K = sum(2**i for i in range(M)) + sum(2**(M-1-i) for i in range(N))

novamente, sempre que N<=M. Parece que isso N<=Mocorre cerca de metade das vezes.

length = 5
for K in range(2**length):
    bits = bin(K)[2:].zfill(length)
    M    = K.bit_count() # numbers of "1"s in the binary sequence
    N    = sum(1 for i in range(K) if M==i.bit_count())
    if N <= M:
        A = sum(2**i for i in range(M)) + sum(2**(M-1-i) for i in range(N))
        B = (K - sum(2**i for i in range(M))).bit_count()
    else:
        A = '-'
        B = '-'
    print(f'{K: <2}',bits,M,N,A,B)
python
Martin Hope
Bobby Ocean
Asked: 2023-09-20 01:53:47 +0800 CST
  • 9

Dadas duas grandes matrizes,

A = np.random.randint(10,size=(10000,2))
B = np.random.randint(10,size=(10000,2))

Gostaria de determinar se algum dos vetores tem um produto vetorial igual a zero. Nós poderíamos fazer

C = np.cross(A[:,None,:],B[None,:,:])

e então verifique se C contém 0 ou não.

not C.all()

No entanto, este processo requer o cálculo de todos os produtos cruzados, o que pode ser demorado. Em vez disso, eu preferiria deixar numpy realizar o produto vetorial, mas SE um zero for alcançado em qualquer ponto, simplesmente corte toda a operação e termine mais cedo. O numpy tem uma operação de "rescisão antecipada" que interromperá as operações numpy antecipadamente se elas atingirem uma condição? Algo como,

np.allfunc()
np.anyfunc()

O exemplo acima é um caso em que A e B têm uma probabilidade extremamente alta de ter um produto vetorial zero em algum ponto (na verdade, é muito provável que ocorra perto do início), tanto que a execução de um python-for-loop (eca!) é muito mais rápido do que usar o código altamente otimizado do numpy.

Em geral, qual é a maneira mais rápida de determinar se A e B têm produto vetorial zero?

python