4 ms·

The coolest way to generate combinations (2009)

97 points by memorable 4y ago

freesports2022 4y ago
[flagged]
alexmolas 4y ago
Does somebody know if is there any repo that implements the algorithm?
- camel-cdr 4y ago
  I found one https://github.com/andrioni/Catalan.jl/blob/master/src/partitions.jl#L29 https://github.com/andrioni/Catalan.jl/blob/master/src/parti... I just searched for the doi with github search.
- Someone 4y ago
  https://gist.github.com/estliberitas/98647a02a23c59e8b9a0 https://gist.github.com/estliberitas/98647a02a23c59e8b9a0 claims to be one. (Used “cool-lex implementation” as search string)
- mkl 4y ago
  The pseudocode seems easy to follow: https://www.sciencedirect.com/science/article/pii/S0012365X07009570#aep-figure-id41 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)
  - deleted 4y ago
    [deleted]
- m1el 4y ago
  The pseudo-code is relatively easy to implement, but it's better to rename the variables. https://gist.github.com/m1el/6016b53ff20ae08712436a4b073820f2 https://gist.github.com/m1el/6016b53ff20ae08712436a4b073820f...
tromp 4y 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 4y 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!
deleted 4y ago
[deleted]

97 points by memorable 4y ago

freesports2022 4y ago

[flagged]

alexmolas 4y ago

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

camel-cdr 4y ago
I found one https://github.com/andrioni/Catalan.jl/blob/master/src/partitions.jl#L29 https://github.com/andrioni/Catalan.jl/blob/master/src/parti... I just searched for the doi with github search.
Someone 4y ago
https://gist.github.com/estliberitas/98647a02a23c59e8b9a0 https://gist.github.com/estliberitas/98647a02a23c59e8b9a0 claims to be one. (Used “cool-lex implementation” as search string)
mkl 4y ago
The pseudocode seems easy to follow: https://www.sciencedirect.com/science/article/pii/S0012365X07009570#aep-figure-id41 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)
- deleted 4y ago
  [deleted]
m1el 4y ago
The pseudo-code is relatively easy to implement, but it's better to rename the variables. https://gist.github.com/m1el/6016b53ff20ae08712436a4b073820f2 https://gist.github.com/m1el/6016b53ff20ae08712436a4b073820f...

tromp 4y 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 4y 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!

deleted 4y ago

[deleted]