Posted on by Kalkicode
Code Probability

Generate all 0 and 1 with 25% and 75% probability

Binary sequences consisting of 0s and 1s are essential in various fields, such as computer science, mathematics, and information theory. In some cases, it becomes necessary to generate balanced binary sequences with specific probabilities for 0s and 1s. This article explores a C program that generates such sequences with a 25% probability for 0s and a 75% probability for 1s. We will dive into the problem statement, explain the provided code, and discuss how it achieves the desired outcome. So, let's explore the fascinating world of balanced binary sequence generation.

Understanding the Problem Statement:

The problem at hand is to generate binary sequences where the probability of encountering a 0 is 25%, and the probability of encountering a 1 is 75%. The code provided uses a recursive approach to generate these sequences efficiently. Let's break down the code and understand how it accomplishes the task.

Code Solution

// C Program
   // Generate all 0 and 1 with 25% and 75% probability
   #include <stdio.h>
   
   void balancedBinary(char result[], int k, 
                         int zero, int one, int index)
   {
       if (zero > k || one > k *3)
       {
           return;
       }
       if (index == k *4)
       {
           printf("%s\n", result);
           return;
       }
       result[index] = '0';
       balancedBinary(result, k, zero + 1, one, index + 1);
       result[index] = '1';
       balancedBinary(result, k, zero, one + 1, index + 1);
   }
   void findSolution(int n)
   {
       if (n <= 0)
       {
           return;
       }
       if (n < 4)
       {
           // When only 1s
           for (int i = 0; i < n; ++i)
           {
               printf("  1");
           }
           return;
       }
       char result[n + 1];
       // set the value of last char is to terminating character
       result[n - 1] = '\0';
       balancedBinary(result, n / 4, 0, 0, 0);
   }
   int main()
   {
       int n = 8;
       // Example
       // n = 8
       // k = n / 4    [8/4 = 2 (two 0s)] (25 % 0s)
       // k *3        [2*3 = 6 (six 1s)] (75 % 1s)
       findSolution(n);
       return 0;
   }

Output

00111111
   01011111
   01101111
   01110111
   01111011
   01111101
   01111110
   10011111
   10101111
   10110111
   10111011
   10111101
   10111110
   11001111
   11010111
   11011011
   11011101
   11011110
   11100111
   11101011
   11101101
   11101110
   11110011
   11110101
   11110110
   11111001
   11111010
   11111100
// Java program for
   // Generate all 0 and 1 with 25% and 75% probability
   public class Combination
   {
       public void balancedBinary(String result, 
                                   int k, int zero, 
                                   int one, int index)
       {
           if (zero > k || one > k * 3)
           {
               return;
           }
           if (index == k * 4)
           {
               System.out.println(result);
               return;
           }
           balancedBinary(result + "0", k, 
                          zero + 1, one, index + 1);
           balancedBinary(result + "1", k, 
                          zero, one + 1, index + 1);
       }
       public void findSolution(int n)
       {
           if (n <= 0)
           {
               return;
           }
           if (n < 4)
           {
               // When only 1s
               for (int i = 0; i < n; ++i)
               {
                   System.out.print(" 1");
               }
               return;
           }
           balancedBinary("", n / 4, 0, 0, 0);
       }
       public static void main(String[] args)
       {
           Combination task = new Combination();
           int n = 8;
           // Example
           // n = 8
           // k = n / 4    [8/4 = 2 (two 0s)] (25 % 0s)
           // k *3        [2*3 = 6 (six 1s)] (75 % 1s)
           task.findSolution(n);
       }
   }

Output

00111111
   01011111
   01101111
   01110111
   01111011
   01111101
   01111110
   10011111
   10101111
   10110111
   10111011
   10111101
   10111110
   11001111
   11010111
   11011011
   11011101
   11011110
   11100111
   11101011
   11101101
   11101110
   11110011
   11110101
   11110110
   11111001
   11111010
   11111100
