当前位置：文江博客话题详情

C# algorithm math combinations

值列表的所有可能组合

发布于 2024-12-10 11:43:03 字数 238 浏览 0 评论 0 原文

我的 C# 程序中有一个整数列表 List。但是，我仅在运行时知道列表中的项目数量。

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

{1, 2, 3}
{1, 2}
{1, 3}
{2, 3}
{1}
{2}
{3}

有人可以帮忙解决这个问题吗？

原文

I have a list of integers List<int> in my C# program. However, I know the number of items I have in my list only at runtime.

Let us say, for the sake of simplicity, my list is {1, 2, 3}
Now I need to generate all possible combinations as follows.

{1, 2, 3}
{1, 2}
{1, 3}
{2, 3}
{1}
{2}
{3}

Can somebody please help with this?

分享到QQ

分享到微博

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

发布评论

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

鯉魚旗 2024-12-17 11:43:04

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

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;
}

我知道这是一篇旧文章，但有人可能会发现这很有帮助。

Here's a generic solution using recursion

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;
}

I know this is an old post, but someone might find this helpful.

回复收藏 0 原文

花开雨落又逢春i 2024-12-17 11:43:04

另一个使用 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);
            }
        }
    }

Another solution using Linq and recursion...

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);
            }
        }
    }

回复收藏 0 原文

°如果伤别离去 2024-12-17 11:43:04

这是对 @ojlovecd 答案的改进，无需使用字符串。

    static void Main(string[] args)
    {
        GetCombination(new List<int> { 1, 2, 3 });
    }


    private static void GetCombination(List<int> list)
    {
        double count = Math.Pow(2, list.Count);
        for (int i = 1; i <= count - 1; i++)
        {
            for (int j = 0; j < list.Count; j++)
            {
                int b = i & (1 << j);
                if (b > 0)
                {
                    Console.Write(list[j]);
                }
            }
            Console.WriteLine();
        }
    }

This is an improvement of @ojlovecd answer without using strings.

    static void Main(string[] args)
    {
        GetCombination(new List<int> { 1, 2, 3 });
    }


    private static void GetCombination(List<int> list)
    {
        double count = Math.Pow(2, list.Count);
        for (int i = 1; i <= count - 1; i++)
        {
            for (int j = 0; j < list.Count; j++)
            {
                int b = i & (1 << j);
                if (b > 0)
                {
                    Console.Write(list[j]);
                }
            }
            Console.WriteLine();
        }
    }

回复收藏 0 原文

生生漫 2024-12-17 11:43:04

首先，给定一组 n 个元素，计算其中 k 个元素的所有组合 (nCk)。您必须将 k 的值从 1 更改为 n 以满足您的要求。

请参阅此 codeproject 文章，了解用于生成组合的 C# 代码。

如果您有兴趣自己开发组合算法，请检查此 SO问题，其中有很多相关材料的链接。

回复收藏 0 原文

娇俏 2024-12-17 11:43:04

protected List<List<T>> AllCombos<T>(Func<List<T>, List<T>, bool> comparer, params T[] items)
    {
        List<List<T>> results = new List<List<T>>();
        List<T> workingWith = items.ToList();
        results.Add(workingWith);
        items.ToList().ForEach((x) =>
        {
            results.Add(new List<T>() { x });
        });
        for (int i = 0; i < workingWith.Count(); i++)
        {
            T removed = workingWith[i];
            workingWith.RemoveAt(i);
            List<List<T>> nextResults = AllCombos2(comparer, workingWith.ToArray());
            results.AddRange(nextResults);
            workingWith.Insert(i, removed);
        }
        results = results.Where(x => x.Count > 0).ToList();
        for (int i = 0; i < results.Count; i++)
        {
            List<T> list = results[i];
            if (results.Where(x => comparer(x, list)).Count() > 1)
            {
                results.RemoveAt(i);
            }
        }

        return results;
    }

    protected List<List<T>> AllCombos2<T>(Func<List<T>, List<T>, bool> comparer, params T[] items)
    {
        List<List<T>> results = new List<List<T>>();
        List<T> workingWith = items.ToList();
        if (workingWith.Count > 1)
        {
            results.Add(workingWith);
        }
        for (int i = 0; i < workingWith.Count(); i++)
        {
            T removed = workingWith[i];
            workingWith.RemoveAt(i);
            List<List<T>> nextResults = AllCombos2(comparer, workingWith.ToArray());
            results.AddRange(nextResults);
            workingWith.Insert(i, removed);
        }
        results = results.Where(x => x.Count > 0).ToList();
        for (int i = 0; i < results.Count; i++)
        {
            List<T> list = results[i];
            if (results.Where(x => comparer(x, list)).Count() > 1)
            {
                results.RemoveAt(i);
            }
        }

        return results;
    }

