Scrambling a string

Question

How would one go about scrambling a string such as the following, so that every possible permutation is achieved? Is there a LINQ method for such an effort? I have searched Google, but could not find anything on it.

STRING = "Little Red Riding Hood"

Answer 1

Here's a full sample program:

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

namespace ConsoleApplication2
{
    internal class Program
    {
        private static void Main(string[] args)
        {
            var sentences = new List<string>
            {
                "Little Red Riding Hood",
                "Three Little Pigs",
                "Jack and the Beanstalk"
            };

            foreach (var sentence in sentences)
            {
                Console.WriteLine("----------------------------------");

                foreach (var permutation in Permute(sentence.Split(' ')))
                {
                    foreach (string word in permutation)
                    {
                        Console.Write(word + " ");
                    }

                    Console.WriteLine();
                }
            }

            // If you want to put all the permutations for all the sentences into a List<string>, you can just do this:

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

            foreach (var sentence in sentences)
            {
                permutations.AddRange(Permute(sentence.Split(' ')).Select(perm => string.Join(" ", perm)));
            }

            Console.WriteLine("The total number of perms is: " + permutations.Count);
        }

        /// <summary>
        /// Provides a sequence of enumerators for obtaining all permutations of a sequence.
        /// Each enumeration in the returned sequence itself enumerates one of the permutations of the input sequence.
        /// Use two nested foreach statements to visit each item in each permuted sequence.
        /// </summary>

        public static IEnumerable<IEnumerable<T>> Permute<T>(IEnumerable<T> sequence)
        {
            return permute(sequence, sequence.Count());
        }

        // Returns an enumeration of enumerators, one for each permutation of the input.

        private static IEnumerable<IEnumerable<T>> permute<T>(IEnumerable<T> sequence, int count)
        {
            if (count == 0)
            {
                yield return new T[0];
            }
            else
            {
                int startingElementIndex = 0;

                foreach (T startingElement in sequence)
                {
                    IEnumerable<T> remainingItems = allExcept(sequence, startingElementIndex);

                    foreach (IEnumerable<T> permutationOfRemainder in permute(remainingItems, count - 1))
                    {
                        yield return concat<T>(new T[] { startingElement }, permutationOfRemainder);
                    }

                    ++startingElementIndex;
                }
            }
        }

        // Implements the recursive part of Permute<T>

        private static void permute<T>(T[] items, int item, T[] permutation, bool[] used, Action<T[]> output)
        {
            for (int i = 0; i < items.Length; ++i)
            {
                if (!used[i])
                {
                    used[i] = true;
                    permutation[item] = items[i];

                    if (item < (items.Length - 1))
                    {
                        permute(items, item + 1, permutation, used, output);
                    }
                    else
                    {
                        output(permutation);
                    }

                    used[i] = false;
                }
            }
        }

        // Enumerates over all items in the input, skipping over the item with the specified index.

        private static IEnumerable<T> allExcept<T>(IEnumerable<T> input, int indexToSkip)
        {
            int index = 0;

            foreach (T item in input)
            {
                if (index != indexToSkip)
                {
                    yield return item;
                }

                ++index;
            }
        }

        // Enumerates over contents of two lists sequentially.

        private static IEnumerable<T> concat<T>(IEnumerable<T> a, IEnumerable<T> b)
        {
            foreach (T item in a)
            {
                yield return item;
            }

            foreach (T item in b)
            {
                yield return item;
            }
        }
    }
}

Answer 2

There are methods in the C++ Standard Template Library (STL), but I believe those are not accessible (in any maningful way) from C#. I believe you would have to write a little C++ wrapper for the STL and invoke that from C#; or code the permutations in C#.

Update:

Generating all permutations of N items is a necessary prelude to the Traveling Salesman Problem (TSP). Algorithms for this are all over the web, which will explain generating the permutaions in various possible sequential and parallel algorithms en passant.

Answer 3

This is an excellent permutation library I have used in the past. The article has a code snippet included that I believe would match your needs well (which I've slightly adapted):

var inputSet = myString.ToCharArray();
var P2 = new Permutations<char>(inputSet, 
      GenerateOption.WithRepetition);
string format2 = "Permutations of {{A A C}} with Repetition; size = {0}";
Console.WriteLine(String.Format(format2, P2.Count));
foreach(IList<char> p in P2) {
  Console.WriteLine(String.Format("{{{0} {1} {2}}}", p[0], p[1], p[2]));
}

Answer 4

You want to do the Knuth/Fisher-Yates shuffle with the characters of the string.

Here are a bunch of C# implementations which you can adapt to a string instead of an array: Is using Random and OrderBy a good shuffle algorithm?