Click here to Skip to main content
15,867,568 members
Articles / Programming Languages / C#
Article

Non-recursive Permutations and Combinations

Rate me:
Please Sign up or sign in to vote.
4.87/5 (11 votes)
22 Dec 2010CPOL4 min read 47.5K   365   16   18
Enumerating permutations and combinations without recursion.

Introduction

Here I'll present my implementation of non-recursive permutations and combinations of a generic list of objects. I don't actually use this code in production, I wrote it as a personal exercise. I only hope that the techniques used will be of some use to someone.

If the provided list contains nulls or duplicates, they will be included, not ignored; if you don't want nulls and duplicates, don't provide them; otherwise, I'll assume you provided them because you want them.

Background

A while back, someone posted recursive implementations of permutations and combinations. I commented that recursion wasn't a good way to do it. At that time, I wrote these implementations, mainly to be sure that I wasn't talking out the wrong end. Eventually, someone else called me on it and asked that I put my cards on the table, so here is my code.

Theory

I won't go into the theory of permutations and combinations; you can look them up on Wikipedia. What I will say, is that as I thought about this in relation to .NET and the IList<T> interface in particular, it occurred to me that performing permutations and combinations can be reduced to performing the permutations and combinations of the indices of the items, rather than the items themselves. (The IList interface specifies 32-bit signed integers as indices.) That makes the task a little easier -- the indices are always a contiguous sequence of integers from 0 to n-1 (where n is the number of items in the list). Therefore, the underlying code need not be generic.

UniqueInt

Because each index value may appear in the output list at most once, I needed a class that would track which values were already in use and not allow a second index to hold a repeated value. The UniqueInt class accomplishes this; no two instances of the class that share the same HashSet will hold the same value. If an attempt to set the value of an instance would result in a duplicate value, the instance will try the next higher value; this continues until an unused value is found.

(Usage of this technique is somewhat overkill for combinations, but is important for permutations.)

C#
public sealed class UniqueInt : System.IDisposable
{
    private System.Collections.Generic.HashSet<int> taken ;

    private readonly int current ;

    public UniqueInt
    (
        int   Value
    ,
        System.Collections.Generic.HashSet<int> Taken
    )
    {
        if ( Taken == null )
        {
            throw ( new System.ArgumentNullException
            (
                "Taken"
            ,
                "Taken must not be null"
            ) ) ;
        }

        this.taken = Taken ;

        lock ( this.taken )
        {
            while ( this.taken.Contains ( Value ) )
            {
                Value++ ;
            }

            this.taken.Add ( this.current = Value ) ;
        }

        return ;
    }

    public void
    Dispose
    (
    )
    {
        if ( this.taken != null )
        {
            this.taken.Remove ( this.current ) ;

            this.taken = null ;
        }

        return ;
    }

    public int
    Value
    {
        get
        {
            if ( this.taken == null )
            {
                throw ( new System.ObjectDisposedException
                    ( "" , "This instance has been disposed" ) ) ;
            }

            return ( this.current ) ;
        }
    }

    public override string
    ToString
    (
    )
    {
        return ( this.Value.ToString() ) ;
    }

    public static implicit operator
    int
    (
        UniqueInt Op
    )
    {
        return ( Op.Value ) ;
    }
}

Notice that the Dispose method will remove the value from the HashSet so that it can be used by another instance.

UniqueIntFactory

The UniqueIntFactory class merely encapsulates the process of instantiating a HashSet and then providing it to the UniqueInts that it instantiates. All UniqueInt instances created by the same UniqueIntFactory will share a HashSet and therefore will be unique within that group.

C#
public sealed class UniqueIntFactory
{
    private readonly System.Collections.Generic.HashSet<int> taken ;

    public UniqueIntFactory
    (
    )
    {
        this.taken = new System.Collections.Generic.HashSet<int>() ;

        return ;
    }

    public UniqueInt
    NewValue
    (
    )
    {
        return ( new UniqueInt ( 0 , this.taken ) ) ;
    }

    public UniqueInt
    NewValue
    (
        int Value
    )
    {
        return ( new UniqueInt ( Value , this.taken ) ) ;
    }
}

Stack

The Stack class is a simple class derived from Stack<T>, but with an indexer that accesses the base class' private array. (Go ahead and vote 1 if you like, you know you wanna.)

The important parts are the static constructor, which uses Reflection to access the FieldInfo for the private array.

Note that we can't cache a reference to the array itself because a new array will be instantiated if the Stack is extended.

C#
protected static readonly System.Reflection.FieldInfo arrayinfo ;

static Stack
(
)
{
    arrayinfo = typeof(System.Collections.Generic.Stack<T>).GetField
    (
        "_array"
    ,
         System.Reflection.BindingFlags.Instance
         |
         System.Reflection.BindingFlags.NonPublic
    ) ;

    return ;
}