这对我有用，它稍微复杂一些，实际上需要一个比较器回调函数，它实际上是 2 个函数，区别在于 AllCombos 显式添加单个项目列表。它非常原始，绝对可以修剪，但它可以完成工作。欢迎任何重构建议。谢谢，

protected List<List<T>> AllCombos<T>(Func<List<T>, List<T>, bool> comparer, params T[] items)
    {
        List<List<T>> results = new List<List<T>>();
        List<T> workingWith = items.ToList();
        results.Add(workingWith);
        items.ToList().ForEach((x) =>
        {
            results.Add(new List<T>() { x });
        });
        for (int i = 0; i < workingWith.Count(); i++)
        {
            T removed = workingWith[i];
            workingWith.RemoveAt(i);
            List<List<T>> nextResults = AllCombos2(comparer, workingWith.ToArray());
            results.AddRange(nextResults);
            workingWith.Insert(i, removed);
        }
        results = results.Where(x => x.Count > 0).ToList();
        for (int i = 0; i < results.Count; i++)
        {
            List<T> list = results[i];
            if (results.Where(x => comparer(x, list)).Count() > 1)
            {
                results.RemoveAt(i);
            }
        }

        return results;
    }

    protected List<List<T>> AllCombos2<T>(Func<List<T>, List<T>, bool> comparer, params T[] items)
    {
        List<List<T>> results = new List<List<T>>();
        List<T> workingWith = items.ToList();
        if (workingWith.Count > 1)
        {
            results.Add(workingWith);
        }
        for (int i = 0; i < workingWith.Count(); i++)
        {
            T removed = workingWith[i];
            workingWith.RemoveAt(i);
            List<List<T>> nextResults = AllCombos2(comparer, workingWith.ToArray());
            results.AddRange(nextResults);
            workingWith.Insert(i, removed);
        }
        results = results.Where(x => x.Count > 0).ToList();
        for (int i = 0; i < results.Count; i++)
        {
            List<T> list = results[i];
            if (results.Where(x => comparer(x, list)).Count() > 1)
            {
                results.RemoveAt(i);
            }
        }

        return results;
    }

This worked for me, it's slightly more complex and actually takes a comparer callback function, and it's actually 2 functions, the difference being that the AllCombos adds the single item lists explicitly. It is very raw and can definitely be trimmed down but it gets the job done. Any refactoring suggestions are welcome. Thanks,

回复收藏 0 原文

握住你手 2024-12-17 11:43:04

public class CombinationGenerator{
    private readonly Dictionary<int, int> currentIndexesWithLevels = new Dictionary<int, int>();
    private readonly LinkedList<List<int>> _combinationsList = new LinkedList<List<int>>();
    private readonly int _combinationLength;

    public CombinationGenerator(int combinationLength)
    {
        _combinationLength = combinationLength;
    }

    private void InitializeLevelIndexes(List<int> list)
    {
        for (int i = 0; i < _combinationLength; i++)
        {
            currentIndexesWithLevels.Add(i+1, i);
        }
    }

    private void UpdateCurrentIndexesForLevels(int level)
    {
        int index;
        if (level == 1)
        {
            index = currentIndexesWithLevels[level];
            for (int i = level; i < _combinationLength + 1; i++)
            {
                index = index + 1;
                currentIndexesWithLevels[i] = index;
            }
        }
        else
        {
            int previousLevelIndex;
            for (int i = level; i < _combinationLength + 1; i++)
            {
                if (i > level)
                {
                    previousLevelIndex = currentIndexesWithLevels[i - 1];
                    currentIndexesWithLevels[i] = previousLevelIndex + 1;
                }
                else
                {
                    index = currentIndexesWithLevels[level];
                    currentIndexesWithLevels[i] = index + 1;
                }
            }
        }
    }

    public void FindCombinations(List<int> list, int level, Stack<int> stack)
    {
        int currentIndex;
        InitializeLevelIndexes(list);
        while (true)
        {
            currentIndex = currentIndexesWithLevels[level];
            bool levelUp = false;          
            for (int i = currentIndex; i < list.Count; i++)
            {
                if (level < _combinationLength)
                {
                    currentIndex = currentIndexesWithLevels[level];
                    MoveToUpperLevel(ref level, stack, list, currentIndex);
                    levelUp = true;
                    break;
                }
                levelUp = false;
                stack.Push(list[i]);
                if (stack.Count == _combinationLength)
                {
                    AddCombination(stack);
                    stack.Pop();
                }                                                                                 
            }

            if (!levelUp)
            {
                MoveToLowerLevel(ref level, stack, list, ref currentIndex);
                while (currentIndex >= list.Count - 1)
                {
                    if (level == 1)
                    {
                        AdjustStackCountToCurrentLevel(stack, level);
                        currentIndex = currentIndexesWithLevels[level];
                        if (currentIndex >= list.Count - 1)
                        {
                            return;
                        }
                        UpdateCurrentIndexesForLevels(level);
                    }
                    else
                    {
                        MoveToLowerLevel(ref level, stack, list, ref currentIndex);
                    }
              }
          }                               
       }
    }

