For $n=5$, I have $32$ binary digits and for this there are $2^{32}$ combinations. Out of this many, the interesting ones (i.e., the ones that have monotone increasing binary digits) are only about "$2111$". I know how these can be found very easily but I am missing Mathematica knowledge. Therefore I cannot complete my program.
First I need to seperate these $32$ bits according to Pascals triangle numbers. Since $n=5$, these numbers are $1,5,10,10,5,1$. Their sum is $32$ and I separate the digits accordingly. My list is as follows:
List={
{0|00000|0000000000|0000000000|00000|0}
... those who satisfy the rule below
{1|11111|1111111111|1111111111|11111|1}}
From right to the left I start with the 5 bits and take all possible combinations:
|00000|--> 00001,00010,00011...11111
This says I have the following ones in the list
{0|00000|0000000000|0000000000|00001|1,
0|00000|0000000000|0000000000|00010|1,
0|00000|0000000000|0000000000|00011|1,...,
0|00000|0000000000|0000000000|11111|1}
Then I go left via keeping |11111|1 as fixed. Now I have $10$ digits and the following are the elements of the list
{0|00000|0000000000|0000000001|11111|1,
0|00000|0000000000|0000000010|11111|1,
0|00000|0000000000|0000000011|11111|1,...,
0|00000|0000000000|1111111111|11111|1}
Then, I do the same thing again but fixing |1111111111|11111|1. Then the followings are the elements of the set:
{0|00000|0000000000|1111111111|11111|1,
0|00000|0000000001|1111111111|11111|1,
0|00000|0000000010|1111111111|11111|1,...,
0|00000|1111111111|1111111111|11111|1}
Again the same thing and we are done:
{0|00001|1111111111|1111111111|11111|1,
0|00010|1111111111|1111111111|11111|1,
0|00011|1111111111|1111111111|11111|1,...,
0|11111|1111111111|1111111111|11111|1}
So in total there are $2^5$ numbers from the first stage, From the other two stages we have $2^{10}-1$ for each and for the last stage $2^5-1$ numbers. We also have all zeros and all ones and if I calculated correctly there are $2111$ of them. I used the character "|" for separation. The final list should look like
List={{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},....,{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}}
I only have the following code part:
IntegerDigits[2, 2, 5]
{0, 0, 0, 1, 0}
IntegerDigits[2, 2, 10]
{0, 0, 0, 0, 0, 0, 0, 0, 1, 0}
Using this code in a 'for loop' I can obtain such combinations but I must concatenate these to the previous bits which are all zeros and all subsequent bits which are all 1s. This is what I don't know how to do.
Answer
One idea is to make use of Tuples
:
monotoneTuples[b_, m_, e_] := Rest @ Tuples@Join[
ConstantArray[{0}, b],
ConstantArray[{0,1}, m],
ConstantArray[{1}, e]
]
monotoneTuples
will create your partitioned set. For example:
Column @ monotoneTuples[5, 3, 1] //TeXForm
$\begin{array}{l} \{0,0,0,0,0,0,0,1,1\} \\ \{0,0,0,0,0,0,1,0,1\} \\ \{0,0,0,0,0,0,1,1,1\} \\ \{0,0,0,0,0,1,0,0,1\} \\ \{0,0,0,0,0,1,0,1,1\} \\ \{0,0,0,0,0,1,1,0,1\} \\ \{0,0,0,0,0,1,1,1,1\} \\ \end{array}$
Then, you can join each of these sets:
res = Join[
monotoneTuples[31,1,0],
monotoneTuples[26,5,1],
monotoneTuples[16,10,6],
monotoneTuples[6,10,16],
monotoneTuples[1,5,26],
monotoneTuples[0,1,31]
];
res //Length
2110
Addendum
For memory reasons, it makes sense to create a list of integers instead of a list of bit vectors, especially if you will be creating a lot of them. So, an alternative is:
monotoneIntegers[list_] := With[{a = Accumulate[Prepend[0] @ Most @ Reverse @ list]},
Prepend[0][Join @@ (Range[2, 2^Reverse@list] 2^a - 1)]
]
For example, compare:
integers = monotoneIntegers[{1,3,2}]
bitvectors = IntegerDigits[%, 2, 6]
{0, 1, 2, 3, 7, 11, 15, 19, 23, 27, 31, 63}
{{0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 1}, {0, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 1, 1}, {0, 0, 0, 1, 1, 1}, {0, 0, 1, 0, 1, 1}, {0, 0, 1, 1, 1, 1}, {0, 1, 0, 0, 1, 1}, {0, 1, 0, 1, 1, 1}, {0, 1, 1, 0, 1, 1}, {0, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1}}
The memory usage of the integers is much less:
ByteCount @ integers
ByteCount @ bitvectors
200
1968
and the disparity increases with more bits.
Comments
Post a Comment