Task: create function that takes binary string and returns natural number from 1 to 2^N

Q

q250

New member
Joined
Nov 22, 2023
Messages
4
Let N be the size of a binary string. Now make set of all binary strings of size N, from 00...00 to 11...11, in increasing order from smaller to larger. Now let's make another set of same elements, but in a different order. In what order? To do this, we take the function X(n), and it does following - it takes a binary string and returns a natural number from 1 to 2^N. I honestly don't know how it should calculate it, but it should do something like following: build a binary tree(?) of comparisons, first compare halves of string with each other. then quarters, and I don't know if we should compare each with each or if 1 to 2, and 3 to 4 comparisons will suffice. then one eights, etc. at end compare neighbouring ones, here each with each is definitely unnecessary. Then we translate these comparisons into values with weights, for example, the strings that have repeats of halves should be lower than those that have repeats of quarters, and those that have no repeats of either quarters or halves should be higher, closer to beginning, to the number 1. Then we do something-something on these values and BOOM! we get natural number, it is also an ordinal number. For example, if N=8, then the string 11111111 should have number 256, it same everywhere no matter how you look, string 00000000 should have number 255, string 11111110 should have number 254 and so on. Your work is to figure out what to put here Instead of (BOOM!)
At first I thought that I could just do away with fact that you can represent the string as a number of combinations of ones from string length, and all combinations where number of ones is close to half the length, just put it in front of set, but then I thought that for example the string 00001111 with this approach will stand higher, closer to 1, than the string 00101001, and this is a fatal flaw.
 
q250 said:
Let N be the size of a binary string. Now make set of all binary strings of size N, from 00...00 to 11...11, in increasing order from smaller to larger. Now let's make another set of same elements, but in a different order. In what order? To do this, we take the function X(n), and it does following - it takes a binary string and returns a natural number from 1 to 2^N. I honestly don't know how it should calculate it, but it should do something like following: build a binary tree(?) of comparisons, first compare halves of string with each other. then quarters, and I don't know if we should compare each with each or if 1 to 2, and 3 to 4 comparisons will suffice. then one eights, etc. at end compare neighbouring ones, here each with each is definitely unnecessary. Then we translate these comparisons into values with weights, for example, the strings that have repeats of halves should be lower than those that have repeats of quarters, and those that have no repeats of either quarters or halves should be higher, closer to beginning, to the number 1. Then we do something-something on these values and BOOM! we get natural number, it is also an ordinal number. For example, if N=8, then the string 11111111 should have number 256, it same everywhere no matter how you look, string 00000000 should have number 255, string 11111110 should have number 254 and so on. Your work is to figure out what to put here Instead of (BOOM!)
At first I thought that I could just do away with fact that you can represent the string as a number of combinations of ones from string length, and all combinations where number of ones is close to half the length, just put it in front of set, but then I thought that for example the string 00001111 with this approach will stand higher, closer to 1, than the string 00101001, and this is a fatal flaw.
Click to expand...
Please post the problem as is, without your comments. Otherwise it's not clear where the problem ends and your comments begin.
 
Create function that take on input binary string length N and give nutural number from 1 to 2^N. using repeating patterns in that string. Compare half of string, then quaters etc then neighboring bits. Strings with less repeating should be given number closer to 1, with more repeating closer to 2^N, example if N=8, then the string 11111111 should have number 256.
 
q250 said:
Let N be the size of a binary string. Now make set of all binary strings of size N, from 00...00 to 11...11, in increasing order from smaller to larger.
Click to expand...
If [imath]N=3[/imath] here are the eight bit-strings built on the design of a three variable truth-table.
[imath]\begin{gathered} 0\;0\;0 \\ 0\;0\;1 \\ 0\;1\;0 \\ 0\;1\;1 \\ 1\;0\;0 \\ 1\;0\;1\\1\;1\;0 \\1\;1\;1 \\ \end{gathered} [/imath]
Note that the numbers are in increasing numerical order.
Now please answer lev888's question in reply #2!

[imath][/imath][imath][/imath][imath][/imath]
 
q250 said:
For example, if N=8, then the string 11111111 should have number 256, it same everywhere no matter how you look, string 00000000 should have number 255, string 11111110 should have number 254 and so on.
Click to expand...
You haven't stated your goal. Can you explain why these should be the resulting values? What is your criterion?
What values would you give to the 8 3-bit strings @pka listed?
 
ok, forget that question
new ones: N - length of binary string, 2^N - amount of all binary strings of that size. how much strings have their halfs look alike, ie take string, cut in half, compare that halfs? how much have their quatrers look alike, ie take string, cut in 4 picies, compare any two of them? how much have their eights look alike? now question, how much strings have their halfs look alike and their quatrers look alike? how much strings have their halfs look alike and not their quatrers look alike and their eights look alike? how much how much strings have their not halfs look alike and their quatrers look alike?
 
q250 said:
ok, forget that question
new ones: N - length of binary string, 2^N - amount of all binary strings of that size. how much strings have their halfs look alike, ie take string, cut in half, compare that halfs? how much have their quatrers look alike, ie take string, cut in 4 picies, compare any two of them? how much have their eights look alike? now question, how much strings have their halfs look alike and their quatrers look alike? how much strings have their halfs look alike and not their quatrers look alike and their eights look alike? how much how much strings have their not halfs look alike and their quatrers look alike?
Click to expand...
Your thoughts? Where are you stuck on the first question?
 