    private void AddCombination(Stack<int> stack)
    {
        List<int> listNew = new List<int>();
        listNew.AddRange(stack);
        _combinationsList.AddLast(listNew);
    }

    private void MoveToUpperLevel(ref int level, Stack<int> stack, List<int> list, int index)
    {
        stack.Push(list[index]);
        level++;
    }

    private void MoveToLowerLevel(ref int level, Stack<int> stack, List<int> list, ref int currentIndex)
    {
        if (level != 1)
        {
            level--;
        }
        AdjustStackCountToCurrentLevel(stack, level);
        UpdateCurrentIndexesForLevels(level);
        currentIndex = currentIndexesWithLevels[level];
    }

    private void AdjustStackCountToCurrentLevel(Stack<int> stack, int currentLevel)
    {
        while (stack.Count >= currentLevel)
        {
            if (stack.Count != 0)
                stack.Pop();
        }
    }

    public void PrintPermutations()
    {
        int count = _combinationsList.Where(perm => perm.Count() == _combinationLength).Count();
        Console.WriteLine("The number of combinations is " + count);
    }

}

public class CombinationGenerator{
    private readonly Dictionary<int, int> currentIndexesWithLevels = new Dictionary<int, int>();
    private readonly LinkedList<List<int>> _combinationsList = new LinkedList<List<int>>();
    private readonly int _combinationLength;

    public CombinationGenerator(int combinationLength)
    {
        _combinationLength = combinationLength;
    }

    private void InitializeLevelIndexes(List<int> list)
    {
        for (int i = 0; i < _combinationLength; i++)
        {
            currentIndexesWithLevels.Add(i+1, i);
        }
    }

    private void UpdateCurrentIndexesForLevels(int level)
    {
        int index;
        if (level == 1)
        {
            index = currentIndexesWithLevels[level];
            for (int i = level; i < _combinationLength + 1; i++)
            {
                index = index + 1;
                currentIndexesWithLevels[i] = index;
            }
        }
        else
        {
            int previousLevelIndex;
            for (int i = level; i < _combinationLength + 1; i++)
            {
                if (i > level)
                {
                    previousLevelIndex = currentIndexesWithLevels[i - 1];
                    currentIndexesWithLevels[i] = previousLevelIndex + 1;
                }
                else
                {
                    index = currentIndexesWithLevels[level];
                    currentIndexesWithLevels[i] = index + 1;
                }
            }
        }
    }

    public void FindCombinations(List<int> list, int level, Stack<int> stack)
    {
        int currentIndex;
        InitializeLevelIndexes(list);
        while (true)
        {
            currentIndex = currentIndexesWithLevels[level];
            bool levelUp = false;          
            for (int i = currentIndex; i < list.Count; i++)
            {
                if (level < _combinationLength)
                {
                    currentIndex = currentIndexesWithLevels[level];
                    MoveToUpperLevel(ref level, stack, list, currentIndex);
                    levelUp = true;
                    break;
                }
                levelUp = false;
                stack.Push(list[i]);
                if (stack.Count == _combinationLength)
                {
                    AddCombination(stack);
                    stack.Pop();
                }                                                                                 
            }

            if (!levelUp)
            {
                MoveToLowerLevel(ref level, stack, list, ref currentIndex);
                while (currentIndex >= list.Count - 1)
                {
                    if (level == 1)
                    {
                        AdjustStackCountToCurrentLevel(stack, level);
                        currentIndex = currentIndexesWithLevels[level];
                        if (currentIndex >= list.Count - 1)
                        {
                            return;
                        }
                        UpdateCurrentIndexesForLevels(level);
                    }
                    else
                    {
                        MoveToLowerLevel(ref level, stack, list, ref currentIndex);
                    }
              }
          }                               
       }
    }

    private void AddCombination(Stack<int> stack)
    {
        List<int> listNew = new List<int>();
        listNew.AddRange(stack);
        _combinationsList.AddLast(listNew);
    }

    private void MoveToUpperLevel(ref int level, Stack<int> stack, List<int> list, int index)
    {
        stack.Push(list[index]);
        level++;
    }

    private void MoveToLowerLevel(ref int level, Stack<int> stack, List<int> list, ref int currentIndex)
    {
        if (level != 1)
        {
            level--;
        }
        AdjustStackCountToCurrentLevel(stack, level);
        UpdateCurrentIndexesForLevels(level);
        currentIndex = currentIndexesWithLevels[level];
    }

    private void AdjustStackCountToCurrentLevel(Stack<int> stack, int currentLevel)
    {
        while (stack.Count >= currentLevel)
        {
            if (stack.Count != 0)
                stack.Pop();
        }
    }

    public void PrintPermutations()
    {
        int count = _combinationsList.Where(perm => perm.Count() == _combinationLength).Count();
        Console.WriteLine("The number of combinations is " + count);
    }

}