// Include header file
   #include <iostream>
   
   using namespace std;
   // C++ program for
   // Generate all 0 and 1 with 25% and 75% probability
   class Combination
   {
       public: void balancedBinary(string result, 
                                   int k, int zero, 
                                   int one, int index)
       {
           if (zero > k || one > k *3)
           {
               return;
           }
           if (index == k *4)
           {
               cout << result << endl;
               return;
           }
           this->balancedBinary(result  +  "0", 
                                k, zero + 1, one, index + 1);
           this->balancedBinary(result  +  "1", 
                                k, zero, one + 1, index + 1);
       }
       void findSolution(int n)
       {
           if (n <= 0)
           {
               return;
           }
           if (n < 4)
           {
               // When only 1s
               for (int i = 0; i < n; ++i)
               {
                   cout << " 1";
               }
               return;
           }
           this->balancedBinary("", n / 4, 0, 0, 0);
       }
   };
   int main()
   {
       Combination *task = new Combination();
       int n = 8;
       // Example
       // n = 8
       // k = n / 4    [8/4 = 2 (two 0s)] (25 % 0s)
       // k *3        [2*3 = 6 (six 1s)] (75 % 1s)
       task->findSolution(n);
       return 0;
   }

Output

00111111
   01011111
   01101111
   01110111
   01111011
   01111101
   01111110
   10011111
   10101111
   10110111
   10111011
   10111101
   10111110
   11001111
   11010111
   11011011
   11011101
   11011110
   11100111
   11101011
   11101101
   11101110
   11110011
   11110101
   11110110
   11111001
   11111010
   11111100
// Include namespace system
   using System;
   // Csharp program for
   // Generate all 0 and 1 with 25% and 75% probability
   public class Combination
   {
       public void balancedBinary(String result, 
                                   int k, int zero, int one, int index)
       {
           if (zero > k || one > k * 3)
           {
               return;
           }
           if (index == k * 4)
           {
               Console.WriteLine(result);
               return;
           }
           this.balancedBinary(result + "0", k, 
                               zero + 1, one, index + 1);
           this.balancedBinary(result + "1", k, 
                               zero, one + 1, index + 1);
       }
       public void findSolution(int n)
       {
           if (n <= 0)
           {
               return;
           }
           if (n < 4)
           {
               // When only 1s
               for (int i = 0; i < n; ++i)
               {
                   Console.Write(" 1");
               }
               return;
           }
           this.balancedBinary("", n / 4, 0, 0, 0);
       }
       public static void Main(String[] args)
       {
           Combination task = new Combination();
           int n = 8;
           // Example
           // n = 8
           // k = n / 4    [8/4 = 2 (two 0s)] (25 % 0s)
           // k *3        [2*3 = 6 (six 1s)] (75 % 1s)
           task.findSolution(n);
       }
   }

Output

00111111
   01011111
   01101111
   01110111
   01111011
   01111101
   01111110
   10011111
   10101111
   10110111
   10111011
   10111101
   10111110
   11001111
   11010111
   11011011
   11011101
   11011110
   11100111
   11101011
   11101101
   11101110
   11110011
   11110101
   11110110
   11111001
   11111010
   11111100
package main
   import "fmt"
   // Go program for
   // Generate all 0 and 1 with 25% and 75% probability
   type Combination struct {}
   func getCombination() * Combination {
       var me *Combination = &Combination {}
       return me
   }
   func(this Combination) balancedBinary(result string, 
                                         k int, zero int, 
                                         one int, index int) {
       if zero > k || one > k * 3 {
           return
       }
       if index == k * 4 {
           fmt.Println(result)
           return
       }
       this.balancedBinary(result + "0", 
           k, zero + 1, one, index + 1)
       this.balancedBinary(result + "1", 
           k, zero, one + 1, index + 1)
   }
   func(this Combination) findSolution(n int) {
       if n <= 0 {
           return
       }
       if n < 4 {
           // When only 1s
           for i := 0 ; i < n ; i++ {
               fmt.Print(" 1")
           }
           return
       }
       this.balancedBinary("", n / 4, 0, 0, 0)
   }
   func main() {
       var task * Combination = getCombination()
       var n int = 8
       // Example
       // n = 8
       // k = n / 4    [8/4 = 2 (two 0s)] (25 % 0s)
       // k *3        [2*3 = 6 (six 1s)] (75 % 1s)
       task.findSolution(n)
   }

Output

