title: How to produce the i-th combination/permutation without iterating
body: <p>Given any iterable, for example: "ABCDEF"</p>
  
  <p>Treating it almost like a numeral system as such:</p>
  
  <p>A
  B
  C
  D
  E
  F
  AA
  AB
  AC
  AD
  AE
  AF
  BA
  BB
  BC
  ....
  FF
  AAA
  AAB
  ....</p>
  
  <p>How would I go about finding the i<sup>th</sup> member in this list?  Efficiently, not by counting up through all of them.  I want to find the billionth (for example) member in this list.  I'm trying to do this in python and I am using 2.4 (not by choice) which might be relevant because I do not have access to itertools.</p>
  
  <p>Nice, but not required: Could the solution be generalized for pseudo-<a href="http://en.wikipedia.org/wiki/Mixed_radix" rel="nofollow noreferrer">"mixed radix"</a> system?</p>
  
  <p>--- RESULTS ---</p>
  
  <pre><code># ------ paul -----
  def f0(x, alph='ABCDE'):
      result = ''
      ct = len(alph)
      while x&gt;=0:
          result += alph[x%ct]
          x /= ct-1
      return result[::-1]
  
  # ----- Glenn Maynard -----
  import math
  def idx_to_length_and_value(n, length):
      chars = 1
      while True:
          cnt = pow(length, chars)
          if cnt &gt; n:
              return chars, n
  
          chars += 1
          n -= cnt
  
  def conv_base(chars, n, values):
      ret = []
      for i in range(0, chars):
          c = values[n % len(values)]
          ret.append(c)
          n /= len(values)
  
      return reversed(ret)
  
  def f1(i, values = "ABCDEF"):
      chars, n = idx_to_length_and_value(i, len(values))
      return "".join(conv_base(chars, n, values))
  
  # -------- Laurence Gonsalves ------
  def f2(i, seq):
      seq = tuple(seq)
      n = len(seq)
      max = n # number of perms with 'digits' digits
      digits = 1
      last_max = 0
      while i &gt;= max:
          last_max = max
          max = n * (max + 1)
          digits += 1
      result = ''
      i -= last_max
      while digits:
          digits -= 1
          result = seq[i % n] + result
          i //= n
      return result
  
  # -------- yairchu -------
  def f3(x, alphabet = 'ABCDEF'):
      x += 1 # Make us skip "" as a valid word
      group_size = 1
      num_letters = 0
      while 1: #for num_letters in itertools.count():
          if x &lt; group_size:
              break
          x -= group_size
          group_size *= len(alphabet)
          num_letters +=1
      letters = []
      for i in range(num_letters):
          x, m = divmod(x, len(alphabet))
          letters.append(alphabet[m])
      return ''.join(reversed(letters))
  
  # ----- testing ----
  import time
  import random
  tries = [random.randint(1,1000000000000) for i in range(10000)]
  numbs = 'ABCDEF'
  
  time0 = time.time()
  s0 = [f1(i, numbs) for i in tries]
  print 's0 paul',time.time()-time0, 'sec'
  time0 = time.time()
  s1 = [f1(i, numbs) for i in tries]
  print 's1 Glenn Maynard',time.time()-time0, 'sec'
  time0 = time.time()
  s2 = [f2(i, numbs) for i in tries]
  print 's2 Laurence Gonsalves',time.time()-time0, 'sec'
  time0 = time.time()
  s3 = [f3(i,numbs) for i in tries]
  print 's3 yairchu',time.time()-time0, 'sec'
  </code></pre>
  
  <p>times: </p>
  
  <pre><code>s0 paul 0.470999956131 sec
  s1 Glenn Maynard 0.472999811172 sec
  s2 Laurence Gonsalves 0.259000062943 sec
  s3 yairchu 0.325000047684 sec
  &gt;&gt;&gt; s0==s1==s2==s3
  True
  </code></pre>