Given a number, generate a list of all possible combination of X and O with length n

Question

For example, if function(2) then it would produce

['XX','XO','OX','OO']

I am not sure how I would approach this problem

This is a small component of my assignment that I could not figure out. Unfortunately, my classes did not learn itertools yet so I don't think I'll be able to utilize this. — user3225528, Mar 17 '14 at 05:01

Burhan Khalid · Answer 1 · 2014-03-17T05:07:16.390

Unless this is an assignment, use product from itertools, like this:

>>> import itertools as it
>>> list(it.product('XO', repeat=2))
[('X', 'X'), ('X', 'O'), ('O', 'X'), ('O', 'O')]

If you want to know how to do this the "long" way, an implementation for the product method is available in the documentation:

def product(*args, **kwds):
    # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
    # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
    pools = map(tuple, args) * kwds.get('repeat', 1)
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]
    for prod in result:
        yield tuple(prod)

You might want to join the tuples. – thefourtheye Mar 17 '14 at 05:12 — thefourtheye, Mar 17 '14 at 05:12

score 2 · Answer 2 · edited Mar 17 '14 at 05:13

2

If you want to make your own function do something like this:

def crossProduct(A, B):
    #returns cross product of elements in A x elements in B
    return [a+b for a in A for b in B]

suits = 'CDHS'
ranks = '123456789JQKA'

cards = cross(suits,ranks)

print cards # prints out all 52 cards

edited Mar 17 '14 at 05:13

thefourtheye

233,700
52
457
497

answered Mar 17 '14 at 05:12

user2415706

932
1
7
19

score 0 · Answer 3 · answered Mar 17 '14 at 20:47

If function(n - 1) produces a list of all possible combinations of length n - 1, you can recursively generate the combinations of length n by returning

1) 'X' concatenated with each element in function(n - 1)

2) 'O' concatenated with each element in function(n - 1)

Like so:

def function(n):
    if n < 1:
        return []
    elif n == 1:
        return ['X', 'O']
    else:
        return ['X' + string for string in function(n - 1)] + ['O' + string
            for string in function(n - 1)]

score 0 · Answer 4 · edited May 23 '17 at 10:25

If you cannot use itertools, I suggest to consider binary number representation. If you iterate through all numbers between 0 and 2^n - 1, their 0-padded binary representations will yield all possible combinations of 0 and 1:

n = 3
for i in xrange(1<<n):
    print bin(i)[2:].zfill(n)

Will print:

(About the string manipulations, see this question)

The remaining part of the task is how to convert 101 to XOX, which can be done manually or, maybe, with maketrans/translate.

Note, that this works only for binary alphabets, like XO or |-.

Given a number, generate a list of all possible combination of X and O with length n

4 Answers4