C# – Permutations of a given set of numbers

Here is a very good article regarding the Mutex solution. The approach described by the article is advantageous for two reasons.

First, it does not require a dependency on the Microsoft.VisualBasic assembly. If my project already had a dependency on that assembly, I would probably advocate using the approach shown in another answer. But as it is, I do not use the Microsoft.VisualBasic assembly, and I'd rather not add an unnecessary dependency to my project.

Second, the article shows how to bring the existing instance of the application to the foreground when the user tries to start another instance. That's a very nice touch that the other Mutex solutions described here do not address.

UPDATE

As of 8/1/2014, the article I linked to above is still active, but the blog hasn't been updated in a while. That makes me worry that eventually it might disappear, and with it, the advocated solution. I'm reproducing the content of the article here for posterity. The words belong solely to the blog owner at Sanity Free Coding.

Today I wanted to refactor some code that prohibited my application from running multiple instances of itself.

Previously I had use System.Diagnostics.Process to search for an instance of my myapp.exe in the process list. While this works, it brings on a lot of overhead, and I wanted something cleaner.

Knowing that I could use a mutex for this (but never having done it before) I set out to cut down my code and simplify my life.

In the class of my application main I created a static named Mutex:

static class Program
{
    static Mutex mutex = new Mutex(true, "{8F6F0AC4-B9A1-45fd-A8CF-72F04E6BDE8F}");
    [STAThread]
    ...
}

Having a named mutex allows us to stack synchronization across multiple threads and processes which is just the magic I'm looking for.

Mutex.WaitOne has an overload that specifies an amount of time for us to wait. Since we're not actually wanting to synchronizing our code (more just check if it is currently in use) we use the overload with two parameters: Mutex.WaitOne(Timespan timeout, bool exitContext). Wait one returns true if it is able to enter, and false if it wasn't. In this case, we don't want to wait at all; If our mutex is being used, skip it, and move on, so we pass in TimeSpan.Zero (wait 0 milliseconds), and set the exitContext to true so we can exit the synchronization context before we try to aquire a lock on it. Using this, we wrap our Application.Run code inside something like this:

static class Program
{
    static Mutex mutex = new Mutex(true, "{8F6F0AC4-B9A1-45fd-A8CF-72F04E6BDE8F}");
    [STAThread]
    static void Main() {
        if(mutex.WaitOne(TimeSpan.Zero, true)) {
            Application.EnableVisualStyles();
            Application.SetCompatibleTextRenderingDefault(false);
            Application.Run(new Form1());
            mutex.ReleaseMutex();
        } else {
            MessageBox.Show("only one instance at a time");
        }
    }
}

So, if our app is running, WaitOne will return false, and we'll get a message box.

Instead of showing a message box, I opted to utilize a little Win32 to notify my running instance that someone forgot that it was already running (by bringing itself to the top of all the other windows). To achieve this I used PostMessage to broadcast a custom message to every window (the custom message was registered with RegisterWindowMessage by my running application, which means only my application knows what it is) then my second instance exits. The running application instance would receive that notification and process it. In order to do that, I overrode WndProc in my main form and listened for my custom notification. When I received that notification I set the form's TopMost property to true to bring it up on top.

Here is what I ended up with:

• Program.cs

static class Program
{
    static Mutex mutex = new Mutex(true, "{8F6F0AC4-B9A1-45fd-A8CF-72F04E6BDE8F}");
    [STAThread]
    static void Main() {
        if(mutex.WaitOne(TimeSpan.Zero, true)) {
            Application.EnableVisualStyles();
            Application.SetCompatibleTextRenderingDefault(false);
            Application.Run(new Form1());
            mutex.ReleaseMutex();
        } else {
            // send our Win32 message to make the currently running instance
            // jump on top of all the other windows
            NativeMethods.PostMessage(
                (IntPtr)NativeMethods.HWND_BROADCAST,
                NativeMethods.WM_SHOWME,
                IntPtr.Zero,
                IntPtr.Zero);
        }
    }
}

• NativeMethods.cs

// this class just wraps some Win32 stuff that we're going to use
internal class NativeMethods
{
    public const int HWND_BROADCAST = 0xffff;
    public static readonly int WM_SHOWME = RegisterWindowMessage("WM_SHOWME");
    [DllImport("user32")]
    public static extern bool PostMessage(IntPtr hwnd, int msg, IntPtr wparam, IntPtr lparam);
    [DllImport("user32")]
    public static extern int RegisterWindowMessage(string message);
}

• Form1.cs (front side partial)

public partial class Form1 : Form
{
    public Form1()
    {
        InitializeComponent();
    }
    protected override void WndProc(ref Message m)
    {
        if(m.Msg == NativeMethods.WM_SHOWME) {
            ShowMe();
        }
        base.WndProc(ref m);
    }
    private void ShowMe()
    {
        if(WindowState == FormWindowState.Minimized) {
            WindowState = FormWindowState.Normal;
        }
        // get our current "TopMost" value (ours will always be false though)
        bool top = TopMost;
        // make our form jump to the top of everything
        TopMost = true;
        // set it back to whatever it was
        TopMost = top;
    }
}

There's a function in the standard-library for this: itertools.permutations.

import itertools
list(itertools.permutations([1, 2, 3]))

If for some reason you want to implement it yourself or are just curious to know how it works, here's one nice approach, taken from http://code.activestate.com/recipes/252178/:

def all_perms(elements):
    if len(elements) <=1:
        yield elements
    else:
        for perm in all_perms(elements[1:]):
            for i in range(len(elements)):
                # nb elements[0:1] works in both string and list contexts
                yield perm[:i] + elements[0:1] + perm[i:]

A couple of alternative approaches are listed in the documentation of itertools.permutations. Here's one:

def permutations(iterable, r=None):
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = range(n)
    cycles = range(n, n-r, -1)
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return

And another, based on itertools.product:

def permutations(iterable, r=None):
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    for indices in product(range(n), repeat=r):
        if len(set(indices)) == r:
            yield tuple(pool[i] for i in indices)