00111111
   01011111
   01101111
   01110111
   01111011
   01111101
   01111110
   10011111
   10101111
   10110111
   10111011
   10111101
   10111110
   11001111
   11010111
   11011011
   11011101
   11011110
   11100111
   11101011
   11101101
   11101110
   11110011
   11110101
   11110110
   11111001
   11111010
   11111100
<?php
   // Php program for
   // Generate all 0 and 1 with 25% and 75% probability
   class Combination
   {
       public	function balancedBinary($result, $k, 
                                        $zero, $one, 
                                        $index)
       {
           if ($zero > $k || $one > $k * 3)
           {
               return;
           }
           if ($index == $k * 4)
           {
               echo($result.
                   "\n");
               return;
           }
           $this->balancedBinary($result.
               "0", $k, $zero + 1, $one, $index + 1);
           $this->balancedBinary($result.
               "1", $k, $zero, $one + 1, $index + 1);
       }
       public	function findSolution($n)
       {
           if ($n <= 0)
           {
               return;
           }
           if ($n < 4)
           {
               // When only 1s
               for ($i = 0; $i < $n; ++$i)
               {
                   echo(" 1");
               }
               return;
           }
           $this->balancedBinary("", (int)($n / 4), 0, 0, 0);
       }
   }
   
   function main()
   {
       $task = new Combination();
       $n = 8;
       // Example
       // n = 8
       // k = n / 4    [8/4 = 2 (two 0s)] (25 % 0s)
       // k *3        [2*3 = 6 (six 1s)] (75 % 1s)
       $task->findSolution($n);
   }
   main();

Output

00111111
   01011111
   01101111
   01110111
   01111011
   01111101
   01111110
   10011111
   10101111
   10110111
   10111011
   10111101
   10111110
   11001111
   11010111
   11011011
   11011101
   11011110
   11100111
   11101011
   11101101
   11101110
   11110011
   11110101
   11110110
   11111001
   11111010
   11111100
// Node JS program for
   // Generate all 0 and 1 with 25% and 75% probability
   class Combination
   {
       balancedBinary(result, k, zero, one, index)
       {
           if (zero > k || one > k * 3)
           {
               return;
           }
           if (index == k * 4)
           {
               console.log(result);
               return;
           }
           this.balancedBinary(result + "0", k, 
                               zero + 1, one, index + 1);
           this.balancedBinary(result + "1", k, 
                               zero, one + 1, index + 1);
       }
       findSolution(n)
       {
           if (n <= 0)
           {
               return;
           }
           if (n < 4)
           {
               // When only 1s
               for (var i = 0; i < n; ++i)
               {
                   process.stdout.write(" 1");
               }
               return;
           }
           this.balancedBinary("", parseInt(n / 4), 0, 0, 0);
       }
   }
   
   function main()
   {
       var task = new Combination();
       var n = 8;
       // Example
       // n = 8
       // k = n / 4    [8/4 = 2 (two 0s)] (25 % 0s)
       // k *3        [2*3 = 6 (six 1s)] (75 % 1s)
       task.findSolution(n);
   }
   main();

Output

00111111
   01011111
   01101111
   01110111
   01111011
   01111101
   01111110
   10011111
   10101111
   10110111
   10111011
   10111101
   10111110
   11001111
   11010111
   11011011
   11011101
   11011110
   11100111
   11101011
   11101101
   11101110
   11110011
   11110101
   11110110
   11111001
   11111010
   11111100
#  Python 3 program for
   #  Generate all 0 and 1 with 25% and 75% probability
   class Combination :
       def balancedBinary(self, result, k, zero, one, index) :
           if (zero > k or one > k * 3) :
               return
           
           if (index == k * 4) :
               print(result)
               return
           
           self.balancedBinary(result + "0", k, 
                               zero + 1, one, index + 1)
           self.balancedBinary(result + "1", k, 
                               zero, one + 1, index + 1)
       
       def findSolution(self, n) :
           if (n <= 0) :
               return
           
           if (n < 4) :
               i = 0
               #  When only 1s
               while (i < n) :
                   print(" 1", end = "")
                   i += 1
               
               return
           
           self.balancedBinary("", int(n / 4), 0, 0, 0)
       
   
   def main() :
       task = Combination()
       n = 8
       #  Example
       #  n = 8
       #  k = n / 4    [8/4 = 2 (two 0s)] (25 % 0s)
       #  k *3        [2*3 = 6 (six 1s)] (75 % 1s)
       task.findSolution(n)
   
   if __name__ == "__main__": main()

