Вопрос по c#, math – Генерация всех комбинаций для списка строк

14

Я хочу создать список всех возможных комбинаций списка строк (фактически это список объектов, но для простоты мы будем использовать строки). Мне нужен этот список, чтобы я мог проверить каждую возможную комбинацию в модульном тесте.

Так, например, если у меня есть список:

<code>  var allValues = new List<string>() { "A1", "A2", "A3", "B1", "B2", "C1" }
</code>

мне нужноList<List<string>> со всеми комбинациями, такими как:

<code>  A1
  A2
  A3
  B1
  B2
  C1
  A1 A2
  A1 A2 A3
  A1 A2 A3 B1
  A1 A2 A3 B1 B2
  A1 A2 A3 B1 B2 C1
  A1 A3
  A1 A3 B1
  etc...
</code>

Рекурсивная функция - это, вероятно, способ сделать это, чтобы получить все комбинации, но это кажется сложнее, чем я себе представлял.

Есть указатели?

Спасибо.

РЕДАКТИРОВАТЬ: два решения, с или без рекурсии:

<code>public class CombinationGenerator<T>
{
    public IEnumerable<List<T>> ProduceWithRecursion(List<T> allValues) 
    {
        for (var i = 0; i < (1 << allValues.Count); i++)
        {
            yield return ConstructSetFromBits(i).Select(n => allValues[n]).ToList();
        }
    }

    private IEnumerable<int> ConstructSetFromBits(int i)
    {
        var n = 0;
        for (; i != 0; i /= 2)
        {
            if ((i & 1) != 0) yield return n;
            n++;
        }
    }

    public List<List<T>> ProduceWithoutRecursion(List<T> allValues)
    {
        var collection = new List<List<T>>();
        for (int counter = 0; counter < (1 << allValues.Count); ++counter)
        {
            List<T> combination = new List<T>();
            for (int i = 0; i < allValues.Count; ++i)
            {
                if ((counter & (1 << i)) == 0)
                    combination.Add(allValues[i]);
            }

            // do something with combination
            collection.Add(combination);
        }
        return collection;
    }
}
</code>
Вам не нужна рекурсия:stackoverflow.com/questions/10331229/… Henrik
Представьте себе двоичный счетчик. Это должно начать вас. SimpleVar
A1 A2 == A2 A1, действительно L-Four
Я знаю, что это не совсем то, что вы искали, но у Microsoft есть эта система в бета-версии, которая будет автоматически генерировать комбинации входов для вас. Это называется Pex:research.microsoft.com/en-us/projects/pex Christopher Rathermel
A1 A2 == A2 A1? Royi Namir

Ваш Ответ

4   ответа
0
Ответы только на ссылки не рекомендуется использовать при переполнении стека, поскольку ссылки могут разрываться, а ресурсы, на которые они ссылаются, могут изменяться. Рассмотрите суммирование соответствующих частей ссылки здесь вместо этого.
Кроме того, ответ, с которым вы связались, заключается в созданииpermutations, которыйare not the same thing какcombinations.
2

посмотрите на этот проект, чтобы увидеть, как он реализован.

http://www.codeproject.com/Articles/26050/Permutations-Combinations-and-Variations-using-C-G

Но вы можете использовать его, так как он открытCPOL.

Например:

var allValues = new List<string>() { "A1", "A2", "A3", "B1", "B2", "C1" };
List<String> result = new List<String>();
var indices = Enumerable.Range(1, allValues.Count);
foreach (int lowerIndex in indices)
{
    var partVariations = new Facet.Combinatorics.Variations<String>(allValues, lowerIndex);
    result.AddRange(partVariations.Select(p => String.Join(" ", p)));
}

var length = result.Count;  // 1956
12

используя тот факт, что n-битное двоичное число естественно соответствует подмножеству n-элементного набора.

private IEnumerable<int> constructSetFromBits(int i)
{
    for (int n = 0; i != 0; i /= 2, n++)
    {
        if ((i & 1) != 0)
            yield return n;
    }
}

List<string> allValues = new List<string>()
        { "A1", "A2", "A3", "B1", "B2", "C1" };

private IEnumerable<List<string>> produceEnumeration()
{
    for (int i = 0; i < (1 << allValues.Count); i++)
    {
        yield return
            constructSetFromBits(i).Select(n => allValues[n]).ToList();
    }
}

public List<List<string>> produceList()
{
    return produceEnumeration().ToList();
}
Здравствуйте, это не возвращает список & lt; List & lt; string & gt; & gt; ... L-Four
@Lud: тогда вам нужно пропустить строку. Присоединяйтесь :) Только что обновили.
0

Еще одно рекурсивное решение. ОтAllCombinations в приведенном ниже коде вы получите все возможные комбинации. Логика:

Starting with one element. Generate all possible combinations with it. Move to next element and begin with step 2 again.

Код:

public class Combination<T>
{
    private IEnumerable<T> list { get; set; }
    private int length;
    private List<IEnumerable<T>> _allCombination;

    public Combination(IEnumerable<T> _list)
    {
        list = _list;
        length = _list.Count();

        _allCombination = new List<IEnumerable<T>>();
    }

    public IEnumerable<IEnumerable<T>> AllCombinations
    {
        get
        {
            GenerateCombination(default(int), Enumerable.Empty<T>());

            return _allCombination;
        }
    }

    private void GenerateCombination(int position, IEnumerable<T> previousCombination)
    {
        for (int i = position; i < length; i++)
        {
            var currentCombination = new List<T>();
            currentCombination.AddRange(previousCombination);
            currentCombination.Add(list.ElementAt(i));

            _allCombination.Add(currentCombination);

            GenerateCombination(i + 1, currentCombination);

        }
 ,   }
}

Похожие вопросы