Finding the balanced code of size k using recursion

Admin 1
Viewed 278

I have a problem for an assignment I am working on, where I have to write a recursive function in python which returns the balanced code of size k, which is defined as the list of all binary strings of length 2k that contain an equal number of 0s in each half of the string. It is only allowed to accept one parameter, k. I have so far found a way to return a list of all possible binary strings of length 2k, but am having trouble reducing the list to only those that meet the criteria. This is my code so far:

def balanced_code(k):  
if k >= 0:        
    if k == 0:
        return ['']
    else:
        L = []
        x = balanced_code(k - 1)
        for i in range(0, len(x)):
            L.append('00' + x[i])                
            L.append('01' + x[i])
            L.append('10' + x[i])
            L.append('11' + x[i])
        return L
else:
    return

My plan was after the for loop, I would check each item in L for the criteria mentioned (number of 0s equal in each half of the string), but quickly realized that this didn't give the right result as it would reduce L during every call, and I only want to reduce it once all calls to the function have been made. Is there any way I could track what recursion level the code is on or something like that so that I only reduce the list once all calls have been made?

recursion binary algorithm python
3 Answers

How recursive does this have to be? Where does the recursion need to be?

If this were me, I'd write a recursive function:

def all_strings_of_length_k_with_n_zeros(k, n):
    ... you should be able to write this easily as recursion

And then

def balanced_code(k):
   result = []
   for zeros in range(0, k + 1):
      temp = all_strings_of_length_k_with_n_zeros(k, zeros)
      for left, right in itertools.product(temp, temp):
         result.append(left + right)
   return result

It's strange that your instructor is asking you to write some code recursively that can be written straightforwardly without recursion. (The function I left as an exercise to the reader could be written using itertools.combinations).

user_64574070

You can approach the recursion by adding "0" and "1" bits on each side of the k-1 results. The bits need to be added last on the right side and at every position on the left side. Since this is going to produce duplicates, using a set to return the strings will ensure distinct results.

def balancedCodes(k):
    if not k: return {""}
    return { code[:pos]+bit+code[pos:]+bit for code in balancedCodes(k-1)
                                           for pos  in range(k)
                                           for bit  in ("0","1") }

for bc in sorted(balancedCodes(3)): print(bc)


000000
001001
001010
001100
010001
010010
010100
011011
011101
011110
100001
100010
100100
101011
101101
101110
110011
110101
110110
111111

The 111111 result is a case of having no zeroes on each side

user_52375600

One way to solve this recursively without creating duplicates is by using what's described by The On-Line Encyclopedia of Integer Sequences® as the "1's-counting sequence: number of 1's in binary expansion of n (or the binary weight of n)" (sequence A000120), which can be formulated as a recurrence relation (see the function, f, below). Although we could "unpack" the sequence into our result at every stage for a self-contained recursive answer, it seemed superfluous so I left the unpacking of the sequence as a separate function we can call on the result.

def str_tuple(a, b, k):
  return "{0:0{align}b}{1:0{align}b}".format(a, b, align=k)

def unpack(seq, k):
  bitcounts = [[] for _ in range(k + 1)]
  products = []

  for n, i in enumerate(seq):
    for n0 in bitcounts[i]:
      products.extend([str_tuple(n0, n, k), str_tuple(n, n0, k)])
    products.append(str_tuple(n, n, k))
    bitcounts[i].append(n)

  return products
  
def f(n):
  if n == 1:
    return [0, 1]

  seq_l = f(n - 1)
  seq_r = list(map(lambda x: x + 1, seq_l))
  
  return seq_l + seq_r
    
k = 3

print(f(k))

print(unpack(f(k), k))

Output:

[0, 1, 1, 2, 1, 2, 2, 3]

['000000', '001001', '001010', '010001', '010010',
 '011011', '001100', '100001', '010100', '100010',
 '100100', '011101', '101011', '101101', '011110',
 '110011', '101110', '110101', '110110', '111111']
user_20347870
Related