97 points by memorable
17 days ago
> He refers to the listing as suffix-rotated (since he indices the bitstrings
While "indices" is a plural of the noun index, I have never seen it used as conjugation of the verb "to index".
Could be a typo from indexes that has been incorrectly auto-corrected?
I see that sort of thing happen in my own typing if I'm not being careful, which I'm often not!
Does somebody know if is there any repo that implements the algorithm?
The pseudocode seems easy to follow: https://www.sciencedirect.com/science/article/pii/S0012365X0...
Here's an (inefficient) implementation in Python:
def cool_lex(s, t):
b = *t+*s
x = t
y = t
while x < s+t:
b[x-1] = 0
b[y-1] = 1
b = b[x]
b[x] = 1
x = x + 1 - (x-1)*b*(1-b)
y = b*y+1
len(set(tuple(c) for c in cool_lex(s, t))) == math.comb(s+t, s)
Edit: I tried the following, to check more correctness. It was a bad idea! Ran out of RAM with 32GB on cool_lex(14, 15).
for s in range(1, 16):
for t in range(1, 16):
if len(set(tuple(c) for c in cool_lex(s, t))) != math.comb(s+t, s):
print('bad', s, t)
I found one https://github.com/andrioni/Catalan.jl/blob/master/src/parti...
I just searched for the doi with github search.
The pseudo-code is relatively easy to implement, but it's better to rename the variables.
https://gist.github.com/estliberitas/98647a02a23c59e8b9a0 claims to be one.
(Used “cool-lex implementation” as search string)