Ordered (n choose p) binary encoding and decoding

Question

I want to 'impose' order on (n choose p) binary and be able to encode/decode items.

Below you can see an example of p=2. For p > 2 it will need more loops. BTW this function is just illustration on ONE specific order, it can be different one just have to exhaust all combinations.

What I'm after is the encode/decode !!

It will be even better if it uses the INDEX value instead of bitarray i.e. 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]

---

seems legit :

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

Below is a recursive implementation of encoding / decoding. I want to issue two caveats:

If you were to encode/decode outrageously large values, you could run into RecursionDepthExceeded exceptions, as with most recursion. However, this will require insanely large input values.

Secondly, this can be a lot slower than it needs to be, due to the list concatenation (used for simplicity). If performance is a concern, you should pass an accumulator, and append to the list rather than concatenating + forming new lists constantly. At that point, probably convert the recursion into an iterative loop as well.

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)

Example:

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

Output:

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