And the FIFO enumerator that will be used for our permutations and combinations (the built-in enumerator is LIFO):

C#
public virtual System.Collections.Generic.IEnumerable<T>
FIFO
{
    get
    {
        lock ( this.pickle )
        {
            T[] temp = (T[]) arrayinfo.GetValue ( this ) ;

            for ( int i = 0 ; i < this.Count ; i++ )
            {
                yield return ( temp [ i ] ) ;
            }

            yield break ;
        }
    }
}

UniqueIntStack

Combine those two classes together and you get a UniqueIntStack -- a Stack that contains unique 32-bit signed integers.

C#
public class UniqueIntStack
{
    private readonly PIEBALD.Types.UniqueIntFactory               factory ;
    private readonly PIEBALD.Types.Stack<PIEBALD.Types.UniqueInt> stack   ;

    public UniqueIntStack
    (
    )
    {
        this.factory = new PIEBALD.Types.UniqueIntFactory() ;
        this.stack   = new PIEBALD.Types.Stack<PIEBALD.Types.UniqueInt>() ;

        return ;
    }

    public virtual int
    Count
    {
        get
        {
            lock ( this.factory )
            {
                return ( this.stack.Count ) ;
            }
        }
    }

    public virtual int
    Push
    (
        int Value
    )
    {
        lock ( this.factory )
        {
            PIEBALD.Types.UniqueInt result = this.factory.NewValue ( Value ) ;

            this.stack.Push ( result ) ;
            
            return ( result ) ;
        }
    }

    public virtual int
    Pop
    (
    )
    {
        lock ( this.factory )
        {
            using
            (
                PIEBALD.Types.UniqueInt result
             =
                this.stack.Pop()
            )
            {
                return ( result ) ;
            }
        }
    }

    public virtual int
    Peek
    (
    )
    {
        lock ( this.factory )
        {
            return ( this.stack.Peek() ) ;
        }
    }

    public virtual int
    this
    [
        int Index
    ]
    {
        get
        {
            lock ( this.factory )
            {
                try
                {
                    return ( this.stack [ Index ] ) ;
                }
                catch ( System.IndexOutOfRangeException err )
                {
                    throw ( new System.ArgumentOutOfRangeException
                    (
                        "That index is out of range"
                    ,
                        err
                    ) ) ;
                }
            }
        }
    }

    public virtual System.Collections.Generic.IEnumerable<int>
    Values
    {
        get
        {
            lock ( this.factory )
            {
                foreach
                (
                    PIEBALD.Types.UniqueInt val
                in
                    this.stack.FIFO
                )
                {
                    yield return ( val ) ;
                }

                yield break ;
            }
        }
    }
}

Note the Values enumerator, we'll be using it in a moment.

Combinations and Permutations

These two Extension Methods are nearly identical. Other than their names, there is only one statement difference between them, so I'll present Combinations.

Writing this article has given me a good reason to revisit this code. The code wasn't as elegant as I'd like, and I wanted to find a more elegant implementation. What I eventually came up with is a state machine; here are the states:

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

And here is the machine; it is an enumerator that yields enumerators of Things:

C#
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 ( stack.Peek() ) == 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 ;

ApplyIndices

ApplyIndices is an Extension Method that returns an enumerator that contains the members of the provided Things based on the provided Indices. The code is a little more convoluted than I'd like because yield isn't allowed within a try/catch.

C#
public static System.Collections.Generic.IEnumerable<T>
ApplyIndices<T>
(
    this System.Collections.Generic.IList<T>    Things
,
    System.Collections.Generic.IEnumerable<int> Indices
)
{
    int count = 0 ;

    foreach
    (
        int index
    in
        Indices
    )
    {
        T thing ;

        try
        {
            thing = Things [ index ] ;
        }
        catch ( System.IndexOutOfRangeException err )
        {
            throw ( new System.IndexOutOfRangeException
            (
                System.String.Format
                (
                    "Index {0} equals {1}, which is outside the range 0..{2}"
                ,
                    count
                ,
                    index
                ,
                    Things.Count - 1
                )
            ,
                err
            ) ) ;
        }

        yield return ( thing ) ;

        count++ ;
    }

    yield break ;
}

PermCombDemo

PermCombDemo is a simple console application that demonstrates the various permutations and combinations of any command-line parameters you provide.

Build.bat

I've included a simple BAT file to build and execute PermCombDemo. Ensure that CSC is in your path, perhaps by using the Visual Studio Command Prompt if you like. If you want to build the code in the IDE of your choice, you're on your own.

Points of Interest

The only surprise was that yield isn't allowed within a try/catch.

History

  • 2010-12-21: First submitted.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Software Developer (Senior)
United States United States
BSCS 1992 Wentworth Institute of Technology

