Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I am a mathematics student and am just starting to learn about programming. I am stuck on a particular program I am trying to write for fun. I want to find an algorithm to create all possible column vectors of size N containing only ones and zeroes and combine them in one large matrix by putting all the columns after each other. The order of the columns is of no importance. For instance if N=3 I want to get the matrix:

0 1 1 1 1 0 0 0
0 0 1 0 1 1 1 0
0 0 0 1 1 0 1 1

which vertically contains all possible combinations of ones and zeroes of length 3. Does anyone have any idea how to do this? I am not necessarily looking for a very efficient or clever way to do this because the value I will be using for N is 14, so my matrix will be 14 x 2^14 which is 14 x 16384 which is not too big. Also, sorry for the formatting of my question, I am used to the math stackexchange where you can use LaTeX text to make your matrices and equations look nice. Thanks to anyone who can help me along!

share|improve this question

closed as not constructive by Glenn Nelson, Martijn Pieters, Bart van Ingen Schenau, BЈовић, ChrisF Apr 15 '13 at 11:12

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance.If this question can be reworded to fit the rules in the help center, please edit the question.

    
Sharing your research helps everyone. Tell us what you've tried and why it didn’t meet your needs. This demonstrates that you’ve taken the time to try to help yourself, it saves us from reiterating obvious answers, and most of all it helps you get a more specific and relevant answer. Also see How to Ask –  gnat Apr 13 '13 at 19:49

3 Answers 3

up vote 5 down vote accepted

In your example you are just writing down all numbers from 0 to 7 = 2^3 in binary form (the columns of your matrix). So, for a mathematician, the generalization for the general case should be obvious. You'll need to have big int to your avail to pursue that idea, though. Which should not really be a problem, though.

share|improve this answer
    
Just noticed you only need N=14 -- for that you won't even need big ints. –  Thomas Apr 13 '13 at 18:07
    
Thanks a lot for your answer. That's actually a great way of doing it! –  Teun Verstraaten Apr 13 '13 at 18:14

I wrote you an quick example of a shell script that would do such a thing in Python. Of course you could make it way faster using a c (or a different programming approach) but that is not my point.

# Size of n
n = 3
# Total possibilities
p = 2**n
# This creates a set of binary numbers
x=0
bnum=[]
bitem=1
while x < n:
  bnum.insert(0,bitem)
  bitem = bitem*2
  x = x +1

# Print the set of binary number to the screen  
print 'bin set', bnum
pset = range(p)
print 'total possibilities = %i' %p

# Function to covert to binary numbers
def convbin(num):
  modc = num
  x=0
  binset = []
  while x < n:
    mod = modc%bnum[x]
    if modc == mod :
      binset.append(0)
    elif mod == 0:
      binset.append(1)
    else:
      binset.append(1)
    modc = mod
    x = x+1
  print binset

# Call function
for item in pset:
  convbin(item)

Output would be:

bin set [4, 2, 1]
total possibilities = 8
[0, 0, 0]
[0, 0, 1]
[0, 1, 0]
[0, 1, 1]
[1, 0, 0]
[1, 0, 1]
[1, 1, 0]
[1, 1, 1]
share|improve this answer

The two other answers (so far) are good ones, but I think it's interesting to point out the recursive nature of the problem. If you want to generate all the binary values up to 2n-1 for some n, you can start by writing the values for n=1, i.e. just write down the possible digits:

0 1                                     n=1

Next, copy those values, and prepend each of the possible digits to each copy:

0 0 1 1                                 n=2
0 1 0 1

Repeat as necessary:

0 0 0 0 1 1 1 1                         n=3
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1

0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1         n=4
0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

You can see that an easy way to generate all the combinations is to write the first line by printing 2n-1 0's followed by 2n-1 1's, repeated 20 times. The next line gets 2n-2 0's followed by 2n-2 1's, repeated 21 times, and so on.

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.