重复排列

本文关键字：排列 | 更新日期: 2023-09-27 18:17:40

如果你能找到更好的标题，请编辑。

我首先要说的是，我已经看过了关于这个主题的几个问题，主要是这篇文章和这篇文章，但没有找到解决这个问题的方法:

给定单词"HALLOWEEN"，我想找到所有长度的所有排列和组合。我尝试的第一件事是遍历下面的代码，让它的长度从1开始，一直到达到单词(9)的长度。

public static IEnumerable<IEnumerable<T>>
        GetPermutations<T>(IEnumerable<T> list, int length)
    {
        if (length == 1) return list.Select(t => new T[] {t});
        return GetPermutations(list, length - 1)
            .SelectMany(t => list.Where(e => !t.Contains(e)),
                (t1, t2) => t1.Concat(new T[] {t2}));
    }

这给了我意想不到的结果，因为省略了两个'E'和'L'，使得最终集合很短。

一个更简单的例子可以是'MOM' {M,O,M}，其中最终结果集将是:

  • O

  • 密苏里州

  • OM

  • 毫米

  • 妈妈

  • MMO

  • 石

注意，我希望看到两个"M"都可用，但我不希望看到结果是"MMM"。"MOM"将在结果中出现两次，因为保留原始顺序(1,2,3)，并且交换位置1和3(3,2,1)都会导致'M'，'O'，'M'，但这个字符序列只出现一次，是结果列表(可以通过字符串比较来完成)

同样，对于set{1,1,2,3}，我希望看到:

{1}

重复排列

这是另一个应该清晰易懂的解决方案:

    public static IEnumerable<string> GetPermutations(string input)
    {
        if (string.IsNullOrEmpty(input))
        {
            return new List<string>();
        }
        var length = input.Length;
        var indices = Enumerable.Range(0, length).ToList();
        var permutationsOfIndices = GetNumericalPermutations(indices, length);
        var permutationsOfInput = permutationsOfIndices.Select(x => new string(x.Select(y => input[y]).ToArray()))
                                                       .Distinct();
        return permutationsOfInput;
    }

    private static List<List<int>> GetNumericalPermutations(List<int> values, int maxLength)
    {
        if (maxLength == 1)
        {
            return values.Select(x => new List<int>{x}).ToList();
        }
        else
        {
            var permutations = GetNumericalPermutations(values, maxLength - 1);
            foreach (var index in values)
            {
                var newPermutations = permutations.Where(x => !x.Contains(index))
                                                  .Select(x => x.Concat(new List<int> { index }))
                                                  .Where(x => !permutations.Any(y => y.SequenceEqual(x)))
                                                  .Select(x => x.ToList())
                                                  .ToList();
                permutations.AddRange(newPermutations);
            }
            return permutations;
        }
    }

例如，"MOM"的输出是:

M
O
OM
MM
MO
MMO
OMM
MOM

我建议查看字母位置0、1、2、3、4等的排列，将它们映射到字母，然后消除重复的字母。

在不更改GetPermutations函数的情况下，我添加了另一个函数来获取字母位置的排列，将这些结果映射到字符串，然后消除重复项。

public void PermutationsTestMethod()
{
    GetPermutationsOfString("MOM").ForEach(v => Debug.Print(v));
}
public List<string> GetPermutationsOfString(string value)
{
    var resultList = new List<string>();
    for (var i = 1; i <= value.Length; i++)
    {
        var permutations = GetPermutations(Enumerable.Range(0, value.Length), i);
        resultList.AddRange(
            permutations
                .Select(v => new string(v.Select(z => value[z]).ToArray()))
                .Distinct()
            );
    }
    return resultList;
}
public static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> list, int length)
{
    if (length == 1) return list.Select(t => new T[] { t });
    return GetPermutations(list, length - 1)
        .SelectMany(t => list.Where(e => !t.Contains(e)),
            (t1, t2) => t1.Concat(new T[] { t2 }));
}

运行正常:

Func<string, IEnumerable<string>> getAllSubsets = null;
getAllSubsets = x =>
    (x == null || !x.Any())
        ? Enumerable.Empty<string>()
        :  (x.Length > 1
            ? getAllSubsets(x.Substring(1))
                .SelectMany(y => new [] { y, x.Substring(0, 1) + y })
            : new [] { "", x.Substring(0, 1) });

给定getAllSubsets("ABC")，我得到:

"， "A"， "B"， "AB"， "C"， "AC"， "BC"， "ABC"

对于"MOM"的例子，我得到:

"， "M"， "O"， "MO"， "M"， "MM"， "OM"， "MOM"

如果需要的话，过滤掉空字符串和重复的值是微不足道的，但它严格生成所有子集。

我认为通常最好尽量避免生成和消除排列。像"aaaaaaaaaaaaaaaaaaaaab"这样的文本会产生大量的重复。

public static IEnumerable<IEnumerable<T>>
GetPermutationsInner<T>(IEnumerable<IGrouping<T, T>> groupedList, int length)
{
    if (length == 1) return groupedList.Select(t => new T[] { t.Key });
    return GetPermutationsInner<T>(groupedList, length - 1)
        .SelectMany(t => groupedList
                .Where(e => t.Count(w => w.Equals(e.Key)) < e.Count())
                .Select(s => s.Key),
            (t1, t2) => t1.Concat(new T[] { t2 }));
}
public static IEnumerable<IEnumerable<T>>
    GetPermutations<T>(IEnumerable<T> list)
{
    var resultList = new List<IEnumerable<T>>();
    for (int i = 1; i <= list.Count(); ++i)
    {
        resultList.AddRange(GetPermutationsInner<T>(list.GroupBy(g => g), i));
    }
    return resultList;
}
相关文章：