Generate All Permutations of 0s and 1s
Hi, I have a basic knowledge of C++ programming (from a first year engineering course) and I'm trying to write some code for personal use. In order to do so, I'm trying to generate all possible permutations of n 0s and (n-k) 1s. For example, if I wanted to have all possibilities of arranging two 0s and two 1s I would want the array to store
1 1 1 0 0 0
1 0 0 1 1 0
0 1 0 1 0 1
0 0 1 0 1 1
This is the biggest difficulty I am having. The code should be able to do this for any amount of 0s and 1s up to thirteen (so up to thirteen 0s and zero 1s or thirteen 1s and zero 0s and anything in between).
1 1 1 0 0 0
1 0 0 1 1 0
0 1 0 1 0 1
0 0 1 0 1 1
This is the biggest difficulty I am having. The code should be able to do this for any amount of 0s and 1s up to thirteen (so up to thirteen 0s and zero 1s or thirteen 1s and zero 0s and anything in between).
Last edited on
Your question is a bit hard to understand: n 0s and (n-k) 1s - is that what you meant? Or should it be k 0s and n-k 1s ... up to n=13.
Your example was confusing me until I realised the permutations were in columns, not rows!
I haven't tried it - sorry! - but it looks like a case for a function called recursively. For example, if f(n,k) produces the permutations for k 0s out of n, then:
f(n+1,k) would come from
0 followed by f(n,k-1), together with
1 followed by f(n,k)
Each step would reduce the first index by 1, so the recursion should finish.
Don't know what anyone else thinks?
Your example was confusing me until I realised the permutations were in columns, not rows!
I haven't tried it - sorry! - but it looks like a case for a function called recursively. For example, if f(n,k) produces the permutations for k 0s out of n, then:
f(n+1,k) would come from
0 followed by f(n,k-1), together with
1 followed by f(n,k)
Each step would reduce the first index by 1, so the recursion should finish.
Don't know what anyone else thinks?
Topic archived. No new replies allowed.