获取k个元素的带重复组合

Question

我希望能获得一个包含重复元素的所有可能组合的列表。

例如：

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时，已经出现了内存不足异常。

我需要以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]);

- fubo

---

“K = 10” 是固定的吗？如果是，您尝试过使用10个嵌套的for循环（丑陋但可能有效）吗？ - Corak

@Corak - 没有 K 也可以是不同的数字 - 那部分必须是动态的。 - fubo

也许看看 http://ericlippert.com/tag/permutations/ 可以有所帮助。您需要将“TinySet”从“Int32”调整为“Int64”来存储数据点，但否则它可能只需能够生成所有 604661760000000000 个项目... - Corak

啊，抱歉，似乎没有重复。不过，这可能会指引你朝一个有用的方向前进。 - Corak

然而，“最简单”的方法是让T4为不同的K值创建方法，然后使用适合的方法。再次强调：虽然不太美观，但是可行的。 - Corak

Answer 1

Here you go:

    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，并且只在程序结束时打印。

- stann1

---

太好了！为了更灵活，有一个小建议：public class Combination<T> { public Combination(IEnumerable<T> items) { mItems = items.ToArray(); } private readonly T[] mItems; private T[] mResult; public void GetCombinations(int k, Action<IList<T>> action) { mResult = new T[k]; GenerateVariations(0, k, action); } private void GenerateVariations(int index, int k, Action<IList<T>> action) { if (index >= k) { action(mResult); } else { foreach (var item in mItems) { mResult[index] = item; GenerateVariations(index + 1, k, action); }}}} - Corak

Answer 2

你的函数没有问题。如果你不尝试将结果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字节。

您想如何使用函数的结果？

- Nickolay Andreychuk

---

你说得对，我在调用中使用了 ToList() 并将整个列表实例化到内存中。你在 Main 中的调用很好！我将数据存储在数据库中。 - fubo

你仍然没有足够的空间来存储结果。 - Nickolay Andreychuk