回复收藏 0 原文

蓝礼 2024-12-17 11:43:04

我们可以使用递归来解决涉及字符串或整数的组合/排列问题。

public static void Main(string[] args)
{
    IntegerList = new List<int> { 1, 2, 3, 4 };

    PrintAllCombination(default(int), default(int));
}

public static List<int> IntegerList { get; set; }

public static int Length { get { return IntegerList.Count; } }

public static void PrintAllCombination(int position, int prefix)
{
    for (int i = position; i < Length; i++)
    {
        Console.WriteLine(prefix * 10 + IntegerList[i]);
        PrintAllCombination(i + 1, prefix * 10 + IntegerList[i]);
    }

}

We can use recursion for combination/permutation problems involving string or integers.

public static void Main(string[] args)
{
    IntegerList = new List<int> { 1, 2, 3, 4 };

    PrintAllCombination(default(int), default(int));
}

public static List<int> IntegerList { get; set; }

public static int Length { get { return IntegerList.Count; } }

public static void PrintAllCombination(int position, int prefix)
{
    for (int i = position; i < Length; i++)
    {
        Console.WriteLine(prefix * 10 + IntegerList[i]);
        PrintAllCombination(i + 1, prefix * 10 + IntegerList[i]);
    }

}

回复收藏 0 原文

俯瞰星空 2024-12-17 11:43:04

怎么样

static void Main(string[] args)
{
     Combos(new [] { 1, 2, 3 });
}

static void Combos(int[] arr)
{
    for (var i = 0; i <= Math.Pow(2, arr.Length); i++)
    {
        Console.WriteLine();
        var j = i;
        var idx = 0;
        do 
        {
            if ((j & 1) == 1) Console.Write($"{arr[idx]} ");
        } while ((j >>= 1) > 0 && ++idx < arr.Length);
    }
}

What about

static void Main(string[] args)
{
     Combos(new [] { 1, 2, 3 });
}

static void Combos(int[] arr)
{
    for (var i = 0; i <= Math.Pow(2, arr.Length); i++)
    {
        Console.WriteLine();
        var j = i;
        var idx = 0;
        do 
        {
            if ((j & 1) == 1) Console.Write($"{arr[idx]} ");
        } while ((j >>= 1) > 0 && ++idx < arr.Length);
    }
}

回复收藏 0 原文

怂人 2024-12-17 11:43:04

使用 C# 7 的 Linq 的稍微更通用的版本。这里按具有两个元素的项目进行过滤。

static void Main(string[] args)
{
    foreach (var vals in Combos(new[] { "0", "1", "2", "3" }).Where(v => v.Skip(1).Any() && !v.Skip(2).Any()))
        Console.WriteLine(string.Join(", ", vals));
}

static IEnumerable<IEnumerable<T>> Combos<T>(T[] arr)
{
    IEnumerable<T> DoQuery(long j, long idx)
    {
        do
        {
            if ((j & 1) == 1) yield return arr[idx];
        } while ((j >>= 1) > 0 && ++idx < arr.Length);
    }
    for (var i = 0; i < Math.Pow(2, arr.Length); i++)
        yield return DoQuery(i, 0);
}

A slightly more generalised version for Linq using C# 7. Here filtering by items that have two elements.

static void Main(string[] args)
{
    foreach (var vals in Combos(new[] { "0", "1", "2", "3" }).Where(v => v.Skip(1).Any() && !v.Skip(2).Any()))
        Console.WriteLine(string.Join(", ", vals));
}

static IEnumerable<IEnumerable<T>> Combos<T>(T[] arr)
{
    IEnumerable<T> DoQuery(long j, long idx)
    {
        do
        {
            if ((j & 1) == 1) yield return arr[idx];
        } while ((j >>= 1) > 0 && ++idx < arr.Length);
    }
    for (var i = 0; i < Math.Pow(2, arr.Length); i++)
        yield return DoQuery(i, 0);
}

回复收藏 0 原文

剪不断理还乱 2024-12-17 11:43:04

我是这样做的。

public static List<List<int>> GetCombination(List<int> lst, int index, int count)
{
    List<List<int>> combinations = new List<List<int>>();
    List<int> comb;
    if (count == 0 || index == lst.Count)
    {
        return null;
    }
    for (int i = index; i < lst.Count; i++)
    {
        comb = new List<int>();
        comb.Add(lst.ElementAt(i));
        combinations.Add(comb);
        var rest = GetCombination(lst,i + 1, count - 1);
        if (rest != null)
        {
            foreach (var item in rest)
            {
                combinations.Add(comb.Union(item).ToList());
            }
        }
    }
    return combinations;
}

您将其称为：

List<int> lst= new List<int>(new int[]{ 1, 2, 3, 4 });
var combinations = GetCombination(lst, 0, lst.Length)

Here is how I did it.