Originally from the Boston (MA) area. Lived in SoCal for a while. Now in the Phoenix (AZ) area.

OpenVMS enthusiast, ISO 8601 evangelist, photographer, opinionated SOB, acknowledged pedant and contrarian

---------------

"I would be looking for better tekkies, too. Yours are broken." -- Paul Pedant

"Using fewer technologies is better than using more." -- Rico Mariani

"Good code is its own best documentation. As you’re about to add a comment, ask yourself, ‘How can I improve the code so that this comment isn’t needed?’" -- Steve McConnell

"Every time you write a comment, you should grimace and feel the failure of your ability of expression." -- Unknown

"If you need help knowing what to think, let me know and I'll tell you." -- Jeffrey Snover [MSFT]

"Typing is no substitute for thinking." -- R.W. Hamming

"I find it appalling that you can become a programmer with less training than it takes to become a plumber." -- Bjarne Stroustrup

ZagNut’s Law: Arrogance is inversely proportional to ability.

"Well blow me sideways with a plastic marionette. I've just learned something new - and if I could award you a 100 for that post I would. Way to go you keyboard lovegod you." -- Pete O'Hanlon

"linq'ish" sounds like "inept" in German -- Andreas Gieriet

"Things would be different if I ran the zoo." -- Dr. Seuss

"Wrong is evil, and it must be defeated." –- Jeff Ello

"A good designer must rely on experience, on precise, logical thinking, and on pedantic exactness." -- Nigel Shaw

“It’s always easier to do it the hard way.” -- Blackhart

“If Unix wasn’t so bad that you can’t give it away, Bill Gates would never have succeeded in selling Windows.” -- Blackhart

"Use vertical and horizontal whitespace generously. Generally, all binary operators except '.' and '->' should be separated from their operands by blanks."

"Omit needless local variables." -- Strunk... had he taught programming

Comments and Discussions

 
GeneralMy vote of 5 Pin
Kanasz Robert6-Nov-12 0:12
professionalKanasz Robert6-Nov-12 0:12 
GeneralRe: My vote of 5 Pin
PIEBALDconsult6-Nov-12 14:24
mvePIEBALDconsult6-Nov-12 14:24 
GeneralExcellent article Pin
Lee N Middleton12-Jan-11 10:14
Lee N Middleton12-Jan-11 10:14 
GeneralRe: Excellent article Pin
PIEBALDconsult13-Jan-11 1:23
mvePIEBALDconsult13-Jan-11 1:23 
GeneralRe: Excellent article Pin
Lee N Middleton19-Jan-11 12:21
Lee N Middleton19-Jan-11 12:21 
GeneralRe: Excellent article Pin
PIEBALDconsult19-Jan-11 18:55
mvePIEBALDconsult19-Jan-11 18:55 
GeneralA use case Pin
dave.dolan23-Dec-10 4:09
dave.dolan23-Dec-10 4:09 
GeneralRe: A use case Pin
PIEBALDconsult23-Dec-10 4:36
mvePIEBALDconsult23-Dec-10 4:36 
Generalsweet!! Pin
KenJohnson22-Dec-10 23:44
KenJohnson22-Dec-10 23:44 
Most excellent,
I've been thinking about doing something like this for use with testing but thankfully you beat me to it and saving me time is always greatly appreciated. Unfortunatly there was no supplied performance data. I will let you know when I have some. (you wouldn't have the recursive equivalent lying around, would you)
Thanks again
Ken
GeneralRe: sweet!! Pin
PIEBALDconsult23-Dec-10 4:33
mvePIEBALDconsult23-Dec-10 4:33 
GeneralMy vote of 5 Pin
RaviRanjanKr22-Dec-10 18:10
professionalRaviRanjanKr22-Dec-10 18:10 
GeneralRe: My vote of 5 Pin
PIEBALDconsult23-Dec-10 4:31
mvePIEBALDconsult23-Dec-10 4:31 
GeneralWOWZA... Pin
SledgeHammer0122-Dec-10 12:03
SledgeHammer0122-Dec-10 12:03 
GeneralRe: WOWZA... Pin
PIEBALDconsult22-Dec-10 14:34
mvePIEBALDconsult22-Dec-10 14:34 
GeneralRe: WOWZA... Pin
HaBiX22-Dec-10 20:53
HaBiX22-Dec-10 20:53 
GeneralRe: WOWZA... Pin
Toli Cuturicu23-Dec-10 13:39
Toli Cuturicu23-Dec-10 13:39 
GeneralRe: WOWZA... Pin
PIEBALDconsult23-Dec-10 15:29
mvePIEBALDconsult23-Dec-10 15:29 
GeneralRe: WOWZA... Pin
SledgeHammer0125-Dec-10 9:54
SledgeHammer0125-Dec-10 9:54 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.