Get all combinations of k elements with repetion

Question

I want to get a list of all possible combinations with repetion.

e.g.

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

for this i use this modified method which is working fine

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

my problem is the memory usage of this recursive approach. With a input of 60 elements and K = 4 there is already a Out Of Memory Exception.

I need to run this with K = 10.

Question: Is there a easy way to avoid this exception? Do i need a iterative approach?

Update:

referring to Corak's comment - K has to be dynamic

this should work with 60 Elements and K = 10 but it's not dynamic.

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

Is `K = 10` fixed? If so, have you tried 10 nested for loops (ugly, but might work)? — Corak, Jul 28 '15 at 06:33
@Corak - no `K` can also be a different number - that part has to be dynamic — fubo, Jul 28 '15 at 06:34
Maybe looking through http://ericlippert.com/tag/permutations/ will help. You'll need to adapt the `TinySet` from `Int32` to `Int64` to store your data points, but otherwise it might just be able to produce all 604661760000000000 items... — Corak, Jul 28 '15 at 07:14
Ah, sorry, that seems to be without repetition. Still, it might point you in a useful direction. — Corak, Jul 28 '15 at 07:24
Still, the "easiest" way would be to let T4 create the methods for different values of `K` and then use the fitting one. Again: ugly, but works. — Corak, Jul 28 '15 at 07:30

score 2 · Answer 1 · answered Jul 28 '15 at 07:38

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

It works even with a selection size of 10 (takes around 2 min). But bear in mind that the Console printing is really slow, that is why I commented it out. If you want to print the list, you could use stringbuilder and only print when the program finishes.

Great! Slight suggestion for more flexibility: `public class Combination { public Combination(IEnumerable items) { mItems = items.ToArray(); } private readonly T[] mItems; private T[] mResult; public void GetCombinations(int k, Action> action) { mResult = new T[k]; GenerateVariations(0, k, action); } private void GenerateVariations(int index, int k, Action> action) { if (index >= k) { action(mResult); } else { foreach (var item in mItems) { mResult[index] = item; GenerateVariations(index + 1, k, action); }}}}` — Corak, Jul 28 '15 at 08:36

Nickolay Andreychuk · Accepted Answer · 2015-07-28T08:59:43.143

There is no problem in your function. If you won't try to place resulting IEnumerable in memory (e.g. calling ToArray()) you won't get Out Of Memory Exception.

Example below works just fine.

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

But you won't have enough space to store result even on hardrive. There is 60^10 combinations. Each combination uses 10-20 bytes.

How do you want to use the result of your function?

You're right i had a `ToList()` in the call and materialized the whole list in the memory. Your call in `Main` works great! I store the Data in a DataBase. — fubo, Jul 28 '15 at 08:45

Get all combinations of k elements with repetion

2 Answers2