Just in time computation of combinations

Question

I want to do something with every combination of ternaries for N variables:

example with 1:

T
F
U

example with 2:

TT
FT
UT
TF
FF
UF
UU

Is there a way to compute this but only as needed: For example:

    var combinator = new Combinator<string>(2, {"T","F","U"});
    List<String> tt = combinator.Next(); 
    //tt contains {"T","T"}

The easiest solution would be to compute it however you are currently compute it, but use a yield return. — Nick Bailey, Mar 30 '16 at 19:29
I don't understand how you are working out your combinations. You have "FT" and "TF", but you have "UT" and no "TU". — Matthew Watson, Mar 30 '16 at 20:38

Arturo Menchaca · Accepted Answer · 2016-03-30T20:30:21.350

You can implement it in an iterator method:

private IEnumerable<List<T>> Combinations<T>(int n, T[] values)
{
    if (n == 0) yield return new List<T>();
    else
    {
        foreach (var list in Combinations(n - 1, values))
            foreach (var item in values)
            {
                var items = new List<T>(list);
                items.Add(item);
                yield return items;
            }
    }
}

This creates all combinations, but does it in a lazy way.

If you want you can create Combinator class like this:

class Combinator<T>
{
    IEnumerator<List<T>> enumerator;

    public Combinator(int n, T[] values)
    {
        enumerator = Combinations(n, values).GetEnumerator();
    }

    public List<T> Next()
    {
        return enumerator.MoveNext() ? enumerator.Current : null;
    }

    private IEnumerable<List<T>> Combinations<T>(int n, T[] values) { ... }
}

score 2 · Answer 2 · answered Mar 30 '16 at 19:50

Probably not the most computationally efficient, but it's combinatorics, so the complexity is probably stuck being awful:

public static IEnumerable<List<T>> Combinations<T>( int count, IEnumerable<T> items )
{
    if( count <= 0 ) yield break;
    if( count == 1 ) 
    {
        foreach( var item in items ) yield return new List<T> { item };
        yield break;
    }

    foreach( var item in items )
    {
        foreach( var combo in Combinations<T>( count - 1, items ) )
        {
            var result = new List<T> { item };
            result.AddRange( combo );
            yield return result;
        }
    }
}

score 1 · Answer 3 · edited Mar 30 '16 at 20:46

It is not clear how you are getting your combinations of TFU.

You list only the following:

TT
FT
UT
TF
FF
UF
UU

However that is missing two combinations, and it should be like this (as far as I can work out):

TT
FT
UT
TF
FF
UF
TU
FU
UU

Assuming that the latter is actually the correct list, then you can compute it "on demand" like so:

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApplication1
{
    class Program
    {
        public static void Main()
        {
            foreach (var combination in Combinator(new [] { "T", "F", "U" }, 2))
                Console.WriteLine(string.Concat(combination));
        }

        public static IEnumerable<IEnumerable<T>> Combinator<T>(IEnumerable<T> sequence, int count)
        {
            if (count == 0)
            {
                yield return Enumerable.Empty<T>();
                yield break;
            }

            foreach (T startingElement in sequence)
            {
                IEnumerable<T> remainingItems = sequence;

                foreach (IEnumerable<T> permutationOfRemainder in Combinator(remainingItems, count - 1))
                    yield return permutationOfRemainder.Concat(new [] { startingElement});
            }
        }
    }
}

score 0 · Answer 4 · answered Mar 30 '16 at 19:55

You could achieve this by giving the cominations some ordering, so you can basically assign a mapping between them and the numbers from 1 to n^m (where n is the length of permutations and m is the number of strings). Then saving the state.

However what this does is bassically reimplementing IEnumerable. https://msdn.microsoft.com/de-de/library/system.collections.ienumerable(v=vs.110).aspx

Even simpler, if you need this in some sort of foreach loop, would be to use just a method that returns IEnumerable. IEnumerable will be lazily evaluated if you use the yield syntax. http://www.dotnetperls.com/yield

Just in time computation of combinations

4 Answers4