Найти перестановку строк, включая один символ, используя C # или F #

Question

Я бы хотел сгенерировать список всех возможных перестановок строки, содержащей список переменных символов.Например, если у меня есть строка «ABC», я хотел бы иметь список, содержащий все возможные варианты, например: A, B, C, AB, BC.

Спасибо.

Answer 1

Трудно точно сказать, что вы хотите, но на основе вашего примера вы узнаете, как сделать то, что Я думаю, вы ищете в 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"]

Answer 2

Вот версия LINQ:

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

Используйте это так:

var ps = perm("abc");

И это будет выполнять ленивые вычисления.

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

Answer 3

Если вы ищете перестановку по индексу (вместо того, чтобы перебирать все перестановки), вы можете использовать систему нумерации, называемую factoradics ( Source ), чтобы найти их. Вот код из оригинальной статьи с более сильным стилем C # (оригинальный код очень похож на C ++ ish) и дженерики.

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

Answer 4

Проверьте этот фрагмент в F # Snippets

Answer 5

Здесь будут возвращены все перестановки (не различимые) для данной строки символов. это не быстро и не эффективно, но работает ...

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

Для использования:

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