public static List<List<int>> GetCombination(List<int> lst, int index, int count)
{
    List<List<int>> combinations = new List<List<int>>();
    List<int> comb;
    if (count == 0 || index == lst.Count)
    {
        return null;
    }
    for (int i = index; i < lst.Count; i++)
    {
        comb = new List<int>();
        comb.Add(lst.ElementAt(i));
        combinations.Add(comb);
        var rest = GetCombination(lst,i + 1, count - 1);
        if (rest != null)
        {
            foreach (var item in rest)
            {
                combinations.Add(comb.Union(item).ToList());
            }
        }
    }
    return combinations;
}

You call it as :

List<int> lst= new List<int>(new int[]{ 1, 2, 3, 4 });
var combinations = GetCombination(lst, 0, lst.Length)

回复收藏 0 原文

柒夜笙歌凉 2024-12-17 11:43:04

我刚刚遇到一种情况，我需要这样做，这就是我想到的：

private static List<string> GetCombinations(List<string> elements)
{
    List<string> combinations = new List<string>();
    combinations.AddRange(elements);
    for (int i = 0; i < elements.Count - 1; i++)
    {
        combinations = (from combination in combinations
                        join element in elements on 1 equals 1
                        let value = string.Join(string.Empty, $"{combination}{element}".OrderBy(c => c).Distinct())
                        select value).Distinct().ToList();
    }

    return combinations;
}

它可能不太有效，而且它确实有改进的空间，但可以完成工作！

List<string> elements = new List<string> { "1", "2", "3" };
List<string> combinations = GetCombinations(elements);

foreach (string combination in combinations)
{
    System.Console.Write(combination);
}

I just run into a situation where I needed to do this, this is what I came up with:

