C# String permutation

Question

I have 5 strings, such as: "one", "two", "three", "four", and "five". I need to get all permutations of these strings. I've explored all internet resources, but all solutions are so bulky and it's hard for me to understand it and integrate it to my program.
So, maybe you know any easy solution how to get permutations.

Answer 1

Permutations are very easy to do.

/// <summary>
/// Returns all permutations of the input <see cref="IEnumerable{T}"/>.
/// </summary>
/// <param name="source">The list of items to permute.</param>
/// <returns>A collection containing all permutations of the input <see cref="IEnumerable&lt;T&gt;"/>.</returns>
public static IEnumerable<IEnumerable<T>> Permutations<T>(this IEnumerable<T> source)
{
    if (source == null)
        throw new ArgumentNullException("source");
    // Ensure that the source IEnumerable is evaluated only once
    return permutations(source.ToArray());
}

private static IEnumerable<IEnumerable<T>> permutations<T>(IEnumerable<T> source)
{
    var c = source.Count();
    if (c == 1)
        yield return source;
    else
        for (int i = 0; i < c; i++)
            foreach (var p in permutations(source.Take(i).Concat(source.Skip(i + 1))))
                yield return source.Skip(i).Take(1).Concat(p);
}

Answer 2

Here's a class that works in .Net 2.0. First, sort your array. Then use it by looping over while(Permute.Next(array)). When there are no more permutations, Permute.Next returns false.

using System;
using System.Collections.Generic;
using System.Text;

public class Permute
{
    public static bool Next(IList<IComparable> list)
    {
        int k = FindSmallestK(list);
        if (k < 0) return false;
        int l = FindLargestL(list, k);
        Swap(list, k, l);
        Reverse(list, k + 1);
        return true;
    }

    private static void Reverse(IList<IComparable> list, int p)
    {
        for (int i = p, j = list.Count - 1; i < j; i++, j--)
        {
            Swap(list, i, j);
        }
    }

    private static void Swap(IList<IComparable> list, int k, int l)
    {
        IComparable temp = list[k];
        list[k] = list[l];
        list[l] = temp;
    }

    private static int FindLargestL(IList<IComparable> list, int k)
    {
        for (int i = list.Count - 1; i > k; i--)
        {
            if (list[k].CompareTo(list[i]) < 0) return i;
        }
        return -1;
    }

    private static int FindSmallestK(IList<IComparable> list)
    {
        for (int i = 0; i < list.Count - 1; i++)
        {
            if (list[i].CompareTo(list[i + 1]) < 0) return i;
        }
        return -1;
    }
}

Answer 3

This article shows the complete code for getting all permutations of letters. Substitute letters with words and you have your solution:

http://www.codeproject.com/KB/recipes/Premutations.aspx

Answer 4

The permutation article on wikipedia has a good summary of some example algorithms

http://en.wikipedia.org/wiki/Permutation#Systematic_generation_of_all_permutations

Answer 5

This is a pretty nice combinatorics library - http://www.codeproject.com/KB/recipes/Combinatorics.aspx

Answer 6

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

namespace caComb
{
    class Program
    {
        private static List<List<string>> allCombinations = new List<List<string>>();
        static void Main(string[] args)
        {
            string[] words = new string[] { "one", "two", "three", "four", "five" };
            List<string> temp = new List<string>();
            GetCombinations(words, temp);
            // Here you can read all combinations from
            // allCombinations. Do whatever you want.
        }

        private static void GetCombinations(string[] words, List<string> temp)
        {
            if (temp.Count == words.Length)
            {
                List<string> clone = temp.ToList();
                if (clone.Distinct().Count() == clone.Count)
                {
                    allCombinations.Add(clone);
                }
                return;
            }

            for (int i = 0; i < words.Length; i++)
            {
                temp.Add(words[i]);
                GetCombinations(words, temp);
                temp.RemoveAt(temp.Count - 1);
            }

        }
    }
}