需要递归生成文件数组的每个唯一组合

Question

我研究并发现很多类似的请求，但没有一个完全符合我的需要。

这是我的问题。我正在使用 C# 工作，并且有一个 FileInfo[] 数组，其中包含未知数量的元素。

FileInfo[] files = new FileInfo[]
{
    new FileInfo(@"C:\a.jpg"),
    new FileInfo(@"C:\b.jpg"),
    new FileInfo(@"C:\c.jpg"),
    new FileInfo(@"C:\d.jpg"),
    new FileInfo(@"C:\e.jpg"),
    new FileInfo(@"C:\f.jpg"),
    new FileInfo(@"C:\g.jpg"),
    new FileInfo(@"C:\h.jpg"),
    new FileInfo(@"C:\i.jpg"),
}; // Using 9 elements for this example

我需要生成这些文件的每种可能的重新排序组合的列表，而不重复这些文件。

因此，我的一些结果将是这样的（示例不是代码格式）：

a, b, c, d, e, f, g, h, i
a, b, c, d, e, f, g, i, h // i & h switched
a, b, c, d, e, f, h, g, i // last 3 elements switched

a, a, b, b, c, c, d, d, e // THIS IS NOT ACCEPTED, because elements are duplicated

依此类推，直到我想出每种可能的组合

所以结果总数应该是中元素数量的阶乘大批。在这个例子中，有9个元素，所以应该有9*8*7*6*5*4*3*2*1=362,880种可能的组合。

我已经把这个问题搞乱了好几天了，但我就是无法集中注意力。感谢任何帮助，尤其是代码示例！

谢谢！

Answer 1

使用 Linq 很容易：

IEnumerable<FileInfo[]> permutations =
    from a in files
    from b in files.Except(new[] { a })
    from c in files.Except(new[] { a, b })
    from d in files.Except(new[] { a, b, c })
    from e in files.Except(new[] { a, b, c, d })
    from f in files.Except(new[] { a, b, c, d, e })
    from g in files.Except(new[] { a, b, c, d, e, f })
    from h in files.Except(new[] { a, b, c, d, e, f, g })
    from i in files.Except(new[] { a, b, c, d, e, f, g, h })
    select new[] { a, b, c, d, e, f, g, h, i };

---

编辑：

这是一个通用解决方案，适用于任意数量的项目：

static class ExtensionMethods
{
    public static IEnumerable<IEnumerable<T>> GetPermutations<T>(this IEnumerable<T> source, int count)
    {
        IEnumerable<IEnumerable<T>> result = new[] { Enumerable.Empty<T>() }; 
        for (int i = 0; i < count; i++)
        {
            result =  
                from seq in result 
                from item in source.Except(seq)
                select seq.Concat(new[] { item }); 
        } 
        return result;
    }
}

按如下方式使用它：（

IEnumerable<IEnumerable<FileInfo>> permutations = files.GetPermutations(9);

此解决方案的灵感来自 Eric Lippert 关于笛卡尔积的文章。）

---

编辑 2：

这是使用 Aggregate：

static class ExtensionMethods
{
    public static IEnumerable<IEnumerable<T>> GetPermutations2<T>(this IEnumerable<T> source, int count)
    {
        IEnumerable<IEnumerable<T>> seed = new[] { Enumerable.Empty<T>() }; 
        return Enumerable.Repeat(source, count)
            .Aggregate(
                seed,
                (accumulator, sequence) =>
                    from acc in accumulator
                    from item in sequence.Except(acc)
                    select acc.Concat(new[] { item }));
    }
}

Answer 2

有多种算法可用于执行此操作。下面的页面列出了 3 个不同的：

计数并列出所有排列

Answer 3

您确实想要该集合的所有排列。

• http://www.codeproject.com/KB/recipes/Combinatorics.aspx
• http:// /blogs.msdn.com/b/updownroundnround/archive/2009/12/14/generating-all-permutations-c-enumerator-implementation.aspx

编辑：这里是您正在谈论的内容的示例： http://www.codeproject.com/KB/recipes/Premutations.aspx