# [Jelly], 16 [bytes]

    ‘ŒPŒcIQLƲÐṀLÐṂṬṚ

A monadic Link that accepts the ruler length, \$N\$, and yields all perfect rulers of length \$N\$ as lists of binary marks ordered numerically.

**[Try it online!][TIO-m3etrb7l]** Or see the [test-suite].

#### How?

If we can assert that a ruler has implicit marks of \$0\$ and \$N\$, which I believe is part of the definition of a [sparse ruler](https://en.wikipedia.org/wiki/Sparse_ruler), then we know that \$N\$ is always in the set of all distances a ruler can measure and hence \$k \ge N\$. At the same time, we cannot hope to measure any distance greater than \$N\$ (as that is the length of our ruler!), so \$k=N\$.

Thus I believe we can just look for those rulers of length up to \$N\$ with maximal measuring capability (i.e. the set \$\{1,2,\cdots,N\}\$) and then filter these rulers down to those with the fewest marks. (Please correct me if I've made a false assertion!)

    ‘ŒPŒcIQLƲÐṀLÐṂṬṚ - Link: non-negative integer, N
    ‘                - increment {N} -> N+1
     ŒP              - powerset {[1..N+1]}
                       -> [[],[1],[2],...,[N+1],[1,2],[1,3],...,[1..N+1]]
                          i.e. all rulers of length <=N where the 0-mark is represented
                               by a value of 1 or higher while no value may exceed N+1
                               (e.g. [1,3,8] & [2,4,9] both represent [0,2,7] when N>=9)
                               Note that there is, therefore, exactly one representation
                               present of every sparse-ruler of length N
             ÐṀ      - keep those maximal under:
            Ʋ        -   last four links as a monad:
       Œc            -     unordered pairs
         I           -     forward deltas
          Q          -     deduplicate
           L         -     length
                ÐṂ   - keep those minimal under:
               L     -   length
                  Ṭ  - untruth (convert to their binary representations)
                   Ṛ - reverse (equivalent to sorting by binary representation)


[Jelly]: https://github.com/DennisMitchell/jelly
[bytes]: https://github.com/DennisMitchell/jelly/wiki/Code-page

[TIO-m3etrb7l]: https://tio.run/##y0rNyan8//9Rw4yjkwKOTkr2DPQ5tunwhIc7G3xAZNPDnWse7pz1//9/MwA "Jelly – Try It Online"

[test-suite]: https://tio.run/##AUAAv/9qZWxsef//4oCYxZJQxZJjSVFMxrLDkOG5gEzDkOG5guG5rOG5mv/Dh1bFkuG5mOKBuCxq4oG@OsK2KVn//zEy "Jelly – Try It Online"