How do I compute all possibilities for an array of numbers/bits (in python, or any language for that matter)

Question

I have been wracking my brains out for 3 hours straight, but I still don't get it, so I am asking here. (I wrote Python in the title, but this could be for pretty much any language)

Let's assume I have an array of bits (but it may also be integers in a defined range) of fixed length n, let's say 5.

array=[0,1,1,0,0]

Now, how do I generate ALL arrays, which are possible in the number range (in the case of bits, 2).

So:

[0,0,0,0,0], [0,0,0,0,1], [0,0,0,1,0], [0,0,0,1,1] ...

I have tried searching for a solution here, but I always find something which is similar, but which doesn't quite solve my problem.

To solve this, I have tried various loops, but I always end up either getting one possibility more than once (should not happen), or not getting all possible ones.

I can manage to do this with if statements (to check if a combination already exists), but that seems very unsophisticated.

Is there a simple method, using only loops, to obtain all possibilities?

Thank you

Edit: Since this was mentioned below, no, this is not homework. This is for research in order to implement a Bayesian network of binary states. (on/off).

Airdrie

For the more general question, where they can be integers in a range, think about how an odometer works. Increment the lowest digit. When it goes past the top of the range it returns to 0, and then the next digit is incremented; if it goes about the top of its range it returns to 0 and you increment the next higher digit; and so on. The process finally stops when the first digit increments past its top. – Bravo

Answer 1

In Python, use itertools for stuff like this

from itertools import product
for i in product([0,1], repeat=5): 
    print(i)

Yields:

(0, 0, 0, 0, 0)
(0, 0, 0, 0, 1)
(0, 0, 0, 1, 0)
(0, 0, 0, 1, 1)
(0, 0, 1, 0, 0)
etc...

Formidable

As usual, python proves to be the way forward. I didn't know such a simple thing existed. Thank you very much indeed. This indeed yields the completely right answer! – Airdrie

Answer 2

I would approach this problem by just looping from 0 to 31 (0b11111) and turning the binary representation into an array of fixed length.

You didn't tag this with a language, so I'm not sure how to give you example code, but that approach should work.

1: 00001
2: 00010
3: 00011
...
30:11110
31:11111

Edit: Just saw you tagged this question with Python. Sample python code implementing the above algorithm:

listLength=5
for x in range(0,2**listlength):
    print(list(bin(x)[2:].zfill(listlength)))

prints out:

['0', '0', '0', '0', '0']
['0', '0', '0', '0', '1']
['0', '0', '0', '1', '0']
['0', '0', '0', '1', '1']
['0', '0', '1', '0', '0']
['0', '0', '1', '0', '1']
['0', '0', '1', '1', '0']
['0', '0', '1', '1', '1']
['0', '1', '0', '0', '0']
['0', '1', '0', '0', '1']
['0', '1', '0', '1', '0']
['0', '1', '0', '1', '1']
['0', '1', '1', '0', '0']
['0', '1', '1', '0', '1']
['0', '1', '1', '1', '0']
['0', '1', '1', '1', '1']
['1', '0', '0', '0', '0']
['1', '0', '0', '0', '1']
['1', '0', '0', '1', '0']
['1', '0', '0', '1', '1']
['1', '0', '1', '0', '0']
['1', '0', '1', '0', '1']
['1', '0', '1', '1', '0']
['1', '0', '1', '1', '1']
['1', '1', '0', '0', '0']
['1', '1', '0', '0', '1']
['1', '1', '0', '1', '0']
['1', '1', '0', '1', '1']
['1', '1', '1', '0', '0']
['1', '1', '1', '0', '1']
['1', '1', '1', '1', '0']

Ind

Thanks for your answer. It was helpful, though I am uncertain about a detail: Does this work for an array of any length, and will this give me all possible representations then? – Airdrie

Yep! For an array of n-length, you'll need to loop from 0 to 2^n-1. – Ind

I like the itertools solution on this question - go with that one. Wish I'd known you were using python right off of the bat or I'd have suggested that myself. :) – Ind

I missed the python as well. I was thinking it could have been anything from C to Haskell to Pascal. :-) – Mafaldamafeking

Answer 3

import numpy as np
def all_combinations(width, vals):
    return np.array(np.meshgrid(*[vals]*width,
                    indexing='ij')).reshape((width,-1)).transpose()

print(all_combinations(width=3, vals=[0,1]))
print(all_combinations(width=2, vals=['a','b','c']))

Output:

[[0 0 0]
 [0 0 1]
 [0 1 0]
 [0 1 1]
 [1 0 0]
 [1 0 1]
 [1 1 0]
 [1 1 1]]
[['a' 'a']
 ['a' 'b']
 ['a' 'c']
 ['b' 'a']
 ['b' 'b']
 ['b' 'c']
 ['c' 'a']
 ['c' 'b']
 ['c' 'c']]

Impetrate

This is so much faster than other answers, Thanks!! I hope you don't mind I added timing. – Eugine

Answer 4

Here is a generalized recursive pseudocode to do what you seek.

array_combination is function (length, elements)
  if length < 1 
  then abort
  end if

  declare arrays as new array
  if length is 1 
  then
    loop for element in elements
      declare element_array as new array
      set element_array[0] to element
      append element_array to arrays
    end loop
  else
    loop for array in array_combination(length - 1, elements)
      loop for element in elements
        declare element_array as new array
        set element_array[0] to element
        append array to element_array
        append element_array to arrays
      end loop
      append array to arrays
    end loop
  end if
  return arrays
end function

You would call this function as "array_combination(5, [1,0])" for your given example. There are better ways to build it but a) I am too old to do homework, b) I don't know the constraints of your assignment, and c) I don't want to make it too obvious that you cheated.

Note repeated code and opportunities for common subexpression elimination along with extremely wasteful memory allocation and cache abuse. However, I'm assuming this is a first quarter computer science assignment, so they probably won't hold it against you.

Mafaldamafeking

Thank you for your reply, but this is not "homework". This is for a simulation of a bayesian network which I would like to implement for my reasearch. I will try to make work what you wrote. – Airdrie

Answer 5

A kinky solution would be to think that, at every 'iteration' up until size n, you would double the number of combinations with a 0 or a 1 in the new dimension.

Starting from the simplest case n=1:

[[0],
 [1]]

With n=2, you repeat the array before adding zeros and ones, respectively:

[[0, 0],
 [1, 0],
 [0, 1],
 [1, 1]]

You can keep going until size n. Implementing this, you'd have:

BIN = np.array([[0], [1]])
for i in range(n-1):
    size = BIN.shape[0]
    BIN = np.vstack((np.hstack((BIN, np.zeros((size, 1)))), np.hstack((BIN, np.ones((size, 1))))))

It's not the prettiest solution, but it opens the possibility of implementing with recursion.

Centenarian