生成 IEnumerable(Of T) 元素的所有唯一组合

发布于 2024-11-06 14:28:04 字数 1166 浏览 5 评论 0 原文

这个问题实际上与 this SO post 相同,只是我正在寻找一个VB.NET (.NET 4) 解决方案。我已经花了很长时间试图想出一个通用的解决方案来解决这个“电源组”问题。

鉴于:

Dim choices As IEnumerable(Of String) = {"Coffee", "Tea", "Milk", "Cookies"}
Dim choiceSets = choices.CombineAll()

我正在寻找 choiceSets 成为 IEnumerable(Of IEnumerable(Of T)) 这样我就可以做类似的事情:

For each choiceSet in choiceSets
    Console.WriteLine(String.Join(", ", choiceSet))
Next

并得到如下所示的结果

Coffee
Tea
Milk
Cookies
Coffee, Tea
Coffee, Milk
Coffee, Cookies
Tea, Milk
Tea, Cookies
Milk, Cookies
Coffee, Tea, Milk
Coffee, Tea, Cookies
Coffee, Milk, Cookies
Tea, Milk, Cookies
Coffee, Tea, Milk, Cookies

:您可以看到,这是来自源 IEnumerable(Of T) 的每个非重复组合(其中可能有 1 到多个项目 - 本示例只有 4 个) ,它根据源 IEnumerable(Of T) 中项目的顺序进行操作,并且列表中的每个项目 >= 内部 IEnumerable(Of T)

无论如何,这不是家庭作业;而是家庭作业。尽管感觉确实如此。

编辑:更新了示例,使其看起来不像结果按字母顺序排序,以强调使用源 IEnumerable(Of T) 的现有顺序,并添加了第四个选择来澄清排序要求每组内。

This question is virtually the same as this SO post, only I'm looking for a VB.NET (.NET 4) solution. I've spun my wheels long enough trying to come up with a generic solution to solving this "power set" problem.

Given:

Dim choices As IEnumerable(Of String) = {"Coffee", "Tea", "Milk", "Cookies"}
Dim choiceSets = choices.CombineAll()

I'm looking for choiceSets to be an IEnumerable(Of IEnumerable(Of T)) so that I can do something like:

For each choiceSet in choiceSets
    Console.WriteLine(String.Join(", ", choiceSet))
Next

And get results that look like:

Coffee
Tea
Milk
Cookies
Coffee, Tea
Coffee, Milk
Coffee, Cookies
Tea, Milk
Tea, Cookies
Milk, Cookies
Coffee, Tea, Milk
Coffee, Tea, Cookies
Coffee, Milk, Cookies
Tea, Milk, Cookies
Coffee, Tea, Milk, Cookies

As you can see, this is every non-repeating combination from the source IEnumerable(Of T) (which could have 1 to many items in it - this example only had 4), it operates based on the order of the items in the source IEnumerable(Of T), and each item in the list is >= the previous item in terms of number of items in the inner IEnumerable(Of T).

For what it's worth, this is not homework; though it sure does feel like it.

EDIT: Updated the example so it does not look like the result is alphabetically sorted, to stress that the source IEnumerable(Of T)'s existing order is used and added a 4th choice to clarify the sorting requirement within each set.

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(6

最佳男配角 2024-11-13 14:28:04

这是一个纯粹的 Linq 解决方案,灵感来自 Eric Lippert 的 关于计算笛卡尔积的博客文章。我稍微修改了 CartesianProduct 方法,使其返回组合:

public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<IEnumerable<T>> sequences)
{
    IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() };
    return sequences.Aggregate(
        emptyProduct,
        (accumulator, sequence) => 
        from accseq in accumulator 
        // Exclude items that were already picked
        from item in sequence.Except(accseq)
        // Enforce ascending order to avoid same sequence in different order
        where !accseq.Any() || Comparer<T>.Default.Compare(item, accseq.Last()) > 0
        select accseq.Concat(new[] {item})).ToArray();
}

基于此扩展方法,您可以生成所需的结果,如下所示:(

IEnumerable<string> items = new[] {"Coffee", "Tea", "Milk"};
IEnumerable<IEnumerable<string>> result =
    Enumerable.Range(1, items.Count())
        .Aggregate(
            Enumerable.Empty<IEnumerable<string>>(),
            (acc, i) =>
                acc.Concat(Enumerable.Repeat(items, i).Combinations()));

连接 1, 2... N 项的所有组合)

它 这可能不是一个非常有效的解决方案,但我认为这是 Linq 的一个有趣的使用...


编辑:这是一个新版本的 Combinations 方法,它保持原始顺序:

public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<IEnumerable<T>> sequences)
{
    var indexedSequences = sequences.Select(seq => seq.Select((item, idx) => new IndexedItem<T>(item, idx)));
    IEnumerable<IEnumerable<IndexedItem<T>>> emptyProduct = new[] { Enumerable.Empty<IndexedItem<T>>() };
    var indexedResult =
        indexedSequences.Aggregate(
            emptyProduct,
            (accumulator, sequence) => 
            from accseq in accumulator 
            // Exclude items that were already picked
            from item in sequence.Except(accseq)
            // Enforce ascending order of indexes to avoid same sequence in different order
            where !accseq.Any() || item.Index > accseq.Last().Index
            select accseq.Concat(new[] {item})).ToArray();
    return indexedResult.Select(seq => seq.Select(i => i.Item));
}

class IndexedItem<T>
{
    public IndexedItem(T item, int index)
    {
        this.Item = item;
        this.Index = index;
    }

    public T Item { get; private set; }
    public int Index { get; set; }
}

可能比以前的版本,但它完成了工作......

Here's a pure Linq solution, inspired by Eric Lippert's blog post about computing a cartesian product. I modified the CartesianProduct method slightly so that it returns combinations:

public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<IEnumerable<T>> sequences)
{
    IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() };
    return sequences.Aggregate(
        emptyProduct,
        (accumulator, sequence) => 
        from accseq in accumulator 
        // Exclude items that were already picked
        from item in sequence.Except(accseq)
        // Enforce ascending order to avoid same sequence in different order
        where !accseq.Any() || Comparer<T>.Default.Compare(item, accseq.Last()) > 0
        select accseq.Concat(new[] {item})).ToArray();
}

Based on this extension method, you can produce the desired result as follows:

IEnumerable<string> items = new[] {"Coffee", "Tea", "Milk"};
IEnumerable<IEnumerable<string>> result =
    Enumerable.Range(1, items.Count())
        .Aggregate(
            Enumerable.Empty<IEnumerable<string>>(),
            (acc, i) =>
                acc.Concat(Enumerable.Repeat(items, i).Combinations()));

(it concatenates all combinations of 1, 2... N items)

Note that it's probably not a very efficient solution, but I think it's an interesting use of Linq...


EDIT: here's a new version of the Combinations method that maintains the original order:

public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<IEnumerable<T>> sequences)
{
    var indexedSequences = sequences.Select(seq => seq.Select((item, idx) => new IndexedItem<T>(item, idx)));
    IEnumerable<IEnumerable<IndexedItem<T>>> emptyProduct = new[] { Enumerable.Empty<IndexedItem<T>>() };
    var indexedResult =
        indexedSequences.Aggregate(
            emptyProduct,
            (accumulator, sequence) => 
            from accseq in accumulator 
            // Exclude items that were already picked
            from item in sequence.Except(accseq)
            // Enforce ascending order of indexes to avoid same sequence in different order
            where !accseq.Any() || item.Index > accseq.Last().Index
            select accseq.Concat(new[] {item})).ToArray();
    return indexedResult.Select(seq => seq.Select(i => i.Item));
}

class IndexedItem<T>
{
    public IndexedItem(T item, int index)
    {
        this.Item = item;
        this.Index = index;
    }

    public T Item { get; private set; }
    public int Index { get; set; }
}

Probably even more inefficient than the previous version, but it gets the job done...

和影子一齐双人舞 2024-11-13 14:28:04

如果它对其他人有用,我已经转换了 Thomas Levesque 发布到 VB.NET 的原始 C# 扩展:

    <System.Runtime.CompilerServices.Extension()> _
    Public Function Combinations(Of T)(ByVal sequences As IEnumerable(Of IEnumerable(Of T))) As IEnumerable(Of IEnumerable(Of T))
        Dim seed As IEnumerable(Of IEnumerable(Of T)) = {  Enumerable.Empty(Of T) }
        Dim r = sequences.Aggregate(seed, 
             Function(ByVal accumulator, ByVal sequence) _
               From accseq In accumulator    _
               From item In sequence.Except(accseq) _
               Where (Not accseq.Any()) OrElse Comparer(Of T).Default.Compare(item, accseq.Last()) > 0  _
               Select accseq.Concat(  {item}  ) ).ToArray()
        Return r
    End Function

必须调用 Repeat n 次才能生成包含所有可能值 n 的集合的重复 Enumerable,这种用法有点尴尬次,其中 n 是 T 的每个唯一组合中的元素数量,但它可以完成工作。结果的顺序对我来说并不重要,所以我没有转换稍后发布的“索引”版本。