private static List<string> GetCombinations(List<string> elements)
{
    List<string> combinations = new List<string>();
    combinations.AddRange(elements);
    for (int i = 0; i < elements.Count - 1; i++)
    {
        combinations = (from combination in combinations
                        join element in elements on 1 equals 1
                        let value = string.Join(string.Empty, quot;{combination}{element}".OrderBy(c => c).Distinct())
                        select value).Distinct().ToList();
    }

    return combinations;
}

It may be not too efficient, and it sure has room for improvement, but gets the job done!

List<string> elements = new List<string> { "1", "2", "3" };
List<string> combinations = GetCombinations(elements);

foreach (string combination in combinations)
{
    System.Console.Write(combination);
}

回复收藏 0 原文

爱情眠于流年 2024-12-17 11:43:04

这是基于使用扩展方法的 ojlovecd 答案的改进版本：

public static class ListExtensions
{
    public static IEnumerable<List<T>> GetCombinations<T>(
        this List<T> valuesToCombine)
    {
        var count = Math.Pow(2, valuesToCombine.Count);
        for(var i = 1; i <= count; i++)
        {
            var itemFlagList = i.ToBinaryString(valuesToCombine.Count())
                .Select(x => x == '1').ToList();

            yield return GetCombinationByFlagList(valuesToCombine, itemFlagList)
                .ToList();
        }
    }
    private static IEnumerable<T> GetCombinationByFlagList<T>(
        List<T> valuesToCombine, List<bool> flagList)
    {
        for (var i = 0; i < valuesToCombine.Count; i++)
        {
            if (!flagList[i]) continue;

            yield return valuesToCombine.ElementAt(i);
        }
    }
}

public static class IntegerExtensions
{
    public static string ToBinaryString(this int value, int length)
    {
        return Convert.ToString(value, 2).ToString().PadLeft(length, '0');
    }
}

用法：

var numbersList = new List<int>() { 1, 2, 3 };
var combinations = numbersList.GetCombinations();
foreach (var combination in combinations)
{
    System.Console.WriteLine(string.Join(",", combination));
}

输出：

3
2
2,3
1
1,3
1,2
1,2,3

这个想法基本上是使用一些标志来跟踪哪些项目已添加到组合中。所以在 1, 2 & 的情况下3、生成以下二进制字符串以指示是否应包含或排除某项：
001、010、011、100、101、110 和111

This is an improved version based on the answer from ojlovecd using extension methods:

public static class ListExtensions
{
    public static IEnumerable<List<T>> GetCombinations<T>(
        this List<T> valuesToCombine)
    {
        var count = Math.Pow(2, valuesToCombine.Count);
        for(var i = 1; i <= count; i++)
        {
            var itemFlagList = i.ToBinaryString(valuesToCombine.Count())
                .Select(x => x == '1').ToList();

            yield return GetCombinationByFlagList(valuesToCombine, itemFlagList)
                .ToList();
        }
    }
    private static IEnumerable<T> GetCombinationByFlagList<T>(
        List<T> valuesToCombine, List<bool> flagList)
    {
        for (var i = 0; i < valuesToCombine.Count; i++)
        {
            if (!flagList[i]) continue;

            yield return valuesToCombine.ElementAt(i);
        }
    }
}

public static class IntegerExtensions
{
    public static string ToBinaryString(this int value, int length)
    {
        return Convert.ToString(value, 2).ToString().PadLeft(length, '0');
    }
}

Usage:

var numbersList = new List<int>() { 1, 2, 3 };
var combinations = numbersList.GetCombinations();
foreach (var combination in combinations)
{
    System.Console.WriteLine(string.Join(",", combination));
}

Output:

3
2
2,3
1
1,3
1,2
1,2,3

The idea is to basically use some flags to keep track of which items were already added to the combination. So in case of 1, 2 & 3, the following binary strings are generated in order to indicate whether an item should be included or excluded:
001, 010, 011, 100, 101, 110 & 111

回复收藏 0 原文

恍梦境° 2024-12-17 11:43:04

我想推荐一种我认为非常直观且易于阅读的方法。（注意：它比当前接受的解决方案慢。）

它建立在这样的想法上：对于列表中的每个整数，我们需要使用

所有当前现有的组合来扩展迄今为止聚合的结果组合列表，每个组合都用给定整数
该整数的单个“组合”

在这里，我使用 .Aggregate() 和一个 IEnumerable> 种子，其中包含单个空集合条目。这个空条目让我们可以轻松地同时执行上述两个步骤。在聚合所得组合集合后，可以跳过空集合条目。

它是这样的：

var emptyCollection = Enumerable.Empty<IEnumerable<int>>();
var emptyCombination = Enumerable.Empty<int>();

IEnumerable<int[]> combinations = list
    .Aggregate(emptyCollection.Append(emptyCombination),
        ( acc, next ) => acc.Concat(acc.Select(entry => entry.Append(next))))
    .Skip(1) // skip the initial, empty combination
    .Select(comb => comb.ToArray());

对于输入整数列表 { 1, 2, 3 } 中的每个条目，累积过程如下：

next = 1

{ { } }.Concat({ { }.Append(1) })

{ { } }.Concat({ { 1 } })

{ { }, { 1 } } // acc

next = 2

{ { }, { 1 } }.Concat({ { }.Append(2), { 1 }.Append(2) })

{ { }, { 1 } }.Concat({ { 2 }, { 1, 2 } })

{ { }, { 1 }, { 2 }, { 1, 2 } } // acc

next = 3

{ { }, { 1 }, { 2 }, { 1, 2 } }.Concat({ { }.Append(3), { 1 }.Append(3), { 2 }.Append(3), { 1, 2 }.Append(3) })

{ { }, { 1 }, { 2 }, { 1, 2 } }.Concat({ { 3 }, { 1, 3 }, { 2, 3 }, { 1, 2, 3 } })

{ { }, { 1 }, { 2 }, { 1, 2 }, { 3 }, { 1, 3 }, { 2, 3 }, { 1, 2, 3 } } // acc

跳过第一个（空）条目，我们剩下以下集合：

1
2
1 2
3
1 3
2 3
1 2 3

，可以轻松地按集合长度和集合条目总和进行排序，以获得更清晰的概览。

小提琴示例此处。

I'd like to suggest an approach that I find to be quite intuitive and easy to read. (Note: It is slower than the currently accepted solution.)

It is built on the idea that for each integer in the list, we need to extend the so-far-aggregated resulting combination list with

all currently existing combinations, each extended with the given integer
a single "combination" of that integer alone

Here, I am using .Aggregate() with a seed that is an IEnumerable<IEnumerable<int>> containing a single, empty collection entry. That empty entry lets us easily do the two steps above simultaneously. The empty collection entry can be skipped after the resulting combination collection has been aggregated.

It goes like this:

var emptyCollection = Enumerable.Empty<IEnumerable<int>>();
var emptyCombination = Enumerable.Empty<int>();

IEnumerable<int[]> combinations = list
    .Aggregate(emptyCollection.Append(emptyCombination),
        ( acc, next ) => acc.Concat(acc.Select(entry => entry.Append(next))))
    .Skip(1) // skip the initial, empty combination
    .Select(comb => comb.ToArray());

For each entry in the input integer list { 1, 2, 3 }, the accumulation progresses as follows:

next = 1

{ { } }.Concat({ { }.Append(1) })

{ { } }.Concat({ { 1 } })

{ { }, { 1 } } // acc

next = 2

{ { }, { 1 } }.Concat({ { }.Append(2), { 1 }.Append(2) })

{ { }, { 1 } }.Concat({ { 2 }, { 1, 2 } })

{ { }, { 1 }, { 2 }, { 1, 2 } } // acc

next = 3

{ { }, { 1 }, { 2 }, { 1, 2 } }.Concat({ { }.Append(3), { 1 }.Append(3), { 2 }.Append(3), { 1, 2 }.Append(3) })

{ { }, { 1 }, { 2 }, { 1, 2 } }.Concat({ { 3 }, { 1, 3 }, { 2, 3 }, { 1, 2, 3 } })

{ { }, { 1 }, { 2 }, { 1, 2 }, { 3 }, { 1, 3 }, { 2, 3 }, { 1, 2, 3 } } // acc

Skipping the first (empty) entry, we are left with the following collection:

1
2
1 2
3
1 3
2 3
1 2 3

, which can easily be ordered by collection length and collection entry sum for a clearer overview.

Example fiddle here.

回复收藏 0 原文

但可醉心 2024-12-17 11:43:04

这里的一些解决方案确实很巧妙；尤其是那些使用位图的。

但我发现，在实践中，

如果所需的特定长度范围（例如，8 个元素的输入集中的 3 到 5 个选择的所有变体）
无法处理大型输入列表（并返回空或单例结果而不是抛出异常）；并且
调试起来可能很棘手。

所以我决定写一些不像这里其他人那么聪明的东西。

我更基本的方法认为，Variations(1 to maxLength) 集合只是每个长度 1 到 maxLength 的所有固定长度变体的 UNION。 code>：

即

Variations(1 to maxLength) = Variations(1) + Variations(2) + ... + Variations(maxLength)

，您可以为每个所需的长度执行“从 N 中选择 K”（对于 (1, 2, 3, ..., maxLength) 中的每个 K），然后只需执行将这些单独的结果合并起来产生一个列表列表。

由此产生的代码旨在易于理解和维护：

/// <summary>
/// Generates ALL variations of length between minLength and maxLength (inclusive)
/// Relies on Combinatorics library to generate each set of Variations
/// Nuget https://www.nuget.org/packages/Combinatorics/
/// Excellent more general references (without this solution):
/// https://www.codeproject.com/Articles/26050/Permutations-Combinations-and-Variations-using-C-G
/// Self-authored solution.
/// </summary>
/// <typeparam name="T">Any type without any constraints.</typeparam>
/// <param name="sourceList">The source list of elements to be combined.</param>
/// <param name="minLength">The minimum length of variation required.</param>
/// <param name="maxLength">The maximum length of variation required.</param>
/// <returns></returns>
public static List<List<T>> GenerateVariations<T>(this IEnumerable<T> sourceList, int minLength, int maxLength)
{
    List<List<T>> finalUnion = new();
    foreach (int length in Enumerable.Range(minLength, maxLength))
    {
        Variations<T> variations = new Variations<T>(sourceList, length, GenerateOption.WithoutRepetition);
        foreach (var variation in variations)
        {
            var list = variation.ToList<T>();
            finalUnion.Add(list);
        }
    }
    Debug.WriteLine(sourceList.Count() + " source " + typeof(T).Name + " yielded " + finalUnion.Count());
    return finalUnion;
}

很高兴收到评论（好的和坏的）。也许有一种更简洁的方法可以在 LINQ 中实现这一目标？也许这里真正聪明的人可以将他们的方法与我更基本的方法结合起来？

Some of the solutions here are truly ingenious; especially the ones that use bitmaps.

But I found that in practice these algos

aren't easy to modify if a specific range of lengths needed (e.g. all variations of 3 to 5 choices from an input set of 8 elements)
can't handle LARGE input lists (and return empty or singleton results instead of throwing exception); and
can be tricky to debug.

So I decided to write something not as clever as the other people here.

My more basic approach recognises that the set of Variations(1 to maxLength) is simply a UNION of all fixed-length Variations of each length 1 to maxLength:

i.e

Variations(1 to maxLength) = Variations(1) + Variations(2) + ... + Variations(maxLength)

So you can do a "choose K from N" for each required length (for each K in (1, 2, 3, ..., maxLength)) and then just do a Union of these separate results to yield a List of Lists.

This resulting code intends to be easy to understand and to maintain:

/// <summary>
/// Generates ALL variations of length between minLength and maxLength (inclusive)
/// Relies on Combinatorics library to generate each set of Variations
/// Nuget https://www.nuget.org/packages/Combinatorics/
/// Excellent more general references (without this solution):
/// https://www.codeproject.com/Articles/26050/Permutations-Combinations-and-Variations-using-C-G
/// Self-authored solution.
/// </summary>
/// <typeparam name="T">Any type without any constraints.</typeparam>
/// <param name="sourceList">The source list of elements to be combined.</param>
/// <param name="minLength">The minimum length of variation required.</param>
/// <param name="maxLength">The maximum length of variation required.</param>
/// <returns></returns>
public static List<List<T>> GenerateVariations<T>(this IEnumerable<T> sourceList, int minLength, int maxLength)
{
    List<List<T>> finalUnion = new();
    foreach (int length in Enumerable.Range(minLength, maxLength))
    {
        Variations<T> variations = new Variations<T>(sourceList, length, GenerateOption.WithoutRepetition);
        foreach (var variation in variations)
        {
            var list = variation.ToList<T>();
            finalUnion.Add(list);
        }
    }
    Debug.WriteLine(sourceList.Count() + " source " + typeof(T).Name + " yielded " + finalUnion.Count());
    return finalUnion;
}

Happy to receive comments (good and bad). Maybe there's a more succint way to achieve this in LINQ? Maybe the really smart people here can marry their approach with my more basic one?

回复收藏 0 原文

月亮坠入山谷 2024-12-17 11:43:04

这是 jaolho 解决方案的一个变体，通过按位运算进行优化以获得更好的性能

public static List<List<T>> GetAllCombinations<T>(this List<T> list)
{
    int comboCount = (1 << list.Count) - 1;
    List<List<T>> result = new List<List<T>>(comboCount);
    for (int i = 1; i <= comboCount; i++)
    {
        // make each combo here
        List<T> combo = new List<T>();
        for (int j = 0; j < list.Count; j++)
        {
            if ((i & (1 << j)) != 0)
                combo.Add(list[j]);
        }
        result.Add(combo);
    }
    return result;
}

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

this is a variant of the jaolho's solution, optimized with bitwise operations for better performance

public static List<List<T>> GetAllCombinations<T>(this List<T> list)
{
    int comboCount = (1 << list.Count) - 1;
    List<List<T>> result = new List<List<T>>(comboCount);
    for (int i = 1; i <= comboCount; i++)
    {
        // make each combo here
        List<T> combo = new List<T>();
        for (int j = 0; j < list.Count; j++)
        {
            if ((i & (1 << j)) != 0)
                combo.Add(list[j]);
        }
        result.Add(combo);
    }
    return result;
}

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

回复收藏 0 原文

水晶透心 2024-12-17 11:43:04

请找到非常非常简单的解决方案，无需递归且不占用内存。

独特组合

回复收藏 0 原文

我乃一代侩神 2024-12-17 11:43:03

试试这个：

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();
    }
}

