Split list recursively until flat

Question

I'm writing a passion program that will determine the best poker hand given hole cards and community cards. As an ace can go both ways in a straight, I've coded this as [1, 14] for a given 5 card combination.

I understand recursion but implementing it is a different story for me. I'm looking for a function that will split all aces recursively, into all possible hand combinations until all nested lists are exhausted. This should obviously work with up to 4 aces, overlooking the fact that you wouldn't care about a straight at that point in all likelihood.

hand = [[1, 14], 2, 3, [1, 14], 7]

desired_output = [
        [1, 2, 3, 1, 7],
        [1, 2, 3, 14, 7],
        [14, 2, 3, 1, 7],
        [14, 2, 3, 14, 7]
        ]

I'm not proud of what I have so far, especially because it returns a list instead of something like a yield which would build the list I'm looking for:

def split_first_ace(hand):
    aces = [True if isinstance(x, list) else False for x in hand]
    for i, x in enumerate(aces):
        if x:
            ranks_temp = hand.copy()
            ace = ranks_temp.pop(i)
            return [[ace[0]] + ranks_temp, [ace[1]] + ranks_temp]

Any help on a solution would be appreciated, mostly because it'll help me understand how to implement recursion. But I'm open to other solutions as well.

Just a bit of feedback, you could replace the `True`/`False` list with a list of indexes containing an ace (as shown [here](https://stackoverflow.com/questions/6294179/how-to-find-all-occurrences-of-an-element-in-a-list)). In short, you'd have `indices = [i for i, x in enumerate(hand) if x == [1,14]]`. Now you can just iterate over `indices` rather than enumerating over `aces` and checking if it is `True` — JolonB, Aug 29 '20 at 03:04
@JolonB Yep, you're right. Would spare me a bit of redundancy. Appreciate the feedback. I'll claim to have been coding that part for clarity ;) — Balter, Aug 29 '20 at 03:09
since your output will be a list of hands... it might be a good idea to define hand that way since the start, `hand = [[[1, 14], 2, 3, [1, 14], 7]]` — RichieV, Aug 29 '20 at 03:11
@RichieV I will indeed have hands defined that way, since I'll be iterating through a list of all possible hand combinations to determine if a hand is a straight, or a flush, or what have you. Just wrote this example for the help. — Balter, Aug 29 '20 at 03:13

score 20 · Accepted Answer · answered Aug 29 '20 at 03:11

20

Well, there is an easier way to do this:

from itertools import product

product(*[i if isinstance(i, list) else [i] for i in hand])

I challenge everybody to come up with a simpler solution

answered Aug 29 '20 at 03:11

Marat

15,215
2
39
48

It took me a while to understand that you are casting every card to a list and that is why `product(*` works... – RichieV Aug 29 '20 at 03:25
2

Wouldn't `from collections.abc import Iterable` then `isinstance(i, Iterable)` be better? (Or the same, with `Sequence` instead.) And, if you want some _premature optimisation_, you should probably write `*(...)` instead of `*[...]` to avoid the unnecessary creation of a list (see `dis.dis()` for details – it's an extra bytecode instruction, though; you need an extra `POP_TOP` because `YIELD_VALUE` returns `None`). (And, actually, you can replace `[i]` with `(i,)`, though I'm not sure whether that would do anything much.) – wizzwizz4 Aug 29 '20 at 17:15
@wizzwizz4 all your suggestions are correct. Checking for `Iterable` will make this a bit more general, and using generator expressions and tuples will decrease memory footprint. However, given the amount of data the expected effect will be small. I admit, however, this is a "good enough" solution and in production it's better to stick to the best practices you named. – Marat Aug 29 '20 at 17:24

score 10 · Answer 2 · answered Aug 29 '20 at 03:08

The itertools.product() function might be useful. If we assume that the recursion will only be 1 level deep (aces don't have nested lists themselves), then we could use the following:

from itertools import product

hand = [[1, 14], 2, 3, [1, 14], 7]

aces = [x for x in hand if isinstance(x, list)]
rest = [x for x in hand if isinstance(x, int)]

combinations = [list(x) + rest for x in product(*aces)]
print(combinations)

Yields:

[[1, 1, 2, 3, 7], [1, 14, 2, 3, 7], [14, 1, 2, 3, 7], [14, 14, 2, 3, 7]]

score 0 · Answer 3 · answered Aug 29 '20 at 03:10

This might be overkill since you only need one level of recursion (like @Aaron Keesing's answer) but this should work:

def iter_hands(hand, __current_index=0, __current_combo=None):
    __current_combo = __current_combo or []
    if __current_index == len(hand):
        yield __current_combo.copy()
        return

    choices = hand[__current_index]
    if not isinstance(choices, list):
        choices = [choices]
    for c in choices:
        __current_combo.append(c)
        yield from iter_hands(hand, __current_index + 1, __current_combo)
        __current_combo.pop()


def main():
    input_hand = [[1, 14], 2, 3, [1, 14], 7]
    want_hands = [
        [1, 2, 3, 1, 7],
        [1, 2, 3, 14, 7],
        [14, 2, 3, 1, 7],
        [14, 2, 3, 14, 7]
    ]
    got_hands = [hand for hand in iter_hands(input_hand)]

    assert want_hands == got_hands


if __name__ == '__main__':
    main()

Split list recursively until flat

3 Answers3