有序(n选p)二进制编解码

Question

我想'强加'顺序(n选择p)二进制，并能够编码/解码项目。

下面是一个p=2的例子。对于p>它将需要更多的循环。顺便说一句，这个函数只是一个特定顺序的说明，它可以是不同的只需要用尽所有的组合。

我要的是编码/解码!!

如果它使用INDEX值而不是bitarray，即10100 =>(3、5)

import numpy as np
#should exhaust all (n choose p) possibilities
def order(p=2,n=4) :
p = 0
for i in range(n):
for j in range(i+1,n):
v = np.zeros(n,dtype=int)
v[i]=1; v[j]=1; p+=1
print(f'pos:{p} {v}')

def encode(pos,p=2,n=4):
pass #should return val at pos
def decode(value,p=2,n=4):
pass #should return  pos of val


order(n=4)
print()
order(n=5)
-----
pos:1 [1 1 0 0]
pos:2 [1 0 1 0]
pos:3 [1 0 0 1]
pos:4 [0 1 1 0]
pos:5 [0 1 0 1]
pos:6 [0 0 1 1]
pos:1 [1 1 0 0 0]
pos:2 [1 0 1 0 0]
pos:3 [1 0 0 1 0]
pos:4 [1 0 0 0 1]
pos:5 [0 1 1 0 0]
pos:6 [0 1 0 1 0]
pos:7 [0 1 0 0 1]
pos:8 [0 0 1 1 0]
pos:9 [0 0 1 0 1]
pos:10 [0 0 0 1 1]

---

似乎是合法的:

In [36]: [nth_combination(range(10),3,i) for i in range(10)]                                                                                                                 
Out[36]: [(0, 1, 2), (0, 1, 3), (0, 1, 4), (0, 1, 5), (0, 1, 6), (0, 1, 7), (0, 1, 8), (0, 1, 9), (0, 2, 3), (0, 2, 4)]

In [6]: [nth_combination(range(1000),5,i) for i in range(100000,100010)]                                                                                                     
Out[6]: 
[(0, 1, 2, 108, 989),
(0, 1, 2, 108, 990),
(0, 1, 2, 108, 991),
(0, 1, 2, 108, 992),
(0, 1, 2, 108, 993),
(0, 1, 2, 108, 994),
(0, 1, 2, 108, 995),
(0, 1, 2, 108, 996),
(0, 1, 2, 108, 997),
(0, 1, 2, 108, 998)]
In [7]: combination_index((0,1,2,108,990),range(1000))                                                                                                                       
Out[7]: 100001

Answer 1

下面是编码/解码的递归实现。我想提出两个警告:

如果您要编码/解码非常大的值，您可能会遇到RecursionDepthExceeded异常，就像大多数递归一样。然而，这将需要非常大的输入值。

其次，由于列表连接(为了简单起见)，这可能比需要的要慢得多。如果关注性能，则应该传递累加器，并将其追加到列表中，而不是不断地连接+形成新列表。此时，可能还需要将递归转换为迭代循环。

from math import comb

def encode(pos, n, p):
if p == n:
return [1] * n
if p == 0:
return [0] * n
if pos < comb(n-1, p-1):
return [1] + encode(pos, n-1, p-1)
else:
return [0] + encode(pos - comb(n-1, p-1), n-1, p)
def decode(value, n, p):
if all(value):
return 0
if not any(value):
return 0
head, *tail = value
if head == 1:
return decode(tail, n-1, p-1)
else:
return comb(n-1, p-1) + decode(tail, n-1, p)

的例子:

for i in range(6):
e = encode(i, 4, 2)
d = decode(e, 4, 2)
print(i, e, i == d)

输出:

0 [1, 1, 0, 0] True
1 [1, 0, 1, 0] True
2 [1, 0, 0, 1] True
3 [0, 1, 1, 0] True
4 [0, 1, 0, 1] True
5 [0, 0, 1, 1] True