6
$\begingroup$

I just had a fun visit from a time traveller and she offered to whisk me off for a whirlwind tour – she offered to take me to observe any one time for each of any choice of distinct years from $1$C.E. to last year ($2015$C.E., if you didn't know!), one for each of the $37$ full solar years I have been alive[1].

Well, not knowing much about history, having chosen to study mathematics instead at every possible opportunity, I chose to visit the time I was born on my birthday from each of the years in the floored middle[2] of the list of my possible choices, after sorting each choice in descending order[3] and then sorting that list in descending order[4].

Even with this somewhat uneducated choice of years it was quite a blast, but the time travelling wiped notes I had taken on my phone
...which years did I visit?


Notes:

  1. That is I chose exactly $37$ distinct years from $[1, 2015]$. I could have done this in $2015 \choose 37$ different ways; this number is also sometimes written $_{2015}\mathrm{C}_{37}$.
  2. The floored middle of a list of $n$ items, indexed from $0$ to $n-1$, would be at index: $$\text{index}=\Big\lfloor\frac{n-1}2\Big\rfloor= \begin{cases} n\text{ even}&\implies\text{index}=\frac{n}2-1\\ n\text{ odd}&\implies\text{index}=\frac{n-1}2 \end{cases}$$
  3. For example, the years $1$ to $3$, the year $1066$ and the years $1983$ to $2015$ collectively are a subset of $[1, 2015]$ that has $37$ members. Thus, this is an example of the selection that I could have made. I am using the word "choice" to refer to such a selection. This example selection would be sorted as:$$(2015,2014,2013,\ldots,1984,1983,1066,3,2,1)$$
  4. Thus the first, second, penultimate and last entries in the list would be:$$(2015,2014,2013,\ldots1982,1981,1980,1979)$$$$(2015,2014,2013,\ldots1982,1981,1980,1978)$$ $$\vdots$$ $$(38,36,35,\ldots,3,2,1)$$$$(37,36,35,\ldots,3,2,1)$$
$\endgroup$
  • 1
    $\begingroup$ This is fun, but the story is a bit flawed (or 'floored', haha). Why would such a math whiz who knows the exact mathematical method he used to originally pick the years suddenly not know those years because the notes he took on his phone were wiped? Also, I'm no date expert but according to Wikipedia year 0 doesn't exist in the "Common Era" which I'm presuming is what C.E. means after the years... en.wikipedia.org/wiki/0_%28year%29 $\endgroup$ – jhabbott Apr 1 '16 at 16:35
  • $\begingroup$ @jhabbott Edited to [1, 2015] since no 0C.E exists - thank you. Yes, I have the method, maybe I a have popped over to your house in excitement but you don't want my grubby mitts touching your keyboard? (Which would be fair enough; never know where they've been!) $\endgroup$ – Jonathan Allan Apr 1 '16 at 17:18
  • $\begingroup$ This question really seems like nonsense to me. What is the "list of possible choices" it refers to? It comes out of nowhere. $\endgroup$ – Blckknght Apr 2 '16 at 0:10
  • $\begingroup$ @Blckknght the choice I have is which of the $37$ distinct years to visit of the last $2015$ years prior to this year, as described in the first paragraph. The list of possible choices is all the choices I could make. So, if I had been $3$ years old and the year was $5$C.E instead I'd be choosing $3$ distinct years from $[1,5)=\{1,2,3,4\}$, so I'd have had $_4C_3=4$ possible choices of three years that I could choose, sorting them each into descending order and then sorting that list into descending order would be: $[(4,3,2),(4,3,1),(4,2,1),(3,2,1)]$, the floored middle would then be $(4,2,1)$ $\endgroup$ – Jonathan Allan Apr 2 '16 at 0:38
  • $\begingroup$ I could not understand this question until I read the comments.  As I understand the terminology, you made $37$ choices; hence the phrase “$2015~choose~37$.  Your use of the word “choice” to refer to the set of $37~choices$ baffled me. … … … … … … … … … … … … … … … … … … … I considered rewriting the definition of “floored middle” to refer to a list of $n$ items, indexed from $\mathit{1~}$to $n$, but I didn’t want to tamper with your content too much. $\endgroup$ – Peregrine Rook Jul 10 '16 at 6:00
3
$\begingroup$

My crude python code tells me

[1978, 1974, 1934, 1919, 1843, 1722, 1658, 1655, 1568, 1541, 1519, 1453, 1280, 1260, 986, 944, 916, 833, 787, 773, 764, 756, 728, 709, 635, 632, 625, 594, 525, 518, 471, 467, 465, 455, 170, 90, 56]

