生成一个字符串列表的所有组合

Question

我想生成一个由字符串列表（实际上是对象列表，但为简单起见，我们将使用字符串）的所有可能组合的列表。我需要这个列表以便在单元测试中测试每个可能的组合。

例如，如果我有以下列表：

  var allValues = new List<string>() { "A1", "A2", "A3", "B1", "B2", "C1" }

我需要一个 List<List<string>>，其中包含所有组合，如：

  A1
  A2
  A3
  B1
  B2
  C1
  A1 A2
  A1 A2 A3
  A1 A2 A3 B1
  A1 A2 A3 B1 B2
  A1 A2 A3 B1 B2 C1
  A1 A3
  A1 A3 B1
  etc...

使用递归函数可能是获取所有组合的方法，但它似乎比我想象的要困难。

有什么提示吗？

谢谢。

编辑：两种解决方案，使用或不使用递归：

public class CombinationGenerator<T>
{
    public IEnumerable<List<T>> ProduceWithRecursion(List<T> allValues) 
    {
        for (var i = 0; i < (1 << allValues.Count); i++)
        {
            yield return ConstructSetFromBits(i).Select(n => allValues[n]).ToList();
        }
    }

    private IEnumerable<int> ConstructSetFromBits(int i)
    {
        var n = 0;
        for (; i != 0; i /= 2)
        {
            if ((i & 1) != 0) yield return n;
            n++;
        }
    }

    public List<List<T>> ProduceWithoutRecursion(List<T> allValues)
    {
        var collection = new List<List<T>>();
        for (int counter = 0; counter < (1 << allValues.Count); ++counter)
        {
            List<T> combination = new List<T>();
            for (int i = 0; i < allValues.Count; ++i)
            {
                if ((counter & (1 << i)) == 0)
                    combination.Add(allValues[i]);
            }

            // do something with combination
            collection.Add(combination);
        }
        return collection;
    }
}

- L-Four

---

我知道这不完全是你想要的，但微软有一个测试版系统，可以自动生成输入组合。它叫做Pex：http://research.microsoft.com/en-us/projects/pex/ - Christopher Rathermel

想象一个二进制计数器。这应该可以让你开始了。 - SimpleVar

你不需要递归：http://stackoverflow.com/questions/10331229/the-different-combinations-of-a-vectors-values/10331312#10331312 - Henrik

确实，甚至不需要递归，太棒了！ - L-Four

你正在寻找一个集合的所有子集，而不是集合的所有组合或排列。 - stuckintheshuck

Answer 1

你可以手动制作，利用n位二进制数自然对应于n元集合的子集这一事实。

private IEnumerable<int> constructSetFromBits(int i)
{
    for (int n = 0; i != 0; i /= 2, n++)
    {
        if ((i & 1) != 0)
            yield return n;
    }
}

List<string> allValues = new List<string>()
        { "A1", "A2", "A3", "B1", "B2", "C1" };

private IEnumerable<List<string>> produceEnumeration()
{
    for (int i = 0; i < (1 << allValues.Count); i++)
    {
        yield return
            constructSetFromBits(i).Select(n => allValues[n]).ToList();
    }
}

public List<List<string>> produceList()
{
    return produceEnumeration().ToList();
}

- Vlad

Answer 2

如果您想要所有的变体，请查看此项目以了解如何实现。

http://www.codeproject.com/Articles/26050/Permutations-Combinations-and-Variations-using-C-G

但是由于它是开源的，您可以使用它CPOL。

例如：

var allValues = new List<string>() { "A1", "A2", "A3", "B1", "B2", "C1" };
List<String> result = new List<String>();
var indices = Enumerable.Range(1, allValues.Count);
foreach (int lowerIndex in indices)
{
    var partVariations = new Facet.Combinatorics.Variations<String>(allValues, lowerIndex);
    result.AddRange(partVariations.Select(p => String.Join(" ", p)));
}

var length = result.Count;  // 1956

- Tim Schmelter

Answer 3

另一种递归解决方案。从下面代码中的AllCombinations，您将获得所有可能的组合。

1. 从一个元素开始。
2. 生成它的所有可能组合。
3. 移动到下一个元素并重新开始步骤2。

代码：

public class Combination<T>
{
    private IEnumerable<T> list { get; set; }
    private int length;
    private List<IEnumerable<T>> _allCombination;

    public Combination(IEnumerable<T> _list)
    {
        list = _list;
        length = _list.Count();

        _allCombination = new List<IEnumerable<T>>();
    }

    public IEnumerable<IEnumerable<T>> AllCombinations
    {
        get
        {
            GenerateCombination(default(int), Enumerable.Empty<T>());

            return _allCombination;
        }
    }

    private void GenerateCombination(int position, IEnumerable<T> previousCombination)
    {
        for (int i = position; i < length; i++)
        {
            var currentCombination = new List<T>();
            currentCombination.AddRange(previousCombination);
            currentCombination.Add(list.ElementAt(i));

            _allCombination.Add(currentCombination);

            GenerateCombination(i + 1, currentCombination);

        }
    }
}

- Nans

Answer 4

类似的任务在下面的帖子中已经实现：

列出字符串/整数的所有排列组合

希望这可以帮到你。

- Pratik

---

在 Stack Overflow 上，不鼓励仅提供链接的答案，因为链接可能会失效，它们所链接到的资源也可能会发生变化。请考虑在此处总结链接中相关的部分。 - user456814

另外，您链接的答案是用于生成排列，而排列与组合不是同一回事。 - user456814