8
\$\begingroup\$

I would like to only allow lists where the first n elements are True and then all of the remaining elements are False. I want lists like these examples to return True:

  • []
  • [True]
  • [False]
  • [False, False]
  • [True, False]
  • [True, False, False]
  • [True, True, True, False]

And lists like these to return False:

  • [False, True]
  • [True, False, True]

That is, any list that can we written as [True] * n + [False] * m for n, m integers in the interval [0, infty).

I am currently using a function called check_true_then_false, but I feel like there is probably a neater way of doing this. The code doesn't need to be fast, as this will only be run once (not inside a loop) and the lists will short (single digit lengths).

def check_true_then_false(x):
    n_trues = sum(x)
    should_be_true = x[:n_trues]  # get the first n items
    should_be_false = x[n_trues:len(x)]  # get the remaining items
    # return True only if all of the first n elements are True and the remaining
    # elements are all False
    return all(should_be_true) and not any(should_be_false)

Testing shows that it produces the correct output:

test_cases = [[True],
              [False],
              [True, False],
              [True, False, False],
              [True, True, True, False],
              [False, True],
              [True, False, True]]
print([check_true_then_false(test_case) for test_case in test_cases])
# expected output: [True, True, True, True, True, False, False]
\$\endgroup\$
  • \$\begingroup\$ Sorry it didn't work out. Try again on SO. I have a concrete answer I'd like to post that I think would work for this site, but would also work for SO. \$\endgroup\$ – Mad Physicist Sep 4 '18 at 3:41
  • \$\begingroup\$ Ping me if you decide to make the post again. \$\endgroup\$ – Mad Physicist Sep 4 '18 at 3:42
  • 1
    \$\begingroup\$ I've just removed this question from SO because I was told it was better suited to Code Review, so I don't know where to post it anymore. \$\endgroup\$ – Hasnep Sep 4 '18 at 3:51
  • 5
    \$\begingroup\$ Could you clarify the requirements? Are [], [True], and [False, False] acceptable? \$\endgroup\$ – 200_success Sep 4 '18 at 10:06
  • 1
    \$\begingroup\$ Another way of explaining is any list that can we written as [True] * n + [False] * m for n, m integers in the interval [0, infty). \$\endgroup\$ – Hasnep Sep 5 '18 at 2:18
13
\$\begingroup\$
  • You can just use x[n_trues:] rather than x[n_trues:len(x)].
  • Your comments don't really say more than the code. And so I'd recommend removing the comments.
  • If you want to keep your code documented use docstrings, which can be exported to your documentation via tools like Sphinx.
  • As commented by Konrad Rudolph, you can remove the and not any(should_be_false) as this will always fail if the all fails.
def check_true_then_false(x):
    """Check first n values are True and the rest are False."""
    return all(x[:sum(x)])

If you want your code to work with iterators, not just sequences then you can instead use:

def check_true_then_false(it):
    """Check first n values are True and the rest are False."""
    it = iter(it)
    # Takes advantage of the iterating side effect, where it consumes the iterator.
    # This allows `all` to simultaneously checks `it` starts with trues and advances `it`.
    return all(it) or not any(it)

For the following two inputs all will result in:

>>> all([True] * n)
True
>>> all([True] * n + [False, ...])
False

However it will mean that it is still [...] as all and any are lazy. Meaning that we just need to check the rest are false. Meaning all slices the iterator for you without you having to. Leaving any with:

>>> any([False] * n)
False
>>> any([False] * n + [True, ...])
True
\$\endgroup\$
  • 6
    \$\begingroup\$ all(it) or not any(it) is elegant! – It would detect ["a", "b"] as a valid list because it checks for truthiness rather than True/False, but from the Python point of view that is probably the “right thing.” \$\endgroup\$ – Martin R Sep 4 '18 at 8:46
  • 2
    \$\begingroup\$ Elegant but cryptic. I would be wary of using it in actual code. In the first bit of code (as in OP’s), you can omit the redundant test for and not any(…) (assuming the list only contains bools). \$\endgroup\$ – Konrad Rudolph Sep 4 '18 at 10:04
  • \$\begingroup\$ @KonradRudolph True, and true. I guess using a comment to decryptify it may help. \$\endgroup\$ – Peilonrayz Sep 4 '18 at 10:19
  • 2
    \$\begingroup\$ In the comment, instead of saying and slices it I would use the phrasing and advances it. \$\endgroup\$ – 409_Conflict Sep 4 '18 at 16:48
  • 1
    \$\begingroup\$ @RichardNeumann Yeah, the question said it only works with booleans, and so I didn't go out of my way to make it work with anything else \$\endgroup\$ – Peilonrayz Sep 17 '18 at 9:38
