8
\$\begingroup\$

the aim of the code below is to print all balanced sequences with equal number of 'A' and 'B'. A sequence is balanced if every prefix of length \$\geqslant 4\$ is balanced. A prefix is balanced if the ratio of 'A' in this prefix is between 0.4 and 0.6 inclusive.

For example, ['A', 'B', 'B', 'A', 'A', 'B', 'A', 'B'] is balanced because:

Prefix Ratio of 'A'
['A', 'B', 'B', 'A'] 2/4 = 0.5
['A', 'B', 'B', 'A', 'A'] 3/5 = 0.6
['A', 'B', 'B', 'A', 'A', 'B'] 3/6 = 0.5
['A', 'B', 'B', 'A', 'A', 'B', 'A'] 4/7 = 0.57
['A', 'B', 'B', 'A', 'A', 'B', 'A', 'B'] 4/8 = 0.5

On the other hand, ['A', 'B', 'B', 'A', 'A', 'A', 'B', 'B'] is not balanced, because the ratio of 'A' in the prefix ['A', 'B', 'B', 'A', 'A', 'A'] is 4/6 = 0.67, which is too high.

The code:

from itertools import combinations

n = 8
MIN_RATIO = 0.4

for c in combinations(range(n), n // 2):
    is_balanced = True
    for prefix_len in range(4, n):
        prefix_ratio = sum([1 if i < prefix_len else 0 for i in c]) / prefix_len
        if not (MIN_RATIO <= prefix_ratio <= 1 - MIN_RATIO):
            is_balanced = False
            break
    if is_balanced:
        res = ['A' if i in c else 'B' for i in range(n)]
        print(res)

The idea here is that there are \$\binom{n}{n/2}\$ ways to place the \$\frac{n}{2}\$ 'A's in a sequence of length \$n\$; the other \$\frac{n}{2}\$ places will be occupied by the 'B's. (\$n\$ is assumed to be even.) Each one of the \$\binom{n}{n/2}\$ ways is tested for being balanced, and if so - a suitable sequence of 'A' and 'B' is generated and printed.

I'm not sure whether my code is readable enough, or whether there are a simpler and/or more elegant algorithm. Please review my code for readability and elegance.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ You seem to be missing a lot. A balanced string may have way less (or way more) As than \$n/2\$. For example, a 10-letter sequence ABABABABBB is balanced, yet it inly have 4 As. Longer strings will survive larger disparity. \$\endgroup\$
    – vnp
    Sep 21 at 2:53
  • \$\begingroup\$ @vnp The requirement is that every sequence has the same number of A and B. In a 10-letter sequence there should be 5 A's and 5 B's. The requirement is stated in the first sentence of the post. \$\endgroup\$
    – kodkod
    Sep 21 at 13:02
  • \$\begingroup\$ The condition is easy to evaluate, You iterate through the values just once. You keep a count of how many A's have been seen so far and how many B's. If you have seen more than four items, and the ratio of A to B is outside of the tolerance range, then stop and report "unbalanced". Otherwise if you run out of items, report "balanced"., \$\endgroup\$
    – Kaz
    Sep 21 at 23:46
  • \$\begingroup\$ Is [A, A] balanced? Every prefix of [A, A] that is greater than length 4 is balanced (vacuous truth). If you have quoted the definition of balance verbatim, I'd like a word with whoever specified it. \$\endgroup\$
    – Kaz
    Sep 21 at 23:48

2 Answers 2

11
\$\begingroup\$

Refactor to use functions

Try to avoid boolean variables. Pseudocode like:

result = True

for item in iterable:
    if item fails test:
        result = False
        break

if result:
    do stuff

can almost always be refactored to:

def any_item_fails_test(iterable):
    for item in iterable:
        if item fails test:
            return False
    return True

if any_item_fails_test(iterable):
    do stuff

This is an improvement because it breaks a logical operation out to a separate function, cleaning up the calling code, reducing state, making debugging easier and promoting reusability. It provides a name for the operation and shows its dependent data as parameters.

I suggest putting all of your code into functions rather than loose in the global scope. In addition to the above organizational reasons, this should provide faster execution in CPython.

The typical setup for a main program or small script is

def main():
    # your code here

if __name__ == "__main__":
    main()

While you're going about creating functions, take hardcoded variables like

n = 8
MIN_RATIO = 0.4

and make them parameters to the function. This facilitates reuse and makes the calling code clearer. I only use global constants like MIN_RATIO when the value is unlikely to change, is used everywhere in the program and is more than just an argument that can be conveniently passed as a parameter in one or two places.


List comprehensions vs generators

sum([1 if i < prefix_len else 0 for i in c])

is good because the list comprehension is faster than a generator unless memory consumption is an issue, in which case consider using a generator here.

I haven't thought about the algorithm here much, but since combinations can blow up in size quickly, you'll typically want to return a generator rather than a list once you put this into a function. Let the caller consume the result as they see fit, optionally printing the results.

len([x for x in combination if x < prefix_len]) seems a bit clearer since we're trying to filter out elements that fail a predicate, then count how many passed.


Simplify conditions

The condition

if not (MIN_RATIO <= prefix_ratio <= 1 - MIN_RATIO):

is a bit too clever for me to grasp; negation adds a good deal of cognitive load. It seems clearer to write it positively:

if prefix_ratio < MIN_RATIO or prefix_ratio > 1 - MIN_RATIO:

Suggested rewrite

from itertools import combinations


def is_balanced(n, combination, min_ratio, start=4):
    for prefix_len in range(start, n):
        prefix_sum = len([x for x in combination if x < prefix_len])
        prefix_ratio = prefix_sum / prefix_len

        if prefix_ratio < min_ratio or prefix_ratio > 1 - min_ratio:
            return False

    return True


def all_balanced_sequences(n, min_ratio, chars="AB"):
    if len(chars) != 2:
        raise ArgumentError("chars length must be 2")

    for combination in combinations(range(n), n // 2):
        if is_balanced(n, combination, min_ratio):
            yield [chars[0] if i in combination else chars[1] for i in range(n)]


def main():
    for seq in all_balanced_sequences(n=8, min_ratio=0.4):
        print(seq)


if __name__ == "__main__":
    main()
\$\endgroup\$
2
  • \$\begingroup\$ Possibly less readable (?), but the sum can be written sum([i < prefix_len for i in c]), which is why the itertools recipe for quantify(pred, iter) is just sum(map(pred, iter)). Though it begs the question for why a “iterator length” function is not standard. \$\endgroup\$ Sep 21 at 22:45
  • 1
    \$\begingroup\$ I thought of that, bools can work like True + True == 2 but I kept it numbers. Really, it's a filter, so len([x for x in combination if x < prefix_len]) may be better. I'll use that. \$\endgroup\$
    – ggorlen
    Sep 22 at 0:01
6
\$\begingroup\$

Avoid unnecessary computations

The requirement that all prefixes of length \$\geq 4\$ must be balanced excludes a lot of combinations. For any prefix length, 80% of the combinations of that length are excluded under the balanced ratio parameters 0.4 and 0.6. As such, less than 20% of all the possible combinations are used.

Instead of computing all the possible combinations and then filtering out the unbalanced ones, you could compute the balanced combinations directly by accumulating from balanced prefixes. For each balanced prefix, you could generate valid prefixes of the next length by adding A, and, or B if the overall count of As will stay within the required bounds.

To avoid repeated counting of As in the balanced prefixes, you could track the count of As together with the prefixes themselves.

  • Initialize a queue with all the valid combinations of length 4
  • loop forever
    • peek prefix, count from the queue
    • if the length of prefix is the target length, break out of the loop, the results are all in the queue
    • for i in range(len(queue))
      • pop prefix, count from the queue
      • if count + 1 will be within the bounds at len(prefix)
        • add prefix + A, count + 1 to the queue
      • if count will be within the bounds at len(prefix)
        • add prefix + B, count to the queue

Implementation:

def all_balanced_sequences_bfs(n, min_ratio, chars="AB"):
    if len(chars) != 2:
        raise ValueError("chars length must be 2")

    max_ratio = 1 - min_ratio
    c1, c2 = chars

    queue = deque((p, 2, 4) for p in set(permutations(chars * 2, 4)))

    while True:
        if len(queue[0][0]) == n:
            break

        for _ in range(len(queue)):
            prefix, count, length = queue.popleft()

            length += 1

            if min_ratio <= (count + 1) / length <= max_ratio:
                queue.append((prefix + (c1,), count + 1, length))

            if min_ratio <= count / length <= max_ratio:
                queue.append((prefix + (c2,), count, length))

    yield from (item[0] for item in queue)

Note that an important caveat of this breadth-first-search approach is that the queue will hold all the results in memory at the end. If you prefer to avoid that, it's easy enough to translate this code to a recursive function that yields the results:

def all_balanced_sequences_dfs(n, min_ratio, chars="AB"):
    if len(chars) != 2:
        raise ValueError("chars length must be 2")

    max_ratio = 1 - min_ratio
    c1, c2 = chars

    def dfs(prefix, count, length):
        if length == n:
            yield prefix
            return

        length += 1

        if min_ratio <= (count + 1) / length <= max_ratio:
            yield from dfs(prefix + (c1,), count + 1, length)

        if min_ratio <= count / length <= max_ratio:
            yield from dfs(prefix + (c2,), count, length)

    for p in set(permutations(chars * 2, 4)):
        yield from dfs(p, 2, 4)

And if you're concerned about reaching the stack size limit, then you can translate the recursive logic to iterative logic using a stack.

\$\endgroup\$

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.