Find list of valid continuing positions in a game My kids got a dice game for Christmas. I'm trying to mathematically analyze it. The first step is to come up with a list of all possible positions.

Each player in the game has a certain number of chips. A valid position is when more than one player has chips. If only one player has chips, they win and the game is over -- that's easy to identify.

I'm trying to come up with sensible code that uniquely lists all non-terminating positions. I use flatten() from more_itertools which is in PIP. Here's what I've got:

from more_itertools import flatten
from itertools import permutations

def all_nonzero_positions(num_players, num_chips, min_chips, max_chips):
    """ Returns all monotonically descending lists
        where num_chips are divided among num_players
        with each player having at least one chip, subject to the
        min_chips and max_chips constraints. Recursive. """ 
    if num_players==1:
        return [[num_chips]] if min_chips &lt;= num_chips &lt;= max_chips else []
    return [[p1] + y for p1 in range(min_chips,max_chips+1)
            for y in all_nonzero_positions(num_players-1, num_chips-p1,min_chips,p1)]

def all_positions_sorted(num_players, num_chips):
    """ Returns all monotonically descending lists
        where num_chips are divided among num_players
        where at least two players have one or more chips. 
        Works by repeatedly calling all_nonzero_positions()
        for smaller num_players and appending necessary zero elements. """ 
    return [position + [0]*zeroes for zeroes in range(0,num_players-1)
            for position in all_nonzero_positions(num_players-zeroes,num_chips,1,1000)]

def all_valid_positions(num_players, num_chips):
    return set(flatten(list(permutations(x))
                       for x in all_positions_sorted(num_players,num_chips)))

def main():
    print(*all_valid_positions(3,3), sep='\n')

if __name__ == "__main__":
    main()


What I don't like:


The lines are too long, but I don't see any place I can create temp variables or functions.
Can I get rid of more_itertools.flatten() without lengthening the code?
Can I get rid of list(), which I'm using to instantiate the generator?
Can I get rid of set(), which I'm using to trim the duplicates?
Is there a better way to permute than using itertools.permutations()?
Can all_nonzero_positions() be written without recursion?
I'm creating a ton of temporary lists here, can that be reduced?
What other comments should I add? The code is really short, I don't know where to put them.
Disclaimer: this is not a code review, but a suggestion for an alternative implementation.

First, there is not that many terminating positions (just num_players), so it seems easier to enumerate all positions, and filter the terminating ones out.

Second, given a position it is easy to generate lexicographically next one. In pseudocode,

    find the leftmost player holding non-zero amount of chips
    if it is the last player,
        we are done
    otherwise
        pass one chip to the next player, and
        give her remaining chips (if any) to player 0