Hacker News new | past | comments | ask | show | jobs | submit login
The coolest way to generate combinations (2009) (sciencedirect.com)
95 points by memorable 2 days ago | hide | past | favorite | 7 comments

> 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 = [1]*t+[0]*s
      x = t
      y = t
      yield b.copy()
      while x < s+t:
          b[x-1] = 0
          b[y-1] = 1
          b[0] = b[x]
          b[x] = 1
          x = x + 1 - (x-1)*b[1]*(1-b[0])
          y = b[0]*y+1
          yield b.copy()
I checked that it gives the right number of combinations (math.comb(s+t, s)) for a whole lot of small s and t values, and that the combinations are all different:

  len(set(tuple(c) for c in cool_lex(s, t))) == math.comb(s+t, s)
It's late at night here though, so I can't vouch for its correctness!

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):
          print(s, t)
          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)

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact