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).
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...
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']
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.
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']]
