得到所有k个元素的重复组合

本文关键字：组合 元素 | 更新日期: 2023-09-27 18:05:16

我想获得所有可能的重复组合的列表。

。

Input: 1,2,3 
Result: 111,112,...,332,333

对于这个，我使用了这个修改过的方法，效果很好

public static IEnumerable<IEnumerable<T>> CombinationsWithRepeat<T>(this IEnumerable<T> elements, int k)
{
    return k == 0 ? new[] { new T[0] } : elements.SelectMany((e, i) => elements.CombinationsWithRepeat(k - 1).Select(c => (new[] { e }).Concat(c)));
}

我的问题是这种递归方法的内存使用。输入60个元素，K = 4，已经有一个Out Of Memory Exception。

我需要用K = 10来运行这个

问题:有没有简单的方法来避免这个异常?我需要迭代方法吗?

更新:

指的是Corak的评论K必须是动态的

这应该与60元素和K = 10工作，但它不是动态的。

StreamWriter sr = new StreamWriter(@"c:'temp.dat");
List<char> cList = new List<char>() { '1', '2', '3', '4', '5', '6', '7', '8', '9' };
for (int i = 0; i < cList.Count; i++)
    for (int j = 0; j < cList.Count; j++)
        for (int k = 0; k < cList.Count; k++)
            sr.WriteLine(cList[i] + cList[j] + cList[k]);

得到所有k个元素的重复组合

给你:

    const int SelectionSize = 4;
    private static long _variationsCount = 0;
    private static int[] _objects;
    private static int[] _arr;
    static void Main(string[] args)
    {
        _objects = new int[]{1,2,3,4,5,6,7,8,9,10};
        _arr = new int[SelectionSize];
        GenerateVariations(0);
        Console.WriteLine("Total variations: {0}", _variationsCount);
    }
    static void GenerateVariations(int index)
    {
        if (index >= SelectionSize)
            Print();
        else
            for (int i = 0; i < _objects.Length; i++)
            {
                _arr[index] = i;
                GenerateVariations(index + 1);
            }
    }
    private static void Print()
    {
        //foreach (int pos in arr)
        //{
        //    Console.Write(objects[pos] + " ");
        //}
        //Console.WriteLine();
        _variationsCount++;
    }

即使选择大小为10(大约需要2分钟)也可以工作。但请记住，控制台打印真的很慢，这就是我把它注释掉的原因。如果要打印列表，可以使用stringbuilder，只在程序完成时打印。

你的函数没有问题。如果你不尝试将结果IEnumerable放在内存中(例如调用ToArray())，你就不会得到内存溢出异常。

下面的例子就可以了。

class Program
{
    static void Main(string[] args)
    {
        var input = Enumerable.Range(1, 60);
        using (var textWriter = File.AppendText("result.txt"))
        {
            foreach (var combination in input.CombinationsWithRepeat(10))
            {
                foreach (var digit in combination)
                {
                    textWriter.Write(digit);
                }
                textWriter.WriteLine();
            }
        }
    }
}
public static class Extensions
{
    public static IEnumerable<IEnumerable<T>> CombinationsWithRepeat<T>(this IEnumerable<T> elements, int k)
    {
        return k == 0 ? new[] { new T[0] } : elements.SelectMany((e, i) => elements.CombinationsWithRepeat(k - 1).Select(c => (new[] { e }).Concat(c)));
    }
}

但是即使在硬盘上也没有足够的空间来存储结果。有60^10种组合。每个组合使用10-20个字节。

您希望如何使用函数的结果?

相关文章：