ابحث عن جميع مجموعات أرقام k-bit مع مجموعة n من البتات حيث 1 <= n <= k بترتيب مفروز
بالنظر إلى الرقم k، ابحث عن جميع المجموعات الممكنة لأرقام k-bit مع مجموعة n-bit حيث 1 <= n <= k. The solution should print all numbers with one set bit first followed by numbers with two bits set.. up to the numbers whose all k-bits are set. If two numbers have the same number of set bits then smaller number should come first. Examples:
Input: K = 3 Output: 001 010 100 011 101 110 111 Input: K = 4 Output: 0001 0010 0100 1000 0011 0101 0110 1001 1010 1100 0111 1011 1101 1110 1111 Input: K = 5 Output: 00001 00010 00100 01000 10000 00011 00101 00110 01001 01010 01100 10001 10010 10100 11000 00111 01011 01101 01110 10011 10101 10110 11001 11010 11100 01111 10111 11011 11101 11110 11111
نحتاج إلى العثور على جميع المجموعات الممكنة لأرقام k-bit مع مجموعة n من البتات حيث 1 <= n <= k. If we carefully analyze we see that problem can further be divided into sub-problems. We can find all combinations of length k with n ones by prefixing 0 to all combinations of length k-1 with n ones and 1 to all combinations of length k-1 with n-1 ones. We can use Dynamic Programming to save solutions of sub-problems. Below is C++ implementation of above idea –
C++ // C++ program find all the possible combinations of // k-bit numbers with n-bits set where 1 <= n <= k #include #include using namespace std ; // maximum allowed value of K #define K 16 // DP lookup table vector < string > DP [ K ][ K ]; // Function to find all combinations k-bit numbers with // n-bits set where 1 <= n <= k void findBitCombinations ( int k ) { string str = '' ; // DP[k][0] will store all k-bit numbers // with 0 bits set (All bits are 0's) for ( int len = 0 ; len <= k ; len ++ ) { DP [ len ][ 0 ]. push_back ( str ); str = str + '0' ; } // fill DP lookup table in bottom-up manner // DP[k][n] will store all k-bit numbers // with n-bits set for ( int len = 1 ; len <= k ; len ++ ) { for ( int n = 1 ; n <= len ; n ++ ) { // prefix 0 to all combinations of length len-1 // with n ones for ( string str : DP [ len - 1 ][ n ]) DP [ len ][ n ]. push_back ( '0' + str ); // prefix 1 to all combinations of length len-1 // with n-1 ones for ( string str : DP [ len - 1 ][ n - 1 ]) DP [ len ][ n ]. push_back ( '1' + str ); } } // print all k-bit binary strings with // n-bit set for ( int n = 1 ; n <= k ; n ++ ) { for ( string str : DP [ k ][ n ]) cout < < str < < ' ' ; cout < < endl ; } } // Driver code int main () { int k = 5 ; for ( int i = 0 ; i < k ; i ++ ) cout < < '0' ; cout < < endl ; findBitCombinations ( k ); return 0 ; }
Java // Java equivalent import java.util.ArrayList ; public class BitCombinations { // Function to find all combinations k-bit numbers with // n-bits set where 1 <= n <= k public static void findBitCombinations ( int k ) { // Array to store all the possible combinations ArrayList < ArrayList < String >> combinations = new ArrayList <> (); // Iterate over all possible values of n for ( int n = 1 ; n <= k ; n ++ ) { // Create an array to store the combinations for the current value of n ArrayList < String > currentCombination = new ArrayList <> (); // Generate all possible combinations with n bits set for ( int i = 0 ; i < Math . pow ( 2 k ); i ++ ) { String binaryString = Integer . toBinaryString ( i ); // Check if the current binary string has n bits set if (( binaryString . length () - binaryString . replace ( '1' '' ). length ()) == n ) { currentCombination . add ( String . format ( '%0' + k + 'd' Long . parseLong ( binaryString ))); } } // Add the current combinations to the main combinations array combinations . add ( currentCombination ); } System . out . println ( '00000' ); // Print all the combinations for ( int i = 0 ; i < combinations . size (); i ++ ) { System . out . println ( String . join ( ' ' combinations . get ( i ))); } } // Driver code public static void main ( String [] args ) { int k = 5 ; findBitCombinations ( k ); } }
Python3 # Python program to find all the possible combinations of # k-bit numbers with n-bits set where 1 <= n <= k # maximum allowed value of K K = 16 # DP lookup table DP = [[[] for _ in range ( K )] for _ in range ( K )] # Function to find all combinations k-bit numbers with # n-bits set where 1 <= n <= k def findBitCombinations ( k ): global DP # DP[k][0] will store all k-bit numbers # with 0 bits set (All bits are 0's) str = '' for len in range ( k + 1 ): DP [ len ][ 0 ] . append ( str ) str += '0' # fill DP lookup table in bottom-up manner # DP[k][n] will store all k-bit numbers # with n-bits set for len in range ( 1 k + 1 ): for n in range ( 1 len + 1 ): # prefix 0 to all combinations of length len-1 # with n ones for str in DP [ len - 1 ][ n ]: DP [ len ][ n ] . append ( '0' + str ) # prefix 1 to all combinations of length len-1 # with n-1 ones for str in DP [ len - 1 ][ n - 1 ]: DP [ len ][ n ] . append ( '1' + str ) # print all k-bit binary strings with # n-bit set for n in range ( k + 1 ): for str in DP [ k ][ n ]: print ( str end = ' ' ) print () # Driver code k = 5 findBitCombinations ( k ) #Contributed by Aditya Sharma
C# using System ; using System.Collections.Generic ; public class BitCombinations { // Function to find all combinations k-bit numbers with // n-bits set where 1 <= n <= k public static void findBitCombinations ( int k ) { // Array to store all the possible combinations List < List < string >> combinations = new List < List < string >> (); // Iterate over all possible values of n for ( int n = 1 ; n <= k ; n ++ ) { // Create a list to store the combinations for the current value of n List < string > currentCombination = new List < string > (); // Generate all possible combinations with n bits set for ( int i = 0 ; i < Math . Pow ( 2 k ); i ++ ) { string binaryString = Convert . ToString ( i 2 ). PadLeft ( k '0' ); // Check if the current binary string has n bits set if (( binaryString . Length - binaryString . Replace ( '1' '' ). Length ) == n ) { currentCombination . Add ( binaryString ); } } // Add the current combinations to the main combinations list combinations . Add ( currentCombination ); } // Print '00000' Console . WriteLine ( '00000' ); // Print all the combinations foreach ( List < string > combination in combinations ) { Console . WriteLine ( string . Join ( ' ' combination )); } } // Driver code public static void Main ( string [] args ) { int k = 5 ; findBitCombinations ( k ); } }
JavaScript // Function to find all combinations k-bit numbers with // n-bits set where 1 <= n <= k function findBitCombinations ( k ) { // Array to store all the possible combinations const combinations = []; // Iterate over all possible values of n for ( let n = 1 ; n <= k ; n ++ ) { // Create an array to store the combinations for the current value of n const currentCombination = []; // Generate all possible combinations with n bits set for ( let i = 0 ; i < Math . pow ( 2 k ); i ++ ) { const binaryString = ( i ). toString ( 2 ); // Check if the current binary string has n bits set if (( binaryString . match ( /1/g ) || []). length === n ) { currentCombination . push ( binaryString . padStart ( k '0' )); } } // Add the current combinations to the main combinations array combinations . push ( currentCombination ); } let curr = '' for ( let i = 0 ; i < k ; i ++ ) curr = curr + '0' console . log ( curr ) // Print all the combinations for ( let i = 0 ; i < combinations . length ; i ++ ) { console . log ( combinations [ i ]. join ( ' ' )); console . log (); } } // Driver code const k = 5 ; findBitCombinations ( k );
الإخراج
00000 00001 00010 00100 01000 10000 00011 00101 00110 01001 01010 01100 10001 10010 10100 11000 00111 01011 01101 01110 10011 10101 10110 11001 11010 11100 01111 10111 11011 11101 11110 11111
