C#List <string>的所有唯一组合

Question

这个问题已被多次询问过,但我见过的每个SO帖子都想要一个特定的长度值,而我只是想知道每个独特的组合,无论长度如何.

下面的代码仅提供了一个列表,其中恰好有3个组合条目(并且它们不是唯一的).

List<string> list = new List<string> { "003_PS", "003_DH", "003_HEAT" };
var perms = list.GetPermutations();

public static class Extensions 
{
    public static IEnumerable<IEnumerable<T>> GetPermutations<T>(this IEnumerable<T> items)
    {
        foreach (var item in items)
        {
            var itemAsEnumerable = Enumerable.Repeat(item, 1);
            var subSet = items.Except(itemAsEnumerable);
            if (!subSet.Any())
            {
                yield return itemAsEnumerable;
            }
            else
            {
                foreach (var sub in items.Except(itemAsEnumerable).GetPermutations())
                {
                    yield return itemAsEnumerable.Union(sub);
                }
            }
        }
    }
}

/*
  OUTPUT:
      003_PS,   003_DH,   003_HEAT
      003_PS,   003_HEAT, 003_DH
      003_DH,   003_PS,   003_HEAT
      003_DH,   003_HEAT, 003_PS
      003_HEAT, 003_PS,   003_DH
      003_HEAT, 003_DH,   003_PS
*/

我正在寻找的是:

/*
OUTPUT:
    003_PS, 003_DH, 003_HEAT
    003_PS, 003_DH
    003_PS, 003_HEAT
    003_PS

    003_DH, 003_HEAT
    003_DH

    003_HEAT
 */

大小不限于3个项目,每个条目都是唯一的.

我需要在此功能中更改什么？我对LINQ解决方案持开放态度

任何帮助表示赞赏.谢谢!

编辑:上面的列表输出不准确

**编辑#2:这是我正在寻找的Javascript版本.但我不知道C#等效语法是什么:

function getUniqueList(arr){
    if (arr.length === 1) return [arr];
    else {
        subarr = getUniqueList(arr.slice(1));
        return subarr.concat(subarr.map(e => e.concat(arr[0])), [[arr[0]]]);
    }
}

.

Answer 1

好的,你有n个项目,你想要这些项目的2 ^n个组合.

仅供参考,当你在套装上这样做时,这被称为"动力装置"; 因为序列可包含重复和集不能,你想要的是不准确的发电机组,但它是足够接近.如果你的序列包含重复项,那么我提出的代码在某种意义上是错误的,因为我们会说结果{10, 10}将会是,{}, {10}, {10}, {10, 10}但是如果你不喜欢它,那么,在开始之前删除重复项,然后你将会计算功率集.

计算所有组合的顺序很简单.我们的理由如下:

• 如果零项目则只有一个组合:零项目的组合.
• 如果有n> 0个项目,则组合是与第一个元素的所有组合,以及没有第一个元素的所有组合.

我们来写代码:

using System;
using System.Collections.Generic;
using System.Linq;

static class Extensions
{
    public static IEnumerable<T> Prepend<T>(
        this IEnumerable<T> items,
        T first)
    {
        yield return first;
        foreach(T item in items)
            yield return item;
    }
    public static IEnumerable<IEnumerable<T>> Combinations<T>(
        this IEnumerable<T> items)
    {
        if (!items.Any())
            yield return items;
        else
        {
          var head = items.First();
          var tail = items.Skip(1);
          foreach(var sequence in tail.Combinations()) 
          {
            yield return sequence; // Without first
            yield return sequence.Prepend(head);
          }
       }
    }
}

public class Program
{
    public static void Main()
    {
        var items = new [] { 10, 20, 30 };
        foreach(var sequence in items.Combinations())
            Console.WriteLine($"({string.Join(",", sequence)})");
    }
}

我们得到了输出

()
(10)
(20)
(10,20)
(30)
(10,30)
(20,30)
(10,20,30)

请注意,如果原始序列很长,则此代码效率不高.

练习1:你明白为什么吗？

练习2:对于长序列,你能在时间和空间上使这段代码有效吗？(提示:如果你能够做到head,tail并且prepend操作更节省内存,那将会有很长的路要走.)

练习3:你在JavaScript中提供相同的算法; 你可以在JS算法的每个部分和C#版本之间进行类比吗？

当然,我们假设原始序列中的项目数量很短.如果它甚至是一百,你将等待很长时间来枚举所有那些数万亿的组合.

如果您想获得具有特定数量元素的所有组合,请参阅我的系列文章:https : //ericlippert.com/2014/10/13/producing-combinations-part-one/