object Permutations {

  def main(args: Array[String]) {
    if (args.length != 1) {
      println("Usage: Permutations [num]")
    } else {
      print_permutations(args.head.toInt)
    }
  }

  def permutations[T](lst: List[T]): List[List[T]] = lst match {
    case Nil => List(Nil)
    case x :: xs => permutations(xs) flatMap { perm =>
      (0 to xs.length) map { num =>
        (perm take num) ++ List(x) ++ (perm drop num)
      }
    }
  }

  def print_permutations(n: Int) = {
    permutations((1 to n).toList) sortWith {
      case (xs, ys) => xs zip ys forall {
        case (a, b) => a < b
      }
    } foreach { lst =>
      lst foreach { elem =>
        print(s"$elem ")
      }
      println()
    }
  }

}