A simple piece of code based off of some C code at http://www.bearcave.com/random_hacks/permute.html , translated into C#, and then sped up a bit (400% or so on my system) with some base code at https://codeblog.jonskeet.uk/2013/06/22/array-covariance-not-just-ugly-but-slow-too/ provided by Jon Skeet.

Permutation.cs

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace Permute
{
  class Program
  {
    private const int Iterations = 1000;
    private const int Numbers = 9;
    private static int _level = -1;
    private static HashSet<InvariantArray<int>> _permutations = new HashSet<InvariantArray<int>>();
    private static InvariantArray<int> _values = new InvariantArray<int>(Numbers);

    static void Main(string[] args)
    {
      long counter = 0;
      for (int i = 0; i < Iterations; i++)
      {
        Reset();
        Stopwatch sw = new Stopwatch();
        sw.Start();
        Visit();
        sw.Stop();
        counter += sw.ElapsedMilliseconds;
      }

      double average = (double)counter / Iterations;
      Console.WriteLine("{0} stored average in {1} milliseconds", _permutations.Count, average);
    }

    private static void Reset()
    {
      _level = -1;
      _permutations = new HashSet<InvariantArray<int>>();
      _values = new InvariantArray<int>(Numbers);
    }

    private static void Visit(int index = 0)
    {
      _values[index] = ++_level;
      if (_level == Numbers)
      {
        Store();
      }
      else
      {
        for (int i = 0; i < Numbers; i++)
        {
          if (_values[i] != 0)
          {
            continue;
          }
          Visit(i);
        }
      }
      _level--;
      _values[index] = 0;
    }

    private static void Store()
    {
      _permutations.Add(new InvariantArray<int>(_values));
    }
  }


  public struct Wrapper<T> where T: struct
  {
    private readonly T _value;
    public T Value { get { return _value; } }

    public Wrapper(T value)
    {
      _value = value;
    }

    public static implicit operator Wrapper<T>(T value)
    {
      return new Wrapper<T>(value);
    }
  }

  public sealed class InvariantArray<T> where T: struct
  {
    private readonly Wrapper<T>[] _array;

    public InvariantArray(int size)
    {
      _array = new Wrapper<T>[size];
    }

    public T this[int index]
    {
      get { return _array[index].Value; }
      set { _array[index] = value; }
    }

    public List<T> ToList()
    {
      return _array.Select(wrapper => wrapper.Value).ToList();
    }

    public int Count { get { return _array.Length; } }

    public InvariantArray(InvariantArray<T> iat)
    {
      _array = new Wrapper<T>[iat.Count];
      for (int k = 0; k < iat.Count; k++)
      {
        _array[k] = iat[k];
      }
    }
  }
}