ちなみに数分で、行き当たりばったりで書いてみたRubyのコードはこんな感じ
手作業でやる場合の手順をそのままコードに書いた、非常に手続き的な思考回路だと思う

class Array
 def my_permu
  return [] if empty?
  return [ns] if size == 1
  result = []
  each do |n|
   without_n = reject{|x| x == n }
   without_n.my_permu.each do |ary|
    result.push( [n] + ary )
   end
  end
  return result
 end
end
p (1..3).to_a.my_permu