2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ thats really an excellent way. Just the all zero sequence is missing. then the total number will be also $2111$. $\endgroup$ – Seyhmus Güngören Sep 22 '18 at 23:11
  • $\begingroup$ monotoneTuples[0, 31, 1] this is killing my mathematica) $\endgroup$ – Seyhmus Güngören Sep 23 '18 at 22:04
  • 2
    $\begingroup$ @SeyhmusGüngören It takes 550GB to store a 2^31 by 32 array of integers, so that's why your computer is unhappy. $\endgroup$ – Carl Woll Sep 24 '18 at 0:39
  • $\begingroup$ maybe it could be nicer if your comment would be told to me by Mathematica itself? $\endgroup$ – Seyhmus Güngören Sep 24 '18 at 13:44
1
$\begingroup$
ClearAll[monotoneDigits]
monotoneDigits = Module[{a = Accumulate[Binomial[#, Range[-1, #]]]},
 Join[{ConstantArray[0, 2^#]}, 
  IntegerDigits[Join@@Range[2^Most[1 + a] - 1, 2^Rest[a] - 1, 2^Most[a]], 2, 2^#]]]&;

Length @ monotoneDigits[5]

2111

Rest @ monotoneDigits[5] == res (* res from Carl's answer *)

True

Length /@ (monotoneDigits /@ Range[2, 6])

{6, 17, 96, 2111, 1114238}

monotoneDigits2[3] // Column // TeXForm

$\small\begin{array}{l} \{0,0,0,0,0,0,0,0\} \\ \{0,0,0,0,0,0,0,1\} \\ \{0,0,0,0,0,0,1,1\} \\ \{0,0,0,0,0,1,0,1\} \\ \{0,0,0,0,0,1,1,1\} \\ \{0,0,0,0,1,0,0,1\} \\ \{0,0,0,0,1,0,1,1\} \\ \{0,0,0,0,1,1,0,1\} \\ \{0,0,0,0,1,1,1,1\} \\ \{0,0,0,1,1,1,1,1\} \\ \{0,0,1,0,1,1,1,1\} \\ \{0,0,1,1,1,1,1,1\} \\ \{0,1,0,0,1,1,1,1\} \\ \{0,1,0,1,1,1,1,1\} \\ \{0,1,1,0,1,1,1,1\} \\ \{0,1,1,1,1,1,1,1\} \\ \{1,1,1,1,1,1,1,1\} \\ \end{array}$

Update: An alternative using Tuples in combination with PadLeft and PadRight:

ClearAll[paddedTuples , monotoneDigits2]
paddedTuples[t_][{m_, n_}] := PadLeft[PadRight[Rest@Tuples[{0, 1}, m], 
  {Automatic, n}, 1], {Automatic, t}] 

monotoneDigits2 = Module[{a = Transpose[{#, Accumulate@#}& @ Binomial[#, Range[0, #]]]}, 
   Join @@ (paddedTuples[2^#] /@ a)]&;

monotoneDigits2[5] == res

True

$\endgroup$
  • $\begingroup$ Great job as always.. $\endgroup$ – Seyhmus Güngören Sep 23 '18 at 19:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.