这是我对扩展的使用,它对整数数组而不是字符串进行操作,并为我提供其中没有元素的“空”集和“完整”(或原始)集

    Dim allRolesArray  = {1,4,5,2,0}
    Dim comboCountValues = Enumerable.Range(0, allRolesArray.Count()+1)
    Dim allRoleCombos = comboCountValues.Aggregate(
        Enumerable.Empty(Of IEnumerable(Of Integer))(),
        Function (acc, i) acc.Concat(Enumerable.Repeat(allRolesArray, i).Combinations() ) ).ToList

In case it's of use to anyone else, I've converted the original C# extension Thomas Levesque posted to VB.NET:

    <System.Runtime.CompilerServices.Extension()> _
    Public Function Combinations(Of T)(ByVal sequences As IEnumerable(Of IEnumerable(Of T))) As IEnumerable(Of IEnumerable(Of T))
        Dim seed As IEnumerable(Of IEnumerable(Of T)) = {  Enumerable.Empty(Of T) }
        Dim r = sequences.Aggregate(seed, 
             Function(ByVal accumulator, ByVal sequence) _
               From accseq In accumulator    _
               From item In sequence.Except(accseq) _
               Where (Not accseq.Any()) OrElse Comparer(Of T).Default.Compare(item, accseq.Last()) > 0  _
               Select accseq.Concat(  {item}  ) ).ToArray()
        Return r
    End Function

It's a bit awkward usage to have to call Repeat n times to generate a repeated Enumerable containing the set of all possible values n times, where n is the number of elements in each resulting unique combination of T, but it gets the job done. Order of the results didn't matter for me, so I didn't convert the 'indexed' version posted later.

Here's my usage of the extension, which operates on an array of Integers instead of Strings, and gets me the 'empty' set with no elements in it and the 'full' (or original) set

    Dim allRolesArray  = {1,4,5,2,0}
    Dim comboCountValues = Enumerable.Range(0, allRolesArray.Count()+1)
    Dim allRoleCombos = comboCountValues.Aggregate(
        Enumerable.Empty(Of IEnumerable(Of Integer))(),
        Function (acc, i) acc.Concat(Enumerable.Repeat(allRolesArray, i).Combinations() ) ).ToList
半葬歌 2024-11-13 14:28:04