This is what I ran for reference:

choose = [[0 for x in xrange(38)] for y in xrange(2150)]

for x in xrange(2020):
    choose[x][0] = 1
    for y in xrange(1,38):
        choose[x][y] = choose[x-1][y-1] + choose[x-1][y]

def rec(up_to, how_many, idx, li):
    if how_many == 0:
        print li
        return

    r = up_to
    while choose[r-1][how_many-1] <= idx:
        idx -= choose[r-1][how_many-1]
        r -= 1
    rec(r-1, how_many-1, idx, li+[r])

rec(2015, 37, (choose[2015][37]-1)/2, [])
$\endgroup$
  • $\begingroup$ hahh! you were a minute faster than me, and we have only 1 difference in the last number. i wonder which one is correct $\endgroup$ – elias Apr 1 '16 at 22:00
  • $\begingroup$ Did you remember that the index of the first list is 0? $\endgroup$ – ffao Apr 1 '16 at 22:05
  • $\begingroup$ Still using python 2?! $\endgroup$ – Jonathan Allan Apr 1 '16 at 22:09
  • $\begingroup$ nice work, ffao! $\endgroup$ – elias Apr 1 '16 at 22:11
  • 1
    $\begingroup$ To run it in Python 3, change the last line to rec(2015, 37, (choose[2015][37]-1)//2, []) (that double slash is so ugly, python 2 for life) $\endgroup$ – ffao Apr 1 '16 at 22:52
2
$\begingroup$

For me there is a little ambiguity in the question - might be because English is not a native language for me. But if I go to the direction which needs more thinking, and look for

the list consisting of the floored middle of elements on each indices of the possible lists

, the answer seems to be

1963, 1910, 1857, 1804, 1751, 1698, 1645, 1592, 1539, 1485, 1432, 1379, 1326, 1273, 1220, 1114, 1061, 1008, 955, 902, 849, 796, 743, 690, 637, 584, 531, 477, 424, 371, 318, 265, 212, 159, 106, 53

No really big trick in it,

using only that neither symmetry nor linearity is hurt during listing and averaging. You might need to realise, that the flooring of indices leads to rounding up at halves, but we don't really face this problem, as for the calculation you use only 1/19s, which never add up to 9.5/19. If you like university level maths, you can approach the problem with expected value of variables with a negative binomial distribution.

$\endgroup$
  • 2
    $\begingroup$ To clarify, I am asking for one of the two middle lists in the list of lists (the lower one). Your answer is not correct given the order I have described - I am afraid it would lie about $\frac1{10^{33}}$ of the way through my list of lists (at index 5605727798341790722739884994273271993964682800) $\endgroup$ – Jonathan Allan Apr 1 '16 at 20:19
  • $\begingroup$ ok, my bad, sorry. thanks for clarifying! $\endgroup$ – elias Apr 1 '16 at 20:21
  • $\begingroup$ FYI I saw your other answer before your edit, and no it's not that :) $\endgroup$ – Jonathan Allan Apr 1 '16 at 20:22
  • $\begingroup$ yes, that was a third interpretation :) $\endgroup$ – elias Apr 1 '16 at 20:23
2
$\begingroup$

After your clarification, some calculations on paper followed by python-programming, then correcting my bugs, and finally correcting my correction, I think the answer is

1978, 1974, 1934, 1919, 1843, 1722, 1658, 1655, 1568, 1541, 1519, 1453, 1280, 1260, 986, 944, 916, 833, 787, 773, 764, 756, 728, 709, 635, 632, 625, 594, 525, 518, 471, 467, 465, 455, 170, 90, 56

My code - with a recursion and memorization-free approach:

def binom(n,k):
  product = 1
  for i in range(k):
    product = product * (n-i) / (i+1)
  return product

def get_indexed_list(n,k,target):
  while (True):
    x = n - 1
    y = k - 1
    s = binom(x,y)
    if s < target:
      n=n-1
      target=target-s       
    elif s == target:
      print n
      for i in range(k-1, 0, -1):
        print i
      return
    else:
      print n
      n=n-1
      k=k-1

n = 2015
k = 37
t = (binom(n,k))/2
get_indexed_list(n,k,t)
$\endgroup$
  • $\begingroup$ thanks. might be a bug in the implementation, as i think it is quite clear, how to do the maths behind it, and i even checked it on smaller examples. working on it. $\endgroup$ – elias Apr 1 '16 at 21:40
  • 1
    $\begingroup$ ah, i realized the library i use for calculating binomial coefficients is not precise enough with large numbers. might need to write my own implementation :) $\endgroup$ – elias Apr 1 '16 at 21:49
  • $\begingroup$ Your most recent edit is closer, but not quite there yet $\endgroup$ – Jonathan Allan Apr 1 '16 at 22:07
  • $\begingroup$ ok, i got it. just introduced a minor modification to test even/odd cases, and left the to-be-uncommented line in the code. my bad again. a painful one this time. $\endgroup$ – elias Apr 1 '16 at 22:13