Output

00111111
   01011111
   01101111
   01110111
   01111011
   01111101
   01111110
   10011111
   10101111
   10110111
   10111011
   10111101
   10111110
   11001111
   11010111
   11011011
   11011101
   11011110
   11100111
   11101011
   11101101
   11101110
   11110011
   11110101
   11110110
   11111001
   11111010
   11111100
#  Ruby program for
   #  Generate all 0 and 1 with 25% and 75% probability
   class Combination 
       def balancedBinary(result, k, zero, one, index) 
           if (zero > k || one > k * 3) 
               return
           end
   
           if (index == k * 4) 
               print(result, "\n")
               return
           end
   
           self.balancedBinary(result + "0", k, 
                               zero + 1, one, index + 1)
           self.balancedBinary(result + "1", k, 
                               zero, one + 1, index + 1)
       end
   
       def findSolution(n) 
           if (n <= 0) 
               return
           end
   
           if (n < 4) 
               i = 0
               #  When only 1s
               while (i < n) 
                   print(" 1")
                   i += 1
               end
   
               return
           end
   
           self.balancedBinary("", n / 4, 0, 0, 0)
       end
   
   end
   
   def main() 
       task = Combination.new()
       n = 8
       #  Example
       #  n = 8
       #  k = n / 4    [8/4 = 2 (two 0s)] (25 % 0s)
       #  k *3        [2*3 = 6 (six 1s)] (75 % 1s)
       task.findSolution(n)
   end
   
   main()

Output

00111111
   01011111
   01101111
   01110111
   01111011
   01111101
   01111110
   10011111
   10101111
   10110111
   10111011
   10111101
   10111110
   11001111
   11010111
   11011011
   11011101
   11011110
   11100111
   11101011
   11101101
   11101110
   11110011
   11110101
   11110110
   11111001
   11111010
   11111100
   
// Scala program for
   // Generate all 0 and 1 with 25% and 75% probability
   class Combination()
   {
       def balancedBinary(result: String, k: Int, 
                          zero: Int, one: Int, index: Int): Unit = {
           if (zero > k || one > k * 3)
           {
               return;
           }
           if (index == k * 4)
           {
               println(result);
               return;
           }
           balancedBinary(result + "0", k, 
                          zero + 1, one, index + 1);
           balancedBinary(result + "1", k, 
                          zero, one + 1, index + 1);
       }
       def findSolution(n: Int): Unit = {
           if (n <= 0)
           {
               return;
           }
           if (n < 4)
           {
               var i: Int = 0;
               // When only 1s
               while (i < n)
               {
                   print(" 1");
                   i += 1;
               }
               return;
           }
           balancedBinary("", n / 4, 0, 0, 0);
       }
   }
   object Main
   {
       def main(args: Array[String]): Unit = {
           var task: Combination = new Combination();
           var n: Int = 8;
           // Example
           // n = 8
           // k = n / 4   [8/4 = 2 (two 0s)] (25 % 0s)
           // k *3        [2*3 = 6 (six 1s)] (75 % 1s)
           task.findSolution(n);
       }
   }

Output

00111111
   01011111
   01101111
   01110111
   01111011
   01111101
   01111110
   10011111
   10101111
   10110111
   10111011
   10111101
   10111110
   11001111
   11010111
   11011011
   11011101
   11011110
   11100111
   11101011
   11101101
   11101110
   11110011
   11110101
   11110110
   11111001
   11111010
   11111100
