Code Kata: Anagrams

Let's do some code katas. Starting with ones from cyber-dojo. The programming language is in C#. Please let me know if  you have any comments. Thanks~

Problem:

Write a program to generate all potential
anagrams of an input string.

For example, the potential anagrams of "biro" are

biro bior brio broi boir bori
ibro ibor irbo irob iobr iorb
rbio rboi ribo riob roib robi
obir obri oibr oirb orbi orib

Solution:

The solution comes with two flavors: recursive and non-recursive ones. The recursive one is more intuitive and easier to come up with. The non-recursive one I had to reference from the existing Knuth algorithms.

Source Code:

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

namespace _01_Anagrams
{
    class Anagrams
    {
        static void Main(string[] args)
        {
            RecursivePermutation();
            NonRecursivePermutation();
        }

        private static void RecursivePermutation()
        {
            new Anagrams().ProduceAnagrams("biro", "");
        }

        private static void NonRecursivePermutation()
        {
            Permutation perm = new Permutation("biro");
            do
            {
                string value = perm.GetNext();
                Debug.WriteLine(value);
            }
            while (perm.NextPermutation());
        }

        private void ProduceAnagrams(string input, string prefix)
        {
            for (int i = 0; i < input.Length; i++)
            {
                if (input.Length > 1)
                {
                    string remainingInput = input.Remove(i, 1);
                    ProduceAnagrams(remainingInput, prefix + input[i]);
                }
                else if (input.Length == 1)
                {
                    Debug.WriteLine(prefix + input[i]);
                }
            }
        }
    }

    class Permutation
    {
        private List<string> _input = new List<string>();
        private int[] _indices;

        public Permutation(string input)
        {
            foreach (char c in input)
                _input.Add(c.ToString());
            _indices = new int[input.Length];
            for (int i = 0; i < _indices.Length; i++)
                _indices[i] = i;
        }

        public string GetNext()
        {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < _indices.Length; i++)
                sb.Append(_input[_indices[i]]);
            return sb.ToString();
        }

        public bool NextPermutation()
        {
            int i, j, l;
            for (j = _input.Count - 2; j >= 0; j--)
                if (_indices[j + 1] > _indices[j])
                    break;
            if (j == -1)
                return false;
            
            for (l = _input.Count - 1; l > j; l--)
                if (_indices[l] > _indices[j])
                    break;
            
            int swap = _indices[j];
            _indices[j] = _indices[l];
            _indices[l] = swap;

            for (i = j + 1; i < _input.Count; i++)
            {
                if (i > _indices.Length - i + j)
                    break;
                swap = _indices[i];
                _indices[i] = _indices[_indices.Length - i + j];
                _indices[_indices.Length - i + j] = swap;
            }
            return true;
        }
    }
}