tromp 16 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".

  • dspillett 16 days 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!

alexmolas 16 days ago

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

  • mkl 16 days ago

    The pseudocode seems easy to follow:

    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)