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

Question

I would like to generate a list 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.

Is AB the same as BA? I.e., do you want to generate just AB or generate AB and BA? The former is printing all the combinations, the latter is printing all the permutations. — i_am_jorf, Aug 30 '11 at 01:59
See these other related questions: [Combinations and Permutations in F#](http://stackoverflow.com/q/4495597/636019), [Calculating permutations in F#](http://stackoverflow.com/q/286427/636019), [F# permutations](http://stackoverflow.com/q/1526046/636019). — ildjarn, Aug 30 '11 at 02:06

score 5 · Answer 1 · answered Aug 30 '11 at 02:57

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"]

score 2 · Accepted Answer · answered Aug 30 '11 at 04:59

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

score 1 · Answer 3 · answered Aug 30 '11 at 02:09

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");

score 1 · Answer 4 · answered Aug 30 '11 at 06:34

1

Check out this snippet at F# Snippets

answered Aug 30 '11 at 06:34

Ankur

33,367
2
46
72

score 1 · Answer 5 · answered Aug 30 '11 at 07:21

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];
    }
}

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

5 Answers5

Linked