我发现另一个 此处的方法(在此处查找 C# 代码)。

    Public Function GetPowerSet(Of T)(items As IEnumerable(Of T)) As IEnumerable(Of IEnumerable(Of T))

         Dim result = From m In Enumerable.Range(0, 1 << items.Count)
                 Select
                    From i In Enumerable.Range(0, items.Count)
                    Where (m And (1 << i)) <> 0
                        Select items(i)
         Return result

End Function

I found another approach here (look there for C# code).

    Public Function GetPowerSet(Of T)(items As IEnumerable(Of T)) As IEnumerable(Of IEnumerable(Of T))

         Dim result = From m In Enumerable.Range(0, 1 << items.Count)
                 Select
                    From i In Enumerable.Range(0, items.Count)
                    Where (m And (1 << i)) <> 0
                        Select items(i)
         Return result

End Function
这个俗人 2024-11-13 14:28:04

一种简单的递归解决方案(大量列表创建开销):

    static List<IEnumerable<string>> GetChoiceSets(IEnumerable<string> choices)
    {
        if (choices == null || !choices.Any())
            return null;
        else
        {
            var first = choices.Take(1);
            var inner = GetChoiceSets(choices.Skip(1));

            if (inner == null)
                return new List<IEnumerable<string>> { first, new List<string> { } };
            else
                return inner.Select(lst => first.Union(lst)).Union(inner).ToList();
        }
    }

一种使用链接 SO 算法的稍微不那么简单的迭代解决方案:

    static List<List<string>> GetChoiceSets2(List<string> choices)
    {
        int capacity = (int)Math.Pow(2, choices.Count());
        int bit = 1;
        List<List<string>> choiceSets = new List<List<string>>(capacity);
        for (int i = 0; i < capacity; i++)
            choiceSets.Add(new List<String>());

        for (int i = 0; i < choices.Count(); i++)
        {
            for (int n = 0; n < capacity; n++)
            {
                if ((n & bit) == bit)
                    choiceSets[n].Add(choices[i]);
            }
            bit *= 2;
        }

        return choiceSets;
    }

这些可能都可以得到改进,但根据所使用的集合的大小,其中一个应该足够高效。

A naive recursive solution (lots of list creation overhead):

    static List<IEnumerable<string>> GetChoiceSets(IEnumerable<string> choices)
    {
        if (choices == null || !choices.Any())
            return null;
        else
        {
            var first = choices.Take(1);
            var inner = GetChoiceSets(choices.Skip(1));

            if (inner == null)
                return new List<IEnumerable<string>> { first, new List<string> { } };
            else
                return inner.Select(lst => first.Union(lst)).Union(inner).ToList();
        }
    }

A slightly less naive iterative solution using the linked SO algorithm:

    static List<List<string>> GetChoiceSets2(List<string> choices)
    {
        int capacity = (int)Math.Pow(2, choices.Count());
        int bit = 1;
        List<List<string>> choiceSets = new List<List<string>>(capacity);
        for (int i = 0; i < capacity; i++)
            choiceSets.Add(new List<String>());

        for (int i = 0; i < choices.Count(); i++)
        {
            for (int n = 0; n < capacity; n++)
            {
                if ((n & bit) == bit)
                    choiceSets[n].Add(choices[i]);
            }
            bit *= 2;
        }

        return choiceSets;
    }

These could probably both be improved, but depending on the size of the sets in use, one or the other should be efficient enough.

紫罗兰の梦幻 2024-11-13 14:28:04

我不是用VB.NET编程的,这只是输入的。所以可能存在严重的错误。但这种方法应该有效。

static List<List<string>> GetChoiceSets(List<string> choices)
{
    int capacity = (int) Math.Pow(2, choices.Count()) - 1;
    int bit = 1;
    List<List<string>> choiceSets = new List<List<string>>(capacity);
    for (int i = 0; i < capacity; i++)
        choiceSets.Add(new List<String>());

    n = 0;
    for (int size = 1; size <= choices.Count(); size++)
    {
        List<int> indexes = new List<int>(size);
        for (int i = 0; i < size; i++)
            indexes.Add(i);

        // We break out after exhausting all sets of this size.
        for (;;) {
            // Insert solution.
            for (int i = 0; i < size; i++)
                choiceSets[n].Add(choices[indexes[i]]);
            n++;

            // Figure out the first place we can advance indexes.
            int j = 1;
            for (; j <= size; j++) {
                if (indexes[size - j] < choices.Count() - j) {
                    break;
                }
            }
            threshold = choices.Count() - j
            // Did we finish?
            if (threshold < 0)
                break;

            // We will increment the index at threshold, and make following ones
            // increment from there.
            indexes[threshold]++;
            for (int i = 1; i + threshold < choices.Count(); i++)
                indexes[threshold + i] = indexes[threshold] + i;
        }
    }

    return choiceSets;
}

I don't program in VB.NET, and this is just typed in. So there may be serious bugs. But the approach should work.

static List<List<string>> GetChoiceSets(List<string> choices)
{
    int capacity = (int) Math.Pow(2, choices.Count()) - 1;
    int bit = 1;
    List<List<string>> choiceSets = new List<List<string>>(capacity);
    for (int i = 0; i < capacity; i++)
        choiceSets.Add(new List<String>());

    n = 0;
    for (int size = 1; size <= choices.Count(); size++)
    {
        List<int> indexes = new List<int>(size);
        for (int i = 0; i < size; i++)
            indexes.Add(i);

        // We break out after exhausting all sets of this size.
        for (;;) {
            // Insert solution.
            for (int i = 0; i < size; i++)
                choiceSets[n].Add(choices[indexes[i]]);
            n++;

            // Figure out the first place we can advance indexes.
            int j = 1;
            for (; j <= size; j++) {
                if (indexes[size - j] < choices.Count() - j) {
                    break;
                }
            }
            threshold = choices.Count() - j
            // Did we finish?
            if (threshold < 0)
                break;

            // We will increment the index at threshold, and make following ones
            // increment from there.
            indexes[threshold]++;
            for (int i = 1; i + threshold < choices.Count(); i++)
                indexes[threshold + i] = indexes[threshold] + i;
        }
    }

    return choiceSets;
}
情仇皆在手 2024-11-13 14:28:04
IEnumerable<IEnumerable<string>> seed = new[] { Enumerable.Empty<string>() };

choices.Aggregate(
    seed,
    (acc, item) =>
        acc.SelectMany(a => new[] { a, a.Concat(new[] {item}) }))

或者

choices.Aggregate(
    seed,
    (acc, item) =>
        from a in acc
        from c in new[] { Enumerable.Empty<string>(), new[] { item } }
        select a.Concat(c))
IEnumerable<IEnumerable<string>> seed = new[] { Enumerable.Empty<string>() };

choices.Aggregate(
    seed,
    (acc, item) =>
        acc.SelectMany(a => new[] { a, a.Concat(new[] {item}) }))

or

choices.Aggregate(
    seed,
    (acc, item) =>
        from a in acc
        from c in new[] { Enumerable.Empty<string>(), new[] { item } }
        select a.Concat(c))
~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文