8
\$\begingroup\$

Basically, you want your list of booleans to be sorted.

Specifically, since True > False, you want your list to be sorted in decreasing order:

def check_true_then_false(booleans):
    return booleans == sorted(booleans, reverse=True)

Done!

>>> test_cases = [[True],
...               [False],
...               [True, False],
...               [True, False, False],
...               [True, True, True, False],
...               [False, True],
...               [True, False, True]]
>>> 
>>> print([check_true_then_false(test_case) for test_case in test_cases])
[True, True, True, True, True, False, False]
\$\endgroup\$
  • 2
    \$\begingroup\$ This is a good answer as it expresses a higher level property of the desired code. The code is clearer because you get the "why", instead of just the "how", from reading it. \$\endgroup\$ – lkraider Sep 4 '18 at 15:11
  • \$\begingroup\$ It may be more obvious if there is a partitioned(...) function in Python (I don't know Python that well, but C++ has std::is_partitioned). It's a bit tricky to think of sorted, as you wouldn't want to sort a list to create this pattern due to partitioning being a simpler algorithm. \$\endgroup\$ – Justin Sep 4 '18 at 17:26
  • \$\begingroup\$ @Justin: You're right that sorted is a minimal overkill. is_partitioned doesn't exist in standard Python as far as I know. Also, partition isn't enough : Trues should appear before Falses. \$\endgroup\$ – Eric Duminil Sep 4 '18 at 17:47
  • \$\begingroup\$ @EricDuminil Any decent partition implementation should take a predicate that allows you to specify how to partition it. Also, FWIW, C++'s std::partition moves true elements before false elements. \$\endgroup\$ – Justin Sep 4 '18 at 17:57
  • \$\begingroup\$ @Justin: Please ignore my last comment then. I learned something today. \$\endgroup\$ – Eric Duminil Sep 4 '18 at 18:20
5
\$\begingroup\$

Your code works correctly under the assumption that the given list contains only True or False elements. For other lists it can return “false positives”

>>> check_true_then_false([1, 1, 0])
True

or abort with a runtime error:

>>> check_true_then_false(["a", "b"])
TypeError: unsupported operand type(s) for +: 'int' and 'str'

The function traverses the given list in order to find the number of True elements. It then creates two additional lists, which are also traversed to check if all elements are True resp. False.

A more efficient way would be to iterate the given list only once:

  • Find the first non-True element. If there is any then it must be False.
  • Then find the next non-False element. There should not be any.

If either of the above iterations fails (and next() raises a StopIteration exception) then the list is of the required form, and the function returns True:

def check_true_then_false(x):
    list_iter = iter(x)
    try:
        return (next(elem for elem in list_iter if elem is not True) is False
            and next(elem for elem in list_iter if elem is not False) is False)
    except StopIteration:
        return True

Peilonrayz explained how to document the function using docstrings. In addition, the test cases can also be embedded into the docstrings, with doctest:

def check_true_then_false(x):
    """Check first n values are True and the rest are False.

    >>> check_true_then_false([True])
    True
    >>> check_true_then_false([False])
    True
    >>> check_true_then_false([False, True])
    False
    >>> check_true_then_false([True, False, True])
    False
    >>> check_true_then_false([1, 1, 0])
    False
    >>> check_true_then_false(["a", "b"])
    False

    """
    # ... Your code ...

if __name__ == "__main__":
    import doctest
    doctest.testmod()
\$\endgroup\$
  • \$\begingroup\$ This doesn’t correctly detect non-boolean values if the first non-True argument is not False. For example: check_true_then_false([True, True, "foo", False]) evaluates to True. \$\endgroup\$ – Neil Roberts Sep 4 '18 at 10:21
  • \$\begingroup\$ @NeilRoberts: You are right (because next() consumes that element). It should be fixed now (but lacks the elegance of Peilonrayz's solution). \$\endgroup\$ – Martin R Sep 4 '18 at 11:01

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.