title: Ordered set and natural bijection (combinatorial species)
body: <p>Let <code>A</code> some set (eg. <code>1000, 1001, 1002, ..., 1999</code>).</p>
  
  <p>Let <code>lessThan</code> some order relation function (eg. <code>(a lessThan b) &lt;-&gt; (a &gt; b)</code>).</p>
  
  <p>Let <code>index</code> a function (with inverse <code>index'</code>) mapping a <code>A</code> element to naturals.</p>
  
  <p>Example:</p>
  
  <pre><code>index a = 2000 - a
  index' n = 2000 - n
  </code></pre>
  
  <p>Exists some way to construct <code>index</code> (and <code>index'</code>) function for all (or some kinds of) <code>(A, lessThan)</code> pairs in P (polynomial time)?</p>
  
  <p>Best regards and thank's in advance!</p>
  
  <p><strong>EDITED</strong>: <code>A</code> could be a set by definition (eg. all combinations with repetition of another big subset), then, we can't suppose <code>A</code> is completely traversable (in P).</p>
  
  <p><strong>EDITED</strong>: another non trivial example, let <code>An</code> a set (with elements like <code>(x, y, p)</code>) whose elements are ordered clockwise into a <code>n X n</code> square, like this</p>
  
  <pre><code> 1    2    3    4
  12   13   14    5
  11   16   15    6
  10    9    8    7
  </code></pre>
  
  <p>then, we can map each triplet in <code>An</code> to <code>Bn = [1..n^2]</code> with <code>O(1)</code> (a polynomial).</p>
  
  <p>Given one <code>An</code> element we can <code>index</code> to <code>Bn</code> with <code>O(1)</code>.
  Given one <code>Bn</code> element we can <code>index'</code> to <code>An</code> with <code>O(1)</code>.</p>
  
  <pre><code>// Square perimeter; square x = 1, 2, 3, ...
  Func&lt;int, int, int&gt; perimeter = ( x, n ) =&gt; 4 * ( n - 2 * x + 1 ); 
  
  // Given main diagonal coordinates (1, 1), (2, 2), ... return cell number
  Func&lt;int, int, int&gt; diagonalPos = ( x, n ) =&gt; -4 * x * x + ( 4 * n + 8 ) * x - 4 * n - 3; 
  
  // Given a number, return their square
  Func&lt;int, int, int&gt; inSquare = ( z, n ) =&gt; (int) Math.Floor(n * 0.5 - 0.5 * Math.Sqrt(n * n - z + 1.0) + 1.0); 
  
  Func&lt;int, int, Point&gt; coords = ( z, n ) =&gt; { 
      var s = inSquare(z, n); 
      var l = perimeter(s, n) / 4; // length sub-square edge -1 
      var l2 = l + l; 
      var l3 = l2 + l; 
      var d = diagonalPos(s, n); 
      if( z &lt;= d + l ) 
          return new Point(s + z - d, s); 
      if( z &lt;= d + l2 ) 
          return new Point(s + l, s + z - d - l); 
      if( z &lt;= d + l3 ) 
          return new Point(s + d + l3 - z, s + l); 
      return new Point(s, s + d + l2 + l2 - z); 
  }; 
  </code></pre>
  
  <p>(I have read about "Combinatorial species", <a href="http://www.cs.tau.ac.il/~nachumd/papers/OrderedConstruction.pdf" rel="nofollow">"Ordered construction of combinatorial objects"</a>, <a href="http://hackage.haskell.org/package/species" rel="nofollow">"species" haskell package</a> and others)</p>