c  go  java  js  lua  py  vbs  rkt  scm  pro  

For the introduction, see Entropy function .

The information entropy function is defined as follows.

The following formula expresses how entropy for a set of symbols is calculated.

• S is the entropy
• P_i is the probability of a given symbol i in a sequence of symbols appearing

Most people have played the game of twenty questions.

Here is a simplified version.

Think of a number from 1 to 1,000,000 I will guess that number in 20 yes-no questions.

Here is a more simplified version.

Think of a number from 1 to 16 I will guess that number in 4 yes-no questions.

How can you do it. Can you explain why it works.

In the study of algorithms, one learns how to use divide and conquer problem solving strategies for a problem space of size n.

• Divide the space by two at each step, or binary division of the problem, leads to a solution of order ln₂n or O(ln₂n).
• Divide the space of size n into 1 and n-1 leads to a solution of order n or O(n).

For guessing the 1 to 16, or 2⁴ the following hold.

• An O(n) solution requires 16 guesses to obtain the solution (in the worst case) and 8.5 guesses on average. Why?
• Note: If someone does not remember the numbers guessed, it can take longer, on average.
• An O(ln₂n) solution requires exactly 4 guesses. Why?

Here is a way to create partitioned lists of numbers using list on a lazy range.

The flowing program shows the entropy of each possible partition of a list of 16 elements into two non-empty lists.

Here is the Python code.
import math def entropyOf1(list1): # assume all different items len1 = len(list1) e1 = len1 * math.log(len1,2) return e1 len1 = 16 # make a list of a lazy range generator list1 = list(range(1,len1+1)) s1 = str(list1) print("List: {0:s}".format(s1)) print("") ePos1 = -1 eMin1 = 999.99 for i1 in range(1,len1): left1 = list1[:i1] lefts1 = str(left1) eLeft1 = entropyOf1(left1) right1 = list1[i1:] rights1 = str(right1) eRight1 = entropyOf1(right1) print("#{0:d}:".format(i1)) print("\t{0:0.2f} {1:s}".format(eLeft1,lefts1)) print("\t{0:0.2f} {1:s}".format(eRight1,rights1)) eMax1 = max(eLeft1,eRight1) print("\t{0:0.2f} (max)".format(eMax1)) if eMax1 < eMin1: ePos1 = i1 eMin1 = eMax1 print("") print("Minimum maximum entropy at #{0:d}:{1:0.2f} of {2:d} partitions.".format(ePos1,eMin1,len1-1)) print("")
Here is the output of the Python code.
List: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16] #1: 0.00 [1] 58.60 [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16] 58.60 (max) #2: 2.00 [1, 2] 53.30 [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16] 53.30 (max) #3: 4.75 [1, 2, 3] 48.11 [4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16] 48.11 (max) #4: 8.00 [1, 2, 3, 4] 43.02 [5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16] 43.02 (max) #5: 11.61 [1, 2, 3, 4, 5] 38.05 [6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16] 38.05 (max) #6: 15.51 [1, 2, 3, 4, 5, 6] 33.22 [7, 8, 9, 10, 11, 12, 13, 14, 15, 16] 33.22 (max) #7: 19.65 [1, 2, 3, 4, 5, 6, 7] 28.53 [8, 9, 10, 11, 12, 13, 14, 15, 16] 28.53 (max) #8: 24.00 [1, 2, 3, 4, 5, 6, 7, 8] 24.00 [9, 10, 11, 12, 13, 14, 15, 16] 24.00 (max) #9: 28.53 [1, 2, 3, 4, 5, 6, 7, 8, 9] 19.65 [10, 11, 12, 13, 14, 15, 16] 28.53 (max) #10: 33.22 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 15.51 [11, 12, 13, 14, 15, 16] 33.22 (max) #11: 38.05 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] 11.61 [12, 13, 14, 15, 16] 38.05 (max) #12: 43.02 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] 8.00 [13, 14, 15, 16] 43.02 (max) #13: 48.11 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13] 4.75 [14, 15, 16] 48.11 (max) #14: 53.30 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14] 2.00 [15, 16] 53.30 (max) #15: 58.60 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] 0.00 [16] 58.60 (max) Minimum maximum entropy at #8:24.00 of 15 partitions.

The result is that the best place to partition the list into two non-empty lists such that the minimum of the maximum entropies is in the middle. That is, that splits the list into two equal sized lists.