Combination Creator?

Question 1

This isn't necessarily the most efficient, but here's how you could do this using non-recursive methods returning IEnumerable<T>. Something like this will probably require the least possible memory, since it doesn't require building all the permutations in memory. Instead, it just allows you to iterate over the permutations one by one.

private static void Main()
{
    var input1 = new[] {"1", "2", "3"};
    foreach (var output in EnumeratePermutations(input1))
        Debug.WriteLine(String.Join(",", output));
}

private static IEnumerable<T[]> EnumeratePermutations<T>(T[] input)
{
    return from partCount in Enumerable.Range(1, input.Length)
            let inputs = Enumerable.Repeat(input, partCount).ToArray()
            from indices in EnumerateCrossjoinIndices(inputs)
            where indices.Distinct().Count() == indices.Length
            select indices.Select(n => input[n]).ToArray();
}

private static IEnumerable<int[]> EnumerateCrossjoinIndices(params Array[] arrays)
{
    var arrayCount = arrays.Length;
    if (arrayCount == 0)
        yield break;

    if (arrays.Any(a => a.Length == 0))
        yield break;

    var indexer = new int[arrayCount];

    yield return (int[]) indexer.Clone();

    for (var dimension = arrayCount - 1; dimension >= 0; --dimension)
    {
        ++indexer[dimension];
        if (indexer[dimension] == arrays[dimension].Length)
            indexer[dimension] = 0;
        else
        {
            yield return (int[]) indexer.Clone();
            dimension = arrayCount;
        }
    }
}

EnumerateCrossjoinIndices takes n arrays of potentially different lengths and yields an enumeration of the indices that would be used in a crossjoin operation. For example, given {"1","2"} and {"A","B","C"}, it would yield 6 arrays {0,0}, {0,1}, {0,2}, {1,0}, {1,1}, {1,2}. Note that the arrays yielded by this method contain indices into the input arrays, not the elements at those indices.

EnumeratePermutations takes an array and yields the permutations of the items of that array. It does this by enumerating over the indices that would be used to crossjoin the array against itself x times (where x = 1 to n, where n is the number of items in the array). It then filters out any set of crossjoin indices where the set isn't a distinct set.

Question 2

Try this sample code:

private static List<int> AllPossibleCombinations(IList<int> alphabet)
{
    List<int[]> combinations = new List<int[]>();
    MakeCombination(combinations, alphabet.Count, new int[0]); // Start recursion
    combinations.RemoveAt(0);   // Remove empty combination
    return combinations.ConvertAll(c => c.Aggregate(0, (sum, index) => sum * 10 + alphabet[index]));
}

private static void MakeCombination(List<int[]> output, int length, int[] usedIndices)
{
    output.Add(usedIndices);
    for (int i = 0; i < length; i++)
        if (Array.IndexOf(usedIndices, i) == -1)    // If the index wasn't used earlier
        {
            // Add element to the array of indices by creating a new one:
            int[] indices = new int[usedIndices.Length + 1];
            usedIndices.CopyTo(indices, 0);
            indices[usedIndices.Length] = i;

            if (length + 1 != indices.Length)
                MakeCombination(output, length, indices);  // Recursion
        }
}

It uses recursion to generate desired combinations.

Usage:

var t = AllPossibleCombinations(new[] { 1, 2, 3 });

Question 3

Solution 1

The more generic and type independent way is to create tree-based algorithm which returns collection of combinations of input objects.

Code:

public static class IEnumerableExtensions
{
    private class Node<T>
    {
        public Node()
        {
            Children = new List<Node<T>>();
        }

        public T Value
        {
            get;
            set;
        }

        public bool IsRoot
        {
            get;
            set;
        }

        public List<Node<T>> Children
        {
            get;
            private set;
        }

        public Node<T> Parent
        {
            get;
            set;
        }

        public List<Node<T>> Path
        {
            get
            {
                List<Node<T>> Result = new List<Node<T>>();

                Result.Add(this);

                if (this.Parent.IsRoot == false)
                {
                    Result.AddRange(this.Parent.Path);
                }

                return Result;
            }
        }
    }