try this:

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();
    }
}

回复收藏 0 原文

听不够的曲调 2024-12-17 11:43:03

假设初始集合中的所有项都是不同，我们可以尝试使用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))代码>

算法说明：

拥有collection.Length不同项的集合，我们得到2 ** collection.Length组合（我们可以将其计算为 1 << collection.Length)：

    mask - comments
------------------------------------
00..0000 - empty, no items are taken
00..0001 - 1st item taken
00..0010 - 2nd item taken
00..0011 - 1st and 2nd items are taken
00..0100 - 3d item taken
...
11..1111 - all items are taken

要生成所有掩码，我们可以直接使用 Enumerable.Range(0, 1 << (data.Length)) Linq 查询。现在有了 index 掩码，当且仅当 index 中的相应位设置为 1 时，我们才应该从集合中获取项目：

011001001
 ^^  ^  ^
 take 7, 6, 3, 0-th items from the collection

代码可以在

.Select(index => data.Where((v, i) => (index & (1 << i)) != 0)

这里对于集合 data 中的每个项目 (v)，我们检查 index 中是否设置了第 i 位（面具）。

Assuming that all items within the initial collection are distinct, we can try using Linq in order to query; let's generalize the solution:

Code:

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());
}

Demo:

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

  var result = Combinations(data);

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

