Hello! Faced such a problem. I need to dynamically create an associative array, receiving from the user 1 parameter, a number, or rather the number of device classes. 3 class device. Each class can be implemented on a processor or on a chip, i.e. the value of class n can be 1 or 0. I need to get an array containing all possible combinations of the numbers 1 and 0 "long" n. I get the number n as an input, then I get the total number of possible combinations, 2 to the power n. I run a cycle in which I generate an element of the i-th row of the array (the 2-dimensional array should be)

$arr[$i]["Class".$j.""] = rand(0,1);

The variable $ j in my case takes values ​​from 1 to n inclusive. Those. OK class in iq line. In parallel with this, I write down the string variable "Key".

 $key .= $arr[$i]["Class".$j.""];

It will be required for comparison with an existing entry in the array. Those. for example, I got such a combination of classes {1; 0; 1} and the key will be equal to string (3) "101", and I will check it in a loop with other keys of the array and if it is NOT a match, write "simplex" in array At first, the logic seemed correct to me, but then I began to doubt. Because somehow I do not write correctly at the beginning of the classes, collect the key, compare the key, did not match - I write down, I match - I delete the classes that I wrote down before the comparison. Maybe someone has an idea for the implementation of such an algorithm?

The input is the number n (the number of classes), the output is such a matrix:

 class1|class2|class3|classn|Key| |1|0|1|..|n|101| ------------ |1|0|0|..|n|100| ------------ |0|0|0|..|n|000| ------------ |0|1|0|..|n|010|

.... etc.

however, strings or keys (since keys are "alias" strings) are unique. Thank you in advance!



    3 answers 3

    It seems that we need a function that returns an array with all combinations of ones and zeros of length N. That is, all possible numbers in a binary notation of N bits.

    For N <32 (<64 for 64-bit systems), you can β€œsort out” all the options:

     function allCombs( $n){ if( $n > PHP_INT_SIZE * 8) { echo '$n слишком Π΄Π»ΠΈΠ½Π½Π° для этого ΠΊΠΎΠΌΠΏΠ°'; return; } $result = array(); $max = 1 << $n; // максимум: $n Π΅Π΄ΠΈΠ½ΠΈΡ† $format = '%0' .$n. 'b'; for( $i=0; $i < $max; $i++){ $bin = sprintf( $format, $i); // строка ΠΈΠ· 0 ΠΈ 1 Π΄Π»ΠΈΠ½ΠΎΠΉ N $set = str_split( $bin); // массив ΠΈΠ· 1 ΠΈ 0 array_push( $set, $bin); // +послСдний элСмСнт строка-ΠΊΠ»ΡŽΡ‡ array_push( $result, $set); } return $result; }

    Output for N=3 :

     0, 0, 0, 000 0, 0, 1, 001 0, 1, 0, 010 0, 1, 1, 011 1, 0, 0, 100 1, 0, 1, 101 1, 1, 0, 110 1, 1, 1, 111

      As far as I understand, this is the task of finding all the subsets of a given source set. Simply, the initial set is given by setting the length.

      For example, the user enters the number 3, which means that the original set {1,2,3}. If the number is 5, then {1,2,3,4,5}.

      For example, for the set {1,2,3} the subsets will be {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}

      This problem is solved through the binary system. In a binary system, a number is created that is something like a mask of the occurrence of elements, for example, the first such number [001]. Then according to this mask {3} will be displayed in the subsets. Next, the unit is added to the mask and the output is repeated on it: [010] = {2}. As a result, he gets this:

       {1,2,3} * [001] = {3} {1,2,3} * [010] = {2} {1,2,3} * [011] = {2,3} {1,2,3} * [100] = {1} {1,2,3} * [101] = {1,3} {1,2,3} * [110] = {1,2} {1,2,3} * [111] = {1,2,3}

      How this should be implemented in your programming language, I think that you will come up with.

      • The TS is interested in a string of constant length, from all possible combinations of 1 and 0, it seems. It's simple, do not be distracted by more complex subsets of variable length) - Sergiks

      If I understand you correctly, then using rand in your case is absolutely wrong, in theory you can never get out of the loop.

      Google combinatorics