Сгенерировать комбинации общего списка

Question

Мне нужно создать список из другого списка, который содержит любую возможную комбинацию. Изучая возможные решения, я нашел много интересных подходов, но все, похоже, генерируют результаты, основанные на количестве предоставленных записей. Мне нужно, чтобы комбинации увеличивались до максимального порога.

т.е. рассмотрим следующий массив

1,2,3,4,5

Мне нужны результаты, чтобы выглядеть примерно так (порог 3 в этом примере)

1 
1,2 
1,2,3 
1,2,4 
1,2,5 
1,3,4 
2,3,5... etc 

В актуальность, данные будут IEnumerable. Я использовал простой int [], чтобы проиллюстрировать желаемые результаты.

Answer 1

Предполагая, что у вас уже есть решение, чтобы найти комбинации для конкретного подсчета (которые вы сказали, что вы), скажем подписи:

public static IEnumerable<IEnumerable<T>> Combinations<T>(
    IList<T> source, int count) 

Тогда вы можете легко получить комбинации для всех рассчитывает, вызывая его N раз:

public static IEnumerable<IEnumerable<T>> Combinations<T>(IList<T> source) 
{ 
    return Enumerable.Range(0, source.Count) 
      .SelectMany(i => Combinations(source, i)); 
} 

Answer 2

Вот одно решение:

public static IEnumerable<T[]> Combinations<T>(IEnumerable<T> items, int threshold) 
{ 
    var comboBuilder = new List<T>(); 
    foreach (var combo in EnumerateCombos(items, comboBuilder, 0, threshold)) 
    { 
     yield return combo; 
    } 
} 
private static IEnumerable<T[]> EnumerateCombos<T>(IEnumerable<T> items, List<T> currentCombo, 
                int startIndex, int threshold) 
{ 
    if (currentCombo.Count >= threshold) { yield break; } 

    for (int i = startIndex; i < items.Count(); i++) 
    { 
     //Skip past the items we've already gone through in the current combo: 
     var item = items.Skip(i).First(); 

     //Create a new combination with the next available item: 
     currentCombo.Add(item); 
     yield return currentCombo.ToArray(); 

     //Repeat the process with the rest of the remaining items: 
     foreach (var combo in EnumerateCombos(items, currentCombo, i + 1, threshold)) 
     { 
      yield return combo; 
     } 

     //Recursion cleanup: 
     currentCombo.RemoveAt(currentCombo.Count - 1); 
    } 
} 

Answer 3

Мое решение использует простой рекурсивный алгоритм для создания комбинаций:

• Когда мы идем через последовательность мы можем немедленно возвратить последовательность, которая содержит только текущее значение. Я написал простой метод расширения для создания IEnumerable для одного элемента.

• Далее мы рекурсивно генерируем все комбинации для остальных элементов с порогом, уменьшенным на 1, и объединяем каждое из них с текущим значением.

Я предполагаю, что элементы не должны повторяться (т. Е. {1, 1} или {1, 2, 1} не допускаются). Если вы хотите разрешить повторяющиеся элементы, вы можете удалить переменную remaining и заменить ее values на рекурсивный вызов GetCombinations.

Обратите внимание на использование ключевого слова yield. Это означает, что код использует отложенное выполнение. Нет необходимости хранить промежуточные результаты до фактического перечисления результата.

public static IEnumerable<IEnumerable<T>> GetCombinations<T>(IEnumerable<T> values, int threshold) 
{ 
    var remaining = values; 

    foreach (T value in values) 
    { 
     yield return value.Yield(); 

     if (threshold < 2) 
     { 
      continue; 
     } 

     remaining = remaining.Skip(1); 

     foreach (var combination in GetCombinations(remaining, threshold - 1)) 
     { 
      yield return value.Yield().Concat(combination); 
     } 
    } 
} 

public static IEnumerable<T> Yield<T>(this T item) 
{ 
    yield return item; 
} 

Для массива целых чисел {1, 2, 3, 4, 5} выход:

1 
1, 2 
1, 2, 3 
1, 2, 4 
1, 2, 5 
1, 3 
1, 3, 4 
1, 3, 5 
1, 4 
1, 4, 5 
1, 5 
2 
2, 3 
2, 3, 4 
2, 3, 5 
2, 4 
2, 4, 5 
2, 5 
3 
3, 4 
3, 4, 5 
3, 5 
4 
4, 5 
5