    public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> enumerable)
    {
        List<Node<T>> AllNodes = new List<Node<T>>();

        // Create tree.
        Node<T> Root = new Node<T>() { IsRoot = true };
        Queue<Node<T>> Queue = new Queue<Node<T>>();
        Queue.Enqueue(Root);

        int CurrentLevel = 0;
        int LevelsToCreate = enumerable.Count();
        while (Queue.Count > 0)
        {
            var CurrentLevelNodes = Queue.ToList();
            Queue.Clear();

            foreach (var LoopNode in CurrentLevelNodes)
            {
                if (LoopNode.Children.Count == 0)
                {
                    foreach (var LoopValue in enumerable)
                    {
                        var NewNode = new Node<T>() { Value = LoopValue, Parent = LoopNode };
                        AllNodes.Add(NewNode);
                        LoopNode.Children.Add(NewNode);
                        Queue.Enqueue(NewNode);
                    }
                }
            }

            CurrentLevel++;
            if (CurrentLevel >= LevelsToCreate)
            {
                break;
            }
        }

        // Return list of all paths (which are combinations).
        List<List<T>> Result = new List<List<T>>();
        foreach (var LoopNode in AllNodes)
        {
            if (!LoopNode.IsRoot)
            {
                List<T> Combination = LoopNode.Path.Select(Item => Item.Value).ToList();
                Result.Add(Combination);
            }
        }

        return Result;
    }
}

Example with numbers:

class Program
{
    static void Main(string[] args)
    {
        List<int> Input = new List<int>() { 1, 2, 3 };
        var Combinations = Input.Combinations();
    }
}

Example with strings:

    static void Main(string[] args)
    {
        var Input = new List<string>() { "a", "b" };
        var Combinations = Input.Combinations();


        foreach (var LoopCombination in Combinations)
        {
            string Combination = string.Join(String.Empty, LoopCombination);
            Console.WriteLine(Combination);
        }

        Console.ReadKey();
    }

Solution 2

The second idea is to not to use tree-based algorithm and create combinations step-by-step - it may be faster.

Code:

public class Combinator<T>
{
    private readonly Dictionary<int, T> _Pattern;
    private readonly int _Min = 0;
    private readonly int _Max;

    private List<int> _CurrentCombination;

    public Combinator(IEnumerable<T> pattern)
    {
        _Pattern = new Dictionary<int, T>();
        for (int i = 0; i < pattern.Count(); i++)
        {
            _Pattern.Add(i, pattern.ElementAt(i));
        }

        _CurrentCombination = new List<int>();
        _Max = pattern.Count() - 1;
    }

    public bool HasFinised
    {
        get;
        private set;
    }

    public IEnumerable<T> Next()
    {
        // Initialize or increase.
        if (_CurrentCombination.Count == 0)
        {
            _CurrentCombination.Add(_Min);
        }
        else
        {
            MyIncrease(_CurrentCombination.Count - 1);
        }

        if (_CurrentCombination.Count - 1 == _Max && _CurrentCombination.All(Key => Key == _Max))
        {
            HasFinised = true;
        }

        return _CurrentCombination.Select(Key => _Pattern[Key]).ToList();;
    }

    private void MyIncrease(int index)
    {
        if (index >= 0)
        {
            _CurrentCombination[index] = _CurrentCombination[index] + 1;

            if (_CurrentCombination[index] > _Max)
            {
                _CurrentCombination[index] = _Min;

                if (index - 1 < 0)
                {
                    _CurrentCombination.Insert(0, -1);
                    index++;
                }

                MyIncrease(index - 1);
            }
        }
    }
}

Example:

class Program
{
    static void Main(string[] args)
    {
        var Pattern = new List<string>() { "a", "b", "c" };
        Combinator<string> Combinator = new Combinator<string>(Pattern);

        while (Combinator.HasFinised == false)
        {
            var Combined = Combinator.Next();
            var Joined = string.Join("-", Combined);
            Console.WriteLine(Joined);
        }

        Console.ReadKey();
    }
}

If you want to combine items with others only:

    static void Main(string[] args)
    {
        Combinator<int> Combinator = new Combinator<int>(new List<int>() { 1, 2, 3 });

        while (Combinator.HasFinised == false)
        {
            var NextCombination = Combinator.Next();
            var DistinctCheck = NextCombination.ToList().Distinct();
            if (DistinctCheck.Count() == NextCombination.Count())
            {
                Console.WriteLine(string.Join(String.Empty, NextCombination.Select(Item => Item.ToString())));
            }                
        }

        Console.ReadKey();
    }