// Swift 4 program for
   // Generate all 0 and 1 with 25% and 75% probability
   class Combination
   {
       func balancedBinary(_ result: String, _ k: Int, 
                            _ zero: Int, _ one: Int, _ index: Int)
       {
           if (zero > k || one > k * 3)
           {
               return;
           }
           if (index == k * 4)
           {
               print(result);
               return;
           }
           self.balancedBinary(result + "0", k, 
                               zero + 1, one, index + 1);
           self.balancedBinary(result + "1", k, 
                               zero, one + 1, index + 1);
       }
       func findSolution(_ n: Int)
       {
           if (n <= 0)
           {
               return;
           }
           if (n < 4)
           {
               var i: Int = 0;
               // When only 1s
               while (i < n)
               {
                   print(" 1", terminator: "");
                   i += 1;
               }
               return;
           }
           self.balancedBinary("", n / 4, 0, 0, 0);
       }
   }
   func main()
   {
       let task: Combination = Combination();
       let n: Int = 8;
       // Example
       // n = 8
       // k = n / 4    [8/4 = 2 (two 0s)] (25 % 0s)
       // k *3        [2*3 = 6 (six 1s)] (75 % 1s)
       task.findSolution(n);
   }
   main();

Output

00111111
   01011111
   01101111
   01110111
   01111011
   01111101
   01111110
   10011111
   10101111
   10110111
   10111011
   10111101
   10111110
   11001111
   11010111
   11011011
   11011101
   11011110
   11100111
   11101011
   11101101
   11101110
   11110011
   11110101
   11110110
   11111001
   11111010
   11111100
// Kotlin program for
   // Generate all 0 and 1 with 25% and 75% probability
   class Combination
   {
       fun balancedBinary(result: String, k: Int, zero: Int, 
                           one: Int, index: Int): Unit
       {
           if (zero > k || one > k * 3)
           {
               return;
           }
           if (index == k * 4)
           {
               println(result);
               return;
           }
           this.balancedBinary(result + "0", k, zero + 1, one, index + 1);
           this.balancedBinary(result + "1", k, zero, one + 1, index + 1);
       }
       fun findSolution(n: Int): Unit
       {
           if (n <= 0)
           {
               return;
           }
           if (n < 4)
           {
               var i: Int = 0;
               // When only 1s
               while (i < n)
               {
                   print(" 1");
                   i += 1;
               }
               return;
           }
           this.balancedBinary("", n / 4, 0, 0, 0);
       }
   }
   fun main(args: Array < String > ): Unit
   {
       val task: Combination = Combination();
       val n: Int = 8;
       // Example
       // n = 8
       // k = n / 4    [8/4 = 2 (two 0s)] (25 % 0s)
       // k *3        [2*3 = 6 (six 1s)] (75 % 1s)
       task.findSolution(n);
   }

Output

00111111
   01011111
   01101111
   01110111
   01111011
   01111101
   01111110
   10011111
   10101111
   10110111
   10111011
   10111101
   10111110
   11001111
   11010111
   11011011
   11011101
   11011110
   11100111
   11101011
   11101101
   11101110
   11110011
   11110101
   11110110
   11111001
   11111010
   11111100

Understanding the Provided Code:

The code is written in the C programming language and consists of several functions to solve the problem. Here's an overview of the functions and their roles:

  1. balancedBinary: This recursive function generates the binary sequences using backtracking. It takes parameters like result[] (the current sequence being generated), k (a limit for the number of 0s in the sequence), zero (the count of 0s encountered so far), one (the count of 1s encountered so far), and index (the current index being processed in the sequence). The function checks the counts of 0s and 1s to ensure they are within the desired probability limits. If the counts exceed the limits, the function terminates. When the end of the sequence is reached (index == k * 4), the function prints the generated sequence. Otherwise, it continues the recursion by setting the current index as 0 or 1 and incrementing the counts accordingly.

  2. findSolution: This function acts as a driver function for generating the binary sequences. It takes the parameter n, which represents the desired length of the sequence. If n is less than or equal to 0, the function terminates. If n is less than 4, it simply prints the number of 1s equal to n. Otherwise, it initializes an array result[] with size n + 1 and sets the last character as the terminating character. It then calls the balancedBinary function with appropriate parameters to generate the binary sequences.

  3. main: The main function sets the value of n (sequence length) as 8, as an example. It calls the findSolution function to generate the binary sequences with the desired probabilities.

Explanation of the Output

The output of the program consists of various binary sequences that satisfy the given probability conditions. Each sequence is printed on a separate line. For example, the sequence "00111111" represents a sequence of length 8, where there are two 0s and six 1s, satisfying the 25% and 75% probability conditions, respectively. The program generates all possible valid sequences that adhere to these conditions.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment