值列表的所有可能组合

Question

我的C#程序中有一个整数列表.但是,我只在运行时知道列表中的项目数.

让我们说,为了简单起见,我的列表是{1,2,3}现在我需要生成所有可能的组合,如下所示.{1,2,3} {1,2} {1,3} {2,3} {1} {2} {3}

有人可以帮忙吗？

Answer 1

试试这个:

static void Main(string[] args)
{

    GetCombination(new List<int> { 1, 2, 3 });
}

static void GetCombination(List<int> list)
{
    double count = Math.Pow(2, list.Count);
    for (int i = 1; i <= count - 1; i++)
    {
        string str = Convert.ToString(i, 2).PadLeft(list.Count, '0');
        for (int j = 0; j < str.Length; j++)
        {
            if (str[j] == '1')
            {
                Console.Write(list[j]);
            }
        }
        Console.WriteLine();
    }
}

Answer 2

假设 initail 集合中的所有项都是distinct，我们可以尝试使用Linq进行查询；让我们概括一下解决方案：

代码：

public static IEnumerable<T[]> Combinations<T>(IEnumerable<T> source) {
  if (null == source)
    throw new ArgumentNullException(nameof(source));

  T[] data = source.ToArray();

  return Enumerable
    .Range(0, 1 << (data.Length))
    .Select(index => data
       .Where((v, i) => (index & (1 << i)) != 0)
       .ToArray());
}

演示：

  var data = new char[] { 'A', 'B', 'C' };

  var result = Combinations(data);

  foreach (var item in result)
    Console.WriteLine($"[{string.Join(", ", item)}]);

结果：

[]
[A]
[B]
[A, B]
[C]
[A, C]
[B, C]
[A, B, C]

如果你想排除初始空数组，把.Range(1, (1 << (data.Length)) - 1)而不是.Range(0, 1 << (data.Length))

Answer 3

以下是强类型列表的两个通用解决方案,它们将返回列表成员的所有唯一组合(如果您可以使用更简单的代码解决此问题,我向您致敬):

// Recursive
public static List<List<T>> GetAllCombos<T>(List<T> list)
{
  List<List<T>> result = new List<List<T>>();
  // head
  result.Add(new List<T>());
  result.Last().Add(list[0]);
  if (list.Count == 1)
    return result;
  // tail
  List<List<T>> tailCombos = GetAllCombos(list.Skip(1).ToList());
  tailCombos.ForEach(combo =>
  {
    result.Add(new List<T>(combo));
    combo.Add(list[0]);
    result.Add(new List<T>(combo));
  });
  return result;
}

// Iterative, using 'i' as bitmask to choose each combo members
public static List<List<T>> GetAllCombos<T>(List<T> list)
{
  int comboCount = (int) Math.Pow(2, list.Count) - 1;
  List<List<T>> result = new List<List<T>>();
  for (int i = 1; i < comboCount + 1; i++)
  {
    // make each combo here
    result.Add(new List<T>());
    for (int j = 0; j < list.Count; j++)
    {
      if ((i >> j) % 2 != 0)
        result.Last().Add(list[j]);
    }
  }
  return result;
}

// Example usage
List<List<int>> combos = GetAllCombos(new int[] { 1, 2, 3 }.ToList());

Answer 4

这是使用递归的通用解决方案

public static ICollection<ICollection<T>> Permutations<T>(ICollection<T> list) {
    var result = new List<ICollection<T>>();
    if (list.Count == 1) { // If only one possible permutation
        result.Add(list); // Add it and return it
        return result;
    }
    foreach (var element in list) { // For each element in that list
        var remainingList = new List<T>(list);
        remainingList.Remove(element); // Get a list containing everything except of chosen element
        foreach (var permutation in Permutations<T>(remainingList)) { // Get all possible sub-permutations
            permutation.Add(element); // Add that element
            result.Add(permutation);
        }
    }
    return result;
}

我知道这是一篇旧帖子,但有人可能会觉得这很有帮助.

Answer 5

这个答案使用与ojlovecd相同的算法和(对于他的迭代解决方案)jaolho.我要添加的唯一选项是过滤组合中最少数量项目的结果.例如,如果您只对包含至少两个项目的组合感兴趣,这可能很有用.

编辑:根据@ user3610374的要求,添加了最大项目数的过滤器.

编辑2:正如@stannius所建议的那样,算法已被更改,以使其在不需要所有组合的情况下更有效.

  /// <summary>
  /// Method to create lists containing possible combinations of an input list of items. This is 
  /// basically copied from code by user "jaolho" on this thread:
  /// http://stackoverflow.com/questions/7802822/all-possible-combinations-of-a-list-of-values
  /// </summary>
  /// <typeparam name="T">type of the items on the input list</typeparam>
  /// <param name="inputList">list of items</param>
  /// <param name="minimumItems">minimum number of items wanted in the generated combinations, 
  ///                            if zero the empty combination is included,
  ///                            default is one</param>
  /// <param name="maximumItems">maximum number of items wanted in the generated combinations,
  ///                            default is no maximum limit</param>
  /// <returns>list of lists for possible combinations of the input items</returns>
  public static List<List<T>> ItemCombinations<T>(List<T> inputList, int minimumItems = 1, 
                                                  int maximumItems = int.MaxValue)
  {
     int nonEmptyCombinations = (int)Math.Pow(2, inputList.Count) - 1;
     List<List<T>> listOfLists = new List<List<T>>(nonEmptyCombinations + 1);

     // Optimize generation of empty combination, if empty combination is wanted
     if (minimumItems == 0)
        listOfLists.Add(new List<T>());

     if (minimumItems <= 1 && maximumItems >= inputList.Count)
     {
        // Simple case, generate all possible non-empty combinations
        for (int bitPattern = 1; bitPattern <= nonEmptyCombinations; bitPattern++)
           listOfLists.Add(GenerateCombination(inputList, bitPattern));
     }
     else
     {
        // Not-so-simple case, avoid generating the unwanted combinations
        for (int bitPattern = 1; bitPattern <= nonEmptyCombinations; bitPattern++)
        {
           int bitCount = CountBits(bitPattern);
           if (bitCount >= minimumItems && bitCount <= maximumItems)
              listOfLists.Add(GenerateCombination(inputList, bitPattern));
        }
     }

     return listOfLists;
  }

  /// <summary>
  /// Sub-method of ItemCombinations() method to generate a combination based on a bit pattern.
  /// </summary>
  private static List<T> GenerateCombination<T>(List<T> inputList, int bitPattern)
  {
     List<T> thisCombination = new List<T>(inputList.Count);
     for (int j = 0; j < inputList.Count; j++)
     {
        if ((bitPattern >> j & 1) == 1)
           thisCombination.Add(inputList[j]);
     }
     return thisCombination;
  }

  /// <summary>
  /// Sub-method of ItemCombinations() method to count the bits in a bit pattern. Based on this:
  /// https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan
  /// </summary>
  private static int CountBits(int bitPattern)
  {
     int numberBits = 0;
     while (bitPattern != 0)
     {
        numberBits++;
        bitPattern &= bitPattern - 1;
     }
     return numberBits;
  }

Answer 6

另一个使用 Linq 和递归的解决方案......

static void Main(string[] args)
    {
        List<List<long>> result = new List<List<long>>();

        List<long> set = new List<long>() { 1, 2, 3, 4 };

        GetCombination<long>(set, result);

        result.Add(set);

        IOrderedEnumerable<List<long>> sorted = result.OrderByDescending(s => s.Count);

        sorted.ToList().ForEach(l => { l.ForEach(l1 => Console.Write(l1 + " ")); Console.WriteLine(); });
    }

    private static void GetCombination<T>(List<T> set, List<List<T>> result)
    {
        for (int i = 0; i < set.Count; i++)
        {
            List<T> temp = new List<T>(set.Where((s, index) => index != i));

            if (temp.Count > 0 && !result.Where(l => l.Count == temp.Count).Any(l => l.SequenceEqual(temp)))
            {
                result.Add(temp);

                GetCombination<T>(temp, result);
            }
        }
    }