1
$\begingroup$

Here is my generic solution.

Code to perform $_nC_k$:

def choose(n, k):
    '''Returns the number of ways to choose k items from n items'''
    reflect = n - k
    if k > reflect:
        if k > n:
            return 0
        k = reflect
    if k == 0:
        return 1
    for nMinusIPlus1, i in zip(range(n - 1, n - k, -1), range(2, k + 1)):
        n = n * nMinusIPlus1 // i
    return n

Code to get the combination at index $index$ in a lexicographically sorted list of combinations which are each sorted in a descending order, where each combination was formed from choosing $k$ items from $n \in [0,n)$ items:

def iterCombination(index, n, k):
'''Yields the items of the single combination that would be at the provided
(0-based) index in a lexicographically sorted list of combinations of choices
of k items from n items [0,n), given the combinations were sorted in 
descending order. Yields in descending order.
'''
    if index < 0 or n < k or n < 1 or k < 1 or choose(n, k) <= index:
        return
    for i in range(k, 0, -1):
        d = (n - i) // 2 or 1
        n -= d
        while 1:
            nCi = choose(n, i)
            while nCi > index:
                d = d // 2 or 1
                n -= d
                nCi = choose(n, i)
            if d == 1:
                break
            n += d
            d //= 2
            n -= d
        yield n
        index -= nCi

To find our solution we need to reverse that list (get the reflected index instead hence the choose(n, k) + 1 rather than choose(n, k) - 1 ) and offset our entries to account for there being no year $0$C.E. hence the y + 1:

>>> n = 2015
>>> k = 37
>>> [y + 1 for y in iterCombination((choose(n, k) + 1) // 2, n, k)]
[1978, 1974, 1934, 1919, 1843, 1722, 1658, 1655, 1568, 1541, 1519, 1453, 1280, 1260, 986,
944, 916, 833, 787, 773, 764, 756, 728, 709, 635, 632, 625, 594, 525, 518, 471, 467, 465,
455, 170, 90, 56]

For completeness we can easily go the other way from an ascending ordered combination of items chosen from $[0,n)$, and due to the lexicographical order we do not need to specify $n$ (and $k$ is implicit since it is the combination's length):

def indexOfCombination(combination):
    '''Returns the (0-based) index the given combination would have if it were in a
    reverse-lexicographically sorted list of combinations of choices of 
    len(combination) items from any possible number of items (given the combination's
    length and maximum value).
    - combination must already be in descending order,
    and it's items drawn from the set [0,n).
    '''
    result = 0
    for i, a in enumerate(combination):
        result += choose(a, i + 1)
    return result

For example here I fetch our second entry at $index 1$ and then find its $index$ again:

>>> [y + 1 for y in iterCombination(choose(n, k) - 2, n, k)]
[2015, 2014, 2013, 2012, 2011, 2010, 2009, 2008, 2007, 2006, 2005, 2004, 2003, 2002, 2001,
2000, 1999, 1998, 1997, 1996, 1995, 1994, 1993, 1992, 1991, 1990, 1989, 1988, 1987, 1986,
1985, 1984, 1983, 1982, 1981, 1980, 1978]
>>>
>>> indexOfCombination([v - 1 for v in _[-1::-1]])
9441083764728504732265958974503719082051120462776858839487337159739517650004648
>>> choose(2015, 37) - 1 - _
1

If we are looking to find a bigger index from some even larger list we can remove the function calls we make to choose, cancel terms that they perform, and reduce the number of the modulo arithmetic functions we perform like so:

def iterCombination(index, n, k):
    '''Yields the items of the single combination that would be at the provided
    (0-based) index in a lexicographically sorted list of combinations of choices
    of k items from n items [0,n), given the combinations were sorted in 
    descending order. Yields in descending order.
    '''
    nCk = 1
    for nMinusI, iPlus1 in zip(range(n, n - k, -1), range(1, k + 1)):
        nCk *= nMinusI
        nCk //= iPlus1
    curIndex = nCk
    for k in range(k, 0, -1):
        nCk *= k
        nCk //= n
        while curIndex - nCk > index:
            curIndex -= nCk
            nCk *= (n - k)
            nCk -= nCk % k
            n -= 1
            nCk //= n
        n -= 1
        yield n
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.