Finding permutations in strings

In C++ the Standard Template Library provides us with std::next_permutation to easily implement this.

#include <iostream>
#include <algorithm>
#include <iterator>
#include <string.h>
  
int main()
{
    char str[] = "abcd";
    const size_t len = strlen( str );
  
    do
    {
        std::copy( str,
        str + len,
        std::ostream_iterator<char>( std::cout ) );
        std::cout << std::endl;
    }
    while ( std::next_permutation( str, str + len ) );

	return 0;
}


Giving the following output:

permutations1

The C# / .NET framework does not have an equivalent for std::next_permutation, but is straightforward enough to implement:

This following StackOverflow post gives an excellent C# implementation of next_permutation, which I’ve used here:

https://stackoverflow.com/questions/2390954/how-would-you-calculate-all-possible-permutations-of-0-through-n-iteratively/12768718#12768718

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

namespace permutations_cs
{
    class Program
    {
        static bool next_permutation<T>(IList<T> a) where T : IComparable
        {
            if (a.Count < 2) return false;
            var k = a.Count - 2;

            while (k >= 0 && a[k].CompareTo(a[k + 1]) >= 0) k--;
            if (k < 0) return false;

            var l = a.Count - 1;
            while (l > k && a[l].CompareTo(a[k]) <= 0) l--;

            var tmp = a[k];
            a[k] = a[l];
            a[l] = tmp;

            var i = k + 1;
            var j = a.Count - 1;
            while (i < j)
            {
                tmp = a[i];
                a[i] = a[j];
                a[j] = tmp;
                i++;
                j--;
            }

            return true;
        }

        static void Main(string[] args)
        {
            char[] str = { 'a', 'b', 'c', 'd' };     

            do
            {
                Console.WriteLine(str);
            }
            while ( next_permutation( str ) );
        }
    }
}

Giving an identical output:

permutations2

Leave a Reply