Software Programming

Kunuk Nykjaer

K-permutations of n objects – C# example

with 2 comments


I think permutation is a fun subject and decided to implement a C# example.

What is permutation? http://en.wikipedia.org/wiki/Permutation

This is a good source to read if you are interested in permutation creation using C# http://msdn.microsoft.com/en-us/library/aa302371.aspx.

Program.cs

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

/// <summary>
/// Author: Kunuk Nykjaer
/// </summary>
class Program
{
    static void Main(string[] args)
    {
        var S = new[] { "A", "B", "C" };

        Console.WriteLine("* BitMapping.SubsetSelection");
        BitMapping.SubsetSelection(S);
        
        Console.WriteLine("\n* Permute.SubsetSelection - len: all, no permutation");
        Permute.SubsetSelection(S,null,false);

        Console.WriteLine("\n* Permute.SubsetSelection - len: 2, with permutation");
        Permute.SubsetSelection(S, 2, true);

        Console.WriteLine("\n* Permute.SubsetSelection - len: 2, no permutation");
        Permute.SubsetSelection(S, 2, false);

        Console.Write("press a key to exit..\n"); Console.ReadKey();
    }

    static class Permute
    {
        public static void SubsetSelection(IEnumerable<string> S, int? n, 
                                            bool allowPermutation)
        {
            var result = new List<string>();
            M(S.ToList(), "", result, n, allowPermutation);

            foreach (string s in result)
            {
                Console.WriteLine(s);
            }                
            Console.WriteLine("Count: {0}", result.Count);
        }
        static void M(List<string> S, string s, List<string> result, int? n, 
                       bool allowPermutation)
        {
            for (int i = 0; i < S.Count; i++)
            {
                bool allowPermutationTest = allowPermutation 
                    ||  !(s.Length > 0 && s[s.Length - 1] > S[i][0]);

                if(!allowPermutationTest) continue;

                string head = s + S[i];
                var tail = new List<string>();
                tail.AddRange(S);
                tail.RemoveAt(i);

                if (n==null || head.Length == n)
                {
                    result.Add(string.Format("{0}", head));
                }
                    
                M(tail, head, result, n, allowPermutation);
            }
        }
    }

    static class BitMapping
    {
        public static void ShowBitMaps(int n)
        {
            var list = GenerateAllBitMappings(n);
            foreach (string s in list) Console.WriteLine(s);            
        }
        public static void SubsetSelection(string[] S)
        {
            PrintAllCombinations(S);            
        }

        // Implemented with Inspiration from a source code seen on the Internet
        static string GetNexBitMapping(string str)
        {
            int p0 = str.LastIndexOf('0');
            if (p0 == -1) return string.Empty;
            int len = str.Length;
            str = str.Substring(0, p0) + "1";
            str = str.PadRight(len, '0');
            return str;
        }

        static List<string> GenerateAllBitMappings(int len)
        {
            var list = new List<string>();
            string bitMapping = "1".PadLeft(len, '0');
            list.Add(bitMapping);
            while (bitMapping != string.Empty)
            {
                bitMapping = GetNexBitMapping(bitMapping);
                if(bitMapping!=string.Empty)
                {
                    list.Add(bitMapping);
                }                    
            }
            return list;
        }

        static void PrintAllCombinations(string[] data)
        {
            var allBitMappings = GenerateAllBitMappings(data.Length);
            foreach (string bitMapping in allBitMappings)
            {
                for (int i = 0; i < data.Length; i++)
                {
                    if (bitMapping[i] == '1') Console.Write(data[i]);                    
                }
                Console.WriteLine();
            }
            Console.WriteLine("Count: {0}", allBitMappings.Count);
        }
    }
}


Input string: S = {"A", "B", "C"}

Result:
* BitMapping.SubsetSelection
C
B
BC
A
AC
AB
ABC
Count: 7

* Permute.SubsetSelection - len: all, no permutation
A
AB
ABC
AC
B
BC
C
Count: 7

* Permute.SubsetSelection - len: 2, with permutation
AB
AC
BA
BC
CA
CB
Count: 6

* Permute.SubsetSelection - len: 2, no permutation
AB
AC
BC
Count: 3

Advertisements

Written by kunuk Nykjaer

June 6, 2012 at 2:07 pm

2 Responses

Subscribe to comments with RSS.

  1. Hello just wanted to give you a quick heads up. The text
    in your article seem to be running off the screen
    in Opera. I’m not sure if this is a format issue or something to do with browser compatibility but I figured I’d
    post to let you know. The design look great
    though! Hope you get the issue solved soon. Kudos

    water damage clean-up

    January 12, 2013 at 2:10 pm

  2. Exactly what I needed.

    Joshua Jebadurai

    March 21, 2014 at 4:30 am


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: