Permutations (Python)

permutations.py

#!/usr/bin/env python

# file: permutations.py

# Copyright (c) 2011, Erik Nordstroem <contact@erikano.net>
#
# Permission to use, copy, modify, and/or distribute this software for any
# purpose with or without fee is hereby granted, provided that the above
# copyright notice and this permission notice appear in all copies.
#
# THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
# WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
# MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
# ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
# WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
# ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
# OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

class Node:
  def __init__ (self, l, lvl = 0, i = None):
    self.l = l      # list
    self.lvl = lvl  # level
    self.i = i      # leftmost element swaped by parent
    self.c = []     # children
    self.s = []     # swaps needed to create children

    self.swaps()
    self.permutations()

  def swaps (self):
    if ((len(self.l) - (self.lvl + 1)) > 0):
      for i in range(1, (len(self.l) - self.lvl)):
        for j in range((i - 1), -1, -1):
          if ((i < self.i) or (self.i is None)):
            self.s.append([i, j])

  def permutations (self):
    while (self.s):
      s_curr = self.s.pop()
      l_p = self.l[:]
      l_p[s_curr[0]] = self.l[s_curr[1]]
      l_p[s_curr[1]] = self.l[s_curr[0]]
      self.c.append(Node(l_p, (self.lvl + 1), s_curr[0]))

  def printPermutation (self, printChildren = False):
    print "%s%s"%("  "*self.lvl, self.l)
    if (printChildren):
      for child in self.c:
        child.printPermutation(True)

if __name__ == '__main__':
  n = Node([1, 2, 3])
  n.printPermutation(True)