Non-recursive Permutations and Combinations


# region Heading

/**************************************************************************************************************/
/*                                                                                                            */
/*  LibExt.Permutations.cs                                                                                    */
/*                                                                                                            */
/*  Calculates the Permutations of the provided Things                                                        */
/*                                                                                                            */
/*  This is free code, use it as you require. If you modify it please use your own namespace.                 */
/*                                                                                                            */
/*  If you like it or have suggestions for improvements please let me know at: PIEBALDconsult@aol.com         */
/*                                                                                                            */
/*  Modification history:                                                                                     */
/*  2009-07-20          Sir John E. Boucher     Created                                                       */
/*                                                                                                            */
/**************************************************************************************************************/

# endregion

namespace PIEBALD.Lib.LibExt.Permutations
{
    using PIEBALD.Lib.LibExt.ApplyIndices ;

    public static class LibExt
    {
        /**
        <summary>
            Calculates the Permutations of the provided Things.
        </summary>
        <param name="Things">
            An IList of items for which you want Permutations.
        </param>
        <param name="Take">
            The number of Things to include in each Permutation.
        </param>
        <returns>
            An enumerator of the Permutations.
        </returns>
        <exception cref="System.ArgumentNullException">
            If Things is null.
        </exception>
        <exception cref="System.ArgumentNullException">
            If Take is less than one (1) or greater than the number of Things.
        </exception>
        */
        public static System.Collections.Generic.IEnumerable<System.Collections.Generic.IEnumerable<T>>
        Permutations<T>
        (
            this System.Collections.Generic.IList<T> Things
        ,
            int                                      Take
        )
        {
            if ( Things == null )
            {
                throw ( new System.ArgumentNullException
                (
                    "Things"
                ,
                    "Things must not be null"
                ) ) ;
            }
        
            if ( Take < 1 )
            {
                throw ( new System.ArgumentOutOfRangeException 
                ( 
                    "Take" 
                , 
                    Take 
                , 
                    "Take must not be less than one" 
                ) ) ;
            }

            if ( Take > Things.Count )
            {
                throw ( new System.ArgumentOutOfRangeException 
                ( 
                    "Take" 
                , 
                    Take 
                , 
                    "Take must not be greater than the number of items in Things" 
                ) ) ;
            }
            
            PIEBALD.Types.UniqueIntStack stack = 
                new PIEBALD.Types.UniqueIntStack() ;
        
            StackState state = StackState.Push ;

            stack.Push ( 0 ) ;
        
            while ( state != StackState.Break ) 
            {
                switch ( state )
                {
                    case StackState.Push :
                    {
                        if ( stack.Count == Take )
                        {
                            state = StackState.Return ;
                        }
                        else if ( stack.Push ( 0 ) == Things.Count )
                        {
                            state = StackState.Pop ;
                        }

                        break ;
                    }

                    case StackState.Pop :
                    {
                        stack.Pop() ;

                        if ( stack.Count == 0 )
                        {
                            state = StackState.Break ;
                        }
                        else
                        {
                            state = StackState.Increment ;
                        }

                        break ;
                    }

                    case StackState.Increment :
                    {
                        if ( stack.Push ( stack.Pop() + 1 ) == Things.Count )
                        {
                            state = StackState.Pop ;
                        }
                        else
                        {
                            state = StackState.Push ;
                        }

                        break ;
                    }

                    case StackState.Return :
                    {
                        yield return ( Things.ApplyIndices ( stack.Values ) ) ;

                        state = StackState.Increment ;

                        break ;
                    }
                }
            }
        
            yield break ;
        }

        private enum StackState
        {
            Push
        ,
            Pop
        ,
            Increment
        ,
            Return
        ,
            Break
        }
    }
}