[tgflynn]

If you think of an nxn matrix the set of all paths containing one element from each column has cardinality n^n. This is also the set of all functions from a set of cardinality n to itself or the set of all sequences of length n where each element is an element of a set of cardinality n.

Below is a procedure that generates it. The number of operations is actually sum from k =0 to k =n ( n^(n-k) ) but asymptotically that's still O( n^n ).

  def allFunctions( s, i = 0, count = 0 ):
 
    F = []
    if i == len( s ) - 1:
      return ( [ [ x ] for x in s ], len( s ) )
    (G,count) = allFunctions( s, i + 1, count )
    for g in G:
      for i in range( len( s ) ):
        F.append( g + [ s[i] ] )
        count += 1
    return ( F, count )

[cao825]

You rock.