The coolest way to generate combinations (2009)

https://www.sciencedirect.com/science/article/pii/S0012365X07009570

by memorable • 4 years ago

97 7 4 years ago

sciencedirect.com

alexmolas• 4 years ago

Does somebody know if is there any repo that implements the algorithm?

camel-cdr• 4 years ago

I found one https://github.com/andrioni/Catalan.jl/blob/master/src/parti...

I just searched for the doi with github search.

Someone• 4 years ago

https://gist.github.com/estliberitas/98647a02a23c59e8b9a0 claims to be one.

(Used “cool-lex implementation” as search string)

mkl• 4 years ago

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)

m1el• 4 years ago

The pseudo-code is relatively easy to implement, but it's better to rename the variables.

https://gist.github.com/m1el/6016b53ff20ae08712436a4b073820f...

tromp• 4 years 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".

dspillett• 4 years ago

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!

The coolest way to generate combinations (2009)

Related Stories