DZone Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

Aniruddha has posted 40 posts at DZone. View Full User Profile

Find All Permutations of string - C#

06.02.2012
| 10008 views |
  • submit to reddit
// 1. remove first char 
// 2. find permutations of the rest of chars
// 3. Attach the first char to each of those permutations.
//     3.1  for each permutation, move firstChar in all indexes to produce even more permutations.
// 4. Return list of possible permutations.

public string[] FindPermutations(string word)
        {
            if (word.Length == 2)
            {
                char[] _c = word.ToCharArray();
                string s = new string(new char[] { _c[1], _c[0] });
                return new string[]
                {
                    word,
                    s
                };
            }

            List<string> _result = new List<string>();

            string[] _subsetPermutations = FindPermutations(word.Substring(1));
            char _firstChar = word[0];
            foreach (string s in _subsetPermutations)
            {
                string _temp = _firstChar.ToString() + s;
                _result.Add(_temp);
                char[] _chars = _temp.ToCharArray();
                for (int i = 0; i < _temp.Length - 1; i++)
                {
                    char t = _chars[i];
                    _chars[i] = _chars[i + 1];
                    _chars[i + 1] = t;
                    string s2 = new string(_chars);
                    _result.Add(s2);
                }
            }
            return _result.ToArray();
        }

Find All Permutations of string - C#