Find string permutation including the single character using C# or F#

I would like to generate a li开发者_如何转开发st of all possible permutations of a string containing a variable list of characters. For example if I have the string "ABC", I would like to have a list that contains all the possible variations, like: A, B, C, AB, BC.

Thank you.

It's hard to tell exactly what you want, but based on your example output here's how to do what I think you're after in F#.

let combinations (s:string) =
  let rec loop acc i =
    seq {
      for i in i .. (s.Length - 1) do
        let acc = acc + s.[i..i]
        yield acc
        yield! loop acc (i + 1)
    }
  loop "" 0

combinations "ABC" |> Seq.toList //["A"; "AB"; "ABC"; "AC"; "B"; "BC"; "C"]

Here's a LINQ version:

Func<string, IEnumerable<string>> perm = t =>
{
    Func<string, string, IEnumerable<string>> perm2 = null;
    perm2 =
        (t0, t1s) =>
            from n in Enumerable.Range(0, t1s.Length)
            let c = t1s.Substring(n, 1)
            let x = t1s.Remove(n, 1)
            let h = t0 + c
            from r in (new [] { h, }).Concat(perm2(h, x))
            select r;
    return perm2("", t);
};

Use it like this:

var ps = perm("abc");

And it will perform a lazy computation.

var ps = perm("abcdefghijklmnopqrstuvwxyz").Take(2);
// Only computes two values when executed

Here will return all of the permutations (not distinct) given a string of chars. it's not fast or efficient, but it does work...

  public List<string> permute(string value, string prefix = "")
    {
        List<string> result = new List<string>();
        for (int x=0;x<value.Length;x++)
        {
            result.Add(prefix + value[x]);
            result.AddRange(permute( value.Remove(x, 1), prefix + value[x]));
        }
        return result;
    }

To use:

       List<string> output = permute("abc");

Check out this snippet at F# Snippets

If you are looking for a permutation by index (instead of having to iterate over all the permutations) you can use a numbering system called factoradics (Source) to find them. Here is the code from the original article, with a stronger C# style (the original code is very 'C++ish') and generics.

/// <summary>
/// Permutes the specified atoms; in lexicographical order.
/// </summary>
/// <typeparam name="T">The type of elements.</typeparam>
/// <param name="atoms">The atoms.</param>
/// <param name="index">The index of the permutation to find.</param>
/// <returns>The permutation.</returns>
public static IList<T> Permute<T>(this IList<T> atoms, int index)
{
    var result = new T[atoms.Count];
    Permute(atoms, result, index);
    return result;
}

/// <summary>
/// Permutes the specified atoms; in lexicographical order.
/// </summary>
/// <typeparam name="T">The type of elements.</typeparam>
/// <param name="atoms">The atoms.</param>
/// <param name="target">The array to place the permutation in.</param>
/// <param name="index">The index of the permutation to find.</param>
public static void Permute<T>(this IList<T> atoms, IList<T> target, int index)
{
    if (atoms == null)
        throw new ArgumentNullException("atoms");
    if (target == null)
        throw new ArgumentNullException("target");
    if (target.Count < atoms.Count)
        throw new ArgumentOutOfRangeException("target");
    if (index < 0)
        throw new ArgumentOutOfRangeException("index");

    var order = atoms.Count;

    // Step #1 - Find factoradic of k
    var perm = new int[order];
    for (var j = 1; j <= order; j++)
    {
        perm[order - j] = index % j;
        index /= j;
    }

    // Step #2 - Convert factoradic[] to numeric permuatation in perm[]
    var temp = new int[order];
    for (var i = 0; i < order; i++)
    {
        temp[i] = perm[i] + 1;
        perm[i] = 0;
    }

    perm[order - 1] = 1;  // right-most value is set to 1.
    for (var i = order - 2; i >= 0; i--)
    {
        perm[i] = temp[i];
        for (var j = i + 1; j < order; j++)
        {
            if (perm[j] >= perm[i])
                perm[j]++;
        }
    }

    // Step #3 - map numeric permutation to string permutation
    for (var i = 0; i < order; ++i)
    {
        target[i] = atoms[perm[i] - 1];
    }
}