[SciPy-Dev] Rank and Unrank functions

[Joseph Fox-Rabinovitz]

Lucas,

I'm unaware of any other computational application. Most of the references
I've read focus on the algorithm, implying that the uses are self-evident.
My use-case has always been combination and permutation sampling for
engineering applications, so I've never bothered to understand the
underlying mathematics too deeply, nor other possible applications.

This in and of itself may mean that the functions are best left as
utilities. At the same time, I feel that if I'm using something fairly
frequently that doesn't have a "standard" implementation, I should at least
ask.

I should also mention at some point that the implementation I have in mind
takes advantage of python's infinite precision integers. I'm currently
doing this in python, but it would be simple to implement in C to bypass
the loop and type checking overhead almost entirely.

Regards,

Joe


On Sun, May 10, 2020, 08:57 <rlucas7 at vt.edu> wrote:

> Hi Joe,
>
> Do you have references that include applications?
>
> The application I’m seeing on the wiki links relates to sampling k sets
> from a set of N elements without a full table scan.
>
> Are there other applications besides sampling?
>
> Sincerely,
>
> -Lucas Roberts
>
> On May 9, 2020, at 11:38 PM, Joseph Fox-Rabinovitz <
> jfoxrabinovitz at gmail.com> wrote:
>
> 
> Josh,
>
> I'm referring to a combinatorial number system:
> https://en.m.wikipedia.org/wiki/Combinatorial_number_system. Also
> mentioned here:
> https://en.m.wikipedia.org/wiki/Combination#Enumerating_k-combinations.
>
> This is something I've made small utilitity functions for a couple of
> times. For a formal implementation, I've got a couple of peer reviewed
> papers for reference, and some different options for features, like with
> and without repetition. I'd prefer not to do the extra work if this is too
> niche though.
>
> Regards,
>
> Joe
>
>
>
> On Sat, May 9, 2020, 11:02 Joshua Wilson <josh.craig.wilson at gmail.com>
> wrote:
>
>> > but no rank and unrank to convert linear indices to combination or
>> permutation
>>
>> Could you point to a definition of these functions? I'm actually not
>> sure what you mean.
>>
>> - Josh
>>
>> On Fri, May 8, 2020 at 12:12 PM Joseph Fox-Rabinovitz
>> <jfoxrabinovitz at gmail.com> wrote:
>> >
>> > Scipy.special has the functions comb and perm but no rank and unrank to
>> convert linear indices to combination or permutation. These are fairly
>> useful for generating random sequences from large sets. Is there any
>> objection to a PR implementing these functions?
>> >
>> > The signatures I had in mind are
>> >
>> > perm_rank(indices, n, k)
>> > perm_unrank(index, n, k)
>> > comb_rank(indices, n, k)
>> > comb_unrank(index, n, k)
>> >
>> > Regards,
>> >
>> > Joe
>> > _______________________________________________
>> > SciPy-Dev mailing list
>> > SciPy-Dev at python.org
>> > https://mail.python.org/mailman/listinfo/scipy-dev
>> _______________________________________________
>> SciPy-Dev mailing list
>> SciPy-Dev at python.org
>> https://mail.python.org/mailman/listinfo/scipy-dev
>>
> _______________________________________________
> SciPy-Dev mailing list
> SciPy-Dev at python.org
> https://mail.python.org/mailman/listinfo/scipy-dev
>
> _______________________________________________
> SciPy-Dev mailing list
> SciPy-Dev at python.org
> https://mail.python.org/mailman/listinfo/scipy-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20200510/5a5d1e54/attachment-0001.html>