MathGroup Archive 2011

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: how to calculate an index and vice versa

  • To: mathgroup at smc.vnet.net
  • Subject: [mg119294] Re: how to calculate an index and vice versa
  • From: Daniel Lichtblau <danl at wolfram.com>
  • Date: Sun, 29 May 2011 07:37:34 -0400 (EDT)

----- Original Message -----
> From: "ferradini" <gianmarco.ferradini at email.it>
> To: mathgroup at smc.vnet.net
> Sent: Saturday, May 28, 2011 6:20:12 AM
> Subject: [mg119277] how to calculate an index and vice versa
> given n numbers (eg. 1 to 90)
> I can build the following list of numbers k (in this case 4)
> 
> 1, 2, 3, 4 associated index -> 0
> 1, 2, 3, 5 associated index -> 1
> 1, 2, 3, 6 associated index -> 2
> 1, 2, 3, 7 associated index -> 3
> 1, 2, 3, 8 ................... ....
> 1, 2, 3, 9 .......................
> .......................
> .......................
> 10, 41, 60, 61 associated index -> 954722
> .......................
> .......................
> 87, 88, 89, 90 associated index -> 2555190
> I need to build an algorithm to assign eg 4 elemnti can obtain its
> index
> in the list
> (1, 2, 3, 7 return 3)
> 
> The second algorithm is 'inverse: given a number such as 954722 I get
> the four elements 87; 88, 89, 90.
> The elemnti in the list are always sorted values.
> 
> I thank those who will send me information on the subject to follow
> Thank ferradini

A pedestrian approach for the first is to count all possiblilites upward for the first value, then second, etc. Here is code for this.

indexnk[vals : {_Integer ..}, k_] := With[
  {vals2 = Prepend[vals, 0], n = Length[vals]},
  Sum[Binomial[k - i, n - j + 1], {j, 2, n + 1}, {i, 
     vals2[[j - 1]] + 1, vals2[[j]] - 1}] + 1
  ]

Example:

In[85]:= indexnk[{10, 41, 60, 61}, 90]
Out[85]= 954722

I thought this might be more summation than necessary, so did a we search. A useful link is

http://en.wikipedia.org/wiki/Combinatorial_number_system

It shows an ordering that is different, and indeed global for a fixed upper bound on values (adding new elements means going above former values). I adapted the idea there to get slightly faster code for the ordering under consideration.

indexnk2[vals : {_Integer ..}, k_] := With[
  {n = Length[vals], vals2 = Reverse[k - vals]},
  Binomial[k, n] - Sum[Binomial[vals2[[j]], j], {j, 1, n}]
  ]


In[86]:= indexnk2[{10, 41, 60, 61}, 90]
Out[86]= 954722

Two remarks.

(1) The inversion can be done by a method similar to these. One use a greedy algorithm to get as close to possible to the target at each step.

(2) Reverse engineering your ordering is not obvious (at least it wasn't to me). If you state in detail why the index of {10, 41, 60, 61}, 90] should be 954722 you might see a path to an algorithmic computation. At the least it will become easier for others to assist.


Daniel Lichtblau
Wolfram Research


  • Prev by Date: Re: Using a Mathematica Program to write a Mathematica Program
  • Next by Date: Re: Precedence question
  • Previous by thread: Re: how to calculate an index and vice versa
  • Next by thread: Re: how to calculate an index and vice versa