q250 said:
ok, forget that question
new ones: N - length of binary string, 2^N - amount of all binary strings of that size. how much strings have their halfs look alike, ie take string, cut in half, compare that halfs? how much have their quatrers look alike, ie take string, cut in 4 picies, compare any two of them? how much have their eights look alike? now question, how much strings have their halfs look alike and their quatrers look alike? how much strings have their halfs look alike and not their quatrers look alike and their eights look alike? how much how much strings have their not halfs look alike and their quatrers look alike?
Click to expand...
Since your English is not clear, it will help if you give examples of exactly what you are asking. Try showing the strings you are looking for, and therefore the answers to all your questions, for a simple case like N=4 or N=5. (Are you assuming N is a power of 2, so that "halves" always make sense? Do all the quarters have to be equal, or just some?)

Also, why are you asking? Is this for a class, or for a real-life problem, or just for fun?
 
  • Like
Reactions: pka
Full context
I notice that set of all strings size N is bigger than set of all strings sizes (N-1) and (N-2) and...(1) only on two elements, and if you remove them then they become equal=> bijection
pictures for understanding
https://imgur.com/a/YiMWjPF
https://imgur.com/a/dLMLSVV

As you can see, yes, it can be done, so for any N theare exist method to compress it at least at one bit smaller. Problem - it not very efficient, look at what kind of string goes in smallest size. To solve this left column need to be reshufled in order that strings with biggest entropy goes on top and with smallest goes on bottom. How to calculate string entropy? Firstly i think that simply putting strings with number of ones, or zeroes, equal to half of string size, then strings with with number of ones equal to half of string size-1 etc would do trick, but then i looked at what strings goes on very top and in case of N=8 it 00001111, so, no, method is better than nothing, but it need something more efficient. Then i think that compare strings by their local corelations is wa to go. This is where i stuck.
 
q250 said:
Let N be the size of a binary string. Now make set of all binary strings of size N, from 00...00 to 11...11, in increasing order from smaller to larger. Now let's make another set of same elements, but in a different order. In what order? To do this, we take the function X(n), and it does following - it takes a binary string and returns a natural number from 1 to 2^N. I honestly don't know how it should calculate it,
Click to expand...
To q250, I want to address THAT QUESTION.
Suppose that [imath]N=7[/imath] and a seven-string is [imath]1011001[/imath].
First make a table as follows: [imath] \dfrac{0}{1}\dfrac{1}{0}\dfrac{2}{0}\dfrac{3}{1}\dfrac{4}{1}\dfrac{5}{0}\dfrac{6}{1}[/imath]
Note that the first row are the positions of the bits from zero to six, seven in all,
The second row are the bits themselves but listed in reverse order,
We are now ready to make the conversion [imath]2^0+2^3+2^4+2^6=89[/imath] So [imath]10110010_2=89_{10}[/imath]
Again make a table
  1. the first row is list of place holders from [imath]0\text{ from }N-1[/imath]
  2. second row is the string to be converted in reverse order.[imath][/imath]
  3. then add a summation of powers of [imath]2[/imath] determined by the [imath]1's[/imath] the table.
 
pka said:
To q250, I want to address THAT QUESTION.
Suppose that [imath]N=7[/imath] and a seven-string is [imath]1011001[/imath].
First make a table as follows: [imath] \dfrac{0}{1}\dfrac{1}{0}\dfrac{2}{0}\dfrac{3}{1}\dfrac{4}{1}\dfrac{5}{0}\dfrac{6}{1}[/imath]
Note that the first row are the positions of the bits from zero to six, seven in all,
The second row are the bits themselves but listed in reverse order,
We are now ready to make the conversion [imath]2^0+2^3+2^4+2^6=89[/imath] So [imath]10110010_2=89_{10}[/imath]
Again make a table
  1. the first row is list of place holders from [imath]0\text{ from }N-1[/imath]
  2. second row is the string to be converted in reverse order.[imath][/imath]
  3. then add a summation of powers of [imath]2[/imath] determined by the [imath]1's[/imath] the table.
Click to expand...
This, of course, produces a number from 0 through [imath]2^{N}-1[/imath]. You could then add 1 if the goal is a number from 1 through [imath]2^N[/imath].

And I think he already knows this part; he just doesn't know how to state what he really wants -- which is something more than a natural number.

q250 said:
I notice that set of all strings size N is bigger than set of all strings sizes (N-1) and (N-2) and...(1) only on two elements, and if you remove them then they become equal=> bijection
pictures for understanding
https://imgur.com/a/YiMWjPF
https://imgur.com/a/dLMLSVV

As you can see, yes, it can be done, so for any N there exist method to compress it at least at one bit smaller. Problem - it not very efficient, look at what kind of string goes in smallest size. To solve this left column need to be reshuffled in order that strings with biggest entropy goes on top and with smallest goes on bottom. How to calculate string entropy? Firstly i think that simply putting strings with number of ones, or zeroes, equal to half of string size, then strings with with number of ones equal to half of string size-1 etc would do trick, but then i looked at what strings goes on very top and in case of N=8 it 00001111, so, no, method is better than nothing, but it need something more efficient. Then i think that compare strings by their local correlations is way to go. This is where i stuck.
Click to expand...
This is still very unclear. What does that first sentence mean? What is the bijection?

If you're talking about compressing a string, you will lose information, and you haven't shown what information you are willing to lose. And how are you defining "entropy"?
 
You must log in or register to reply here.
Top