Получить все комбинации элементов k с повторением

Question

Я хочу получить список всех возможных комбинаций с повторением.

например.

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

для этого я использую this модифицированный метод, который работает отлично

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.

Вопрос: Есть ли простой способ избежать этого исключения? Нужен ли итеративный подход?

Update:

со ссылкой на комментарий 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]); 

Answer 1

В вашей функции нет проблем. Если вы не попытаетесь поместить результирующий IEnumerable в память (например, вызывая ToArray()), вы не получите Out Of Memory Exception.

Пример ниже работает очень хорошо.

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 байтов.

Как вы хотите использовать результат своей функции?

Answer 2

Здесь вы идете:

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 и только распечатывать, когда программа закончится.