1

我已经查看了有关组合和排列的所有 StackOverflow 帖子，但找不到我正在寻找的确切细致入微的答案，我也无法思考如何正确实现这一点。理想情况下，我正在寻找一种不使用递归的解决方案，这样我就可以避免大列表上的堆栈溢出。如何获得具有以下要求的字符串列表的所有组合？

  • 每个结果列表中至少有 2 个元素
  • 秩序对于平等并不重要。换句话说，("a", "b") == ("b", "a")

例子：

var input = new List<string> { "a", "b", "c", "d" };

// TODO


// Note: the final order of lists in expectedResult doesn't matter
var expectedResult = new List<List<string>>{
    new List<string> { "a", "b", "c", "d" },
    new List<string> { "a", "b", "c" },
    new List<string> { "a", "b", "d" },
    new List<string> { "a", "c", "d" },
    new List<string> { "b", "c", "d" },
    new List<string> { "a", "b" },
    new List<string> { "a", "c", },
    new List<string> { "a", "d" },
    new List<string> { "b", "c" },
    new List<string> { "b", "d" },
    new List<string> { "c", "d" }
};

Assert.IsTrue(expectedResult.Count == 11);
Assert.IsTrue(expectedResult.All(list => list.Count >= 2));
4

2 回答 2

2

您可以使用数字掩码很容易地做到这一点，以跟踪您访问过的内容和一些位移。

给定

public static IEnumerable<T[]> GetCombinations<T>(List<T> source)
{
   for (var i = 0; i < (1 << source.Count); i++)
      yield return source
         .Where((t, j) => (i & (1 << j)) != 0)
         .ToArray();
}

或者如果你有for 循环强迫症和类似的扩展方法

public static IEnumerable<T[]> GetCombinations<T>(this List<T> source)
   => Enumerable
      .Range(0, 1 << source.Count)
      .Select(i => source
         .Where((t, j) => (i & (1 << j)) != 0)
         .ToArray());

用法

var input = new List<string> {"a", "b", "c", "d"};

var results = GetCombinations(input)
      .Where(x => x.Length >= 2);

foreach (var items in results)
   Console.WriteLine(string.Join(",",items));

输出

a,b
a,c
b,c
a,b,c
a,d
b,d
a,b,d
c,d
a,c,d
b,c,d
a,b,c,d

加入胡椒盐，按个人口味排序

前提是，

  1. 对要返回的组合使用位掩码。每个位代表一个true或false，并且与集合中的一个元素相关联。即掩码1100将意味着返回组合C,D等。

  2. 对给定的集合使用具有一定范围（甚至更好，如Enigmativity建议的那样更好）最大组合的循环来增加掩码..Math.Pow(2, source.Count)1 << source.Count

  3. 然后把它全部放在一个迭代器方法中以获得一桶笑声......所有组合都会给出。

唯一的限制是数组的最大大小限制为可以位移的数字类型的最大位（在当前实现中），即 32/64 个元素，具体取决于or ，这将分别产生/组合。intlong2^322^64

更新

Enigmativity的进一步评论（以及我不知道的事情）

您可以使用BigInteger来绕过最大位数限制

BigInteger one = 1; 

for (BigInteger i = 0; i < one << source.Count; i++) 
   yield return source.Where((_, j) => (i & one << j) != 0).ToArray();
于 2020-11-25T05:40:47.920 回答
0

这是该问题的一个hacky解决方案：

static IEnumerable<IEnumerable<string>> GetPermutations(IList<string> input)
{
    List<List<string>> output = new List<List<string>>();

    for (int count = input.Count; count >= 2; count--)
    {
        var indexes = new int[count];

        // Set initial index values to be default (i.e. 0,1,2,3)
        for (int index = 0; index < count; index++)
        {
            indexes[index] = index;
        }

        // Start at the last index (i.e. D) and build output
        for (int arrayIndex = indexes.Length - 1; arrayIndex >= 0; arrayIndex--)
        {
            bool indexCanBeIncremented = true;
            while (indexCanBeIncremented)
            {
                List<string> currentList = new List<string>();

                foreach (var index in indexes)
                {
                    currentList.Add(input[index]);
                }

                if (IsUnique(output, currentList))
                {
                    output.Add(currentList);
                }                       

                if (arrayIndex == indexes.Length - 1 && indexes[arrayIndex] < input.Count - 1 || 
                    arrayIndex < indexes.Length - 1 && indexes[arrayIndex] + 1 != indexes[arrayIndex + 1])
                {
                    indexes[arrayIndex] += 1;
                }
                else
                {
                    indexCanBeIncremented = false;
                }
            }
        }
    }

    return output;
}

public static bool IsUnique(List<List<string>> collection, List<string> input)
{
    foreach (var list in collection)
    {
        if (input.SequenceEqual(list))
        {
            return false;
        }
    }

    return true;
}

该代码本质上跟踪输入的所有索引，并将根据排列构建输出。

输出

a b c d
a b c
a b d
a c d
b c d
a b
a c
a d
b d
c d
于 2020-11-25T05:44:04.157 回答