Outcome:

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

If you want to exclude the initial empty array, put .Range(1, (1 << (data.Length)) - 1) instead of .Range(0, 1 << (data.Length))

Algorithm explanation:

Having a collection of collection.Length distinct items we get 2 ** collection.Length combinations (we can compute it as 1 << collection.Length):

    mask - comments
------------------------------------
00..0000 - empty, no items are taken
00..0001 - 1st item taken
00..0010 - 2nd item taken
00..0011 - 1st and 2nd items are taken
00..0100 - 3d item taken
...
11..1111 - all items are taken

To generate all masks we can use direct Enumerable.Range(0, 1 << (data.Length)) Linq query. Now having index mask we should take item from the collection if and only if corresponding bit within index is set to 1:

011001001
 ^^  ^  ^
 take 7, 6, 3, 0-th items from the collection

The code can be

.Select(index => data.Where((v, i) => (index & (1 << i)) != 0)

here for each item (v) in the collection data we check if i-th bit is set in the index (mask).

回复收藏 0 原文

魔法少女 2024-12-17 11:43:03

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

// 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());

Here are two generic solutions for strongly typed lists that will return all unique combinations of list members (if you can solve this with simpler code, I salute you):

// 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());

回复收藏 0 原文

七堇年 2024-12-17 11:43:03

这个答案使用与 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;
  }

This answer uses the same algorithm as ojlovecd and (for his iterative solution) jaolho. The only thing I'm adding is an option to filter the results for a minimum number of items in the combinations. This can be useful, for example, if you are only interested in the combinations that contain at least two items.

Edit: As requested by @user3610374 a filter for the maximum number of items has been added.

Edit 2: As suggested by @stannius the algorithm has been changed to make it more efficient for cases where not all combinations are wanted.

  /// <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;
  }

回复收藏 0 原文

~没有更多了~