Permutation with number of 1s greater than or equal to number of 0s

Given a binary array containing 0s and 1s, print all the permutations of a specified length such that for any index position the number of 1s encountered is always greater than or equal to the number of 0s encountered from starting index.

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

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int numberOfOnes = 4;
            int numberOfZeroes = 4;
            int length = 8;
            GeneratePermutation(numberOfOnes, numberOfZeroes, 0, 0, length, "");
        }
        
        public static void GeneratePermutation(int numberOfOnesRemaining, int numberOfZeroesRemaining, int numberOfOnesUsed, int numberOfZeroesUsed, int length, string str)
        {
            if (str.Length == length)
            {
                Console.WriteLine(str);
                return;
            }
            
            if (numberOfOnesRemaining > 0)
            {
                GeneratePermutation(numberOfOnesRemaining - 1, numberOfZeroesRemaining, numberOfOnesUsed + 1, numberOfZeroesUsed, length, str + "1");
            }
            
            if (numberOfZeroesRemaining > 0 && numberOfOnesUsed > numberOfZeroesUsed)
            {
                GeneratePermutation(numberOfOnesRemaining, numberOfZeroesRemaining - 1, numberOfOnesUsed, numberOfZeroesUsed + 1, length, str + "0");
            }
        }
    }
}

Output
=======
11110000
11101000
11100100
11100010
11011000
11010100
11010010
11001100
11001010
10111000
10110100
10110010
10101100
10101010
Press any key to continue . . .
Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

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