Create combinations of a binary vector
A slightly faster version of Marat's answer:
f.roland <- function(n, m) {
ind <- combn(seq_len(n), m)
ind <- t(ind) + (seq_len(ncol(ind)) - 1) * n
res <- rep(0, nrow(ind) * n)
res[ind] <- 1
matrix(res, ncol = n, nrow = nrow(ind), byrow = TRUE)
}
all.equal(f.2(16, 8), f.roland(16, 8))
#[1] TRUE
library(rbenchmark)
benchmark(f(16,8),f.2(16,8),f.roland(16,8))
# test replications elapsed relative user.self sys.self user.child sys.child
#2 f.2(16, 8) 100 5.693 1.931 5.670 0.020 0 0
#3 f.roland(16, 8) 100 2.948 1.000 2.929 0.017 0 0
#1 f(16, 8) 100 8.287 2.811 8.214 0.066 0 0
R - generate all possible pairwise combinations of binary vectors
Something like this?
n <- 3
g <- 2 # g must be < n
m <- combn(n, g)
mm <- as.numeric(m)
mat <- matrix(0, nrow = g * ncol(m), ncol = n)
mat[ cbind(1:nrow(mat), mm)] <- 1
mat
# [,1] [,2] [,3]
#[1,] 1 0 0
#[2,] 0 1 0
#[3,] 1 0 0
#[4,] 0 0 1
#[5,] 0 1 0
#[6,] 0 0 1
# mat is half the answer :)
# the other half is
mat[nrow(mat):1, ]
# [,1] [,2] [,3]
#[1,] 0 0 1
#[2,] 0 1 0
#[3,] 0 0 1
#[4,] 1 0 0
#[5,] 0 1 0
#[6,] 1 0 0
soln <- rbind(mat, mat[nrow(mat):1, ])
# as suggested by the OP to split the soln
d <- split(data.frame(soln), rep(1:(nrow(soln)/g), each=g))
R: all possible combinations of a binary vector of length n, where only one value is “1” in each combination of m
This is very similar to your other question. In my answer to that question, we see that rephrasing the question, makes it much easier to attack. So for this question, we can reduce it to: "How to generate all pairwise permutations of powers of 2 with repeats?"
We can use almost exactly the same setup as before, only this time we set the argument repeats.allowed = TRUE.
library(gtools)
bitPairwise2 <- function(numBits, groupSize) {
t(sapply(t(permutations(numBits + 1, groupSize,
c(0, 2^(0:(numBits-1))), repeats.allowed = TRUE)),
function(x) {as.integer(intToBits(x))})[1:numBits, ])
}
bitPairwise2(2,2)
[,1] [,2]
[1,] 0 0 ## (00,00)
[2,] 0 0
[3,] 0 0 ## (00,10)
[4,] 1 0
[5,] 0 0 ## (00,01)
[6,] 0 1
[7,] 1 0 ## (10,00)
[8,] 0 0
[9,] 1 0 ## (10,10)
[10,] 1 0
[11,] 1 0 ## (10,01)
[12,] 0 1
This function generalizes to any number of bits as well as any number of groups. For example, all possible 3-tuples of 3 bits is given by:
## first 9 groups
bitPairwise2(3, 3)[1:27, ]
[,1] [,2] [,3]
[1,] 0 0 0 ## (000,000,000)
[2,] 0 0 0
[3,] 0 0 0
[4,] 0 0 0 ## (000,000,100)
[5,] 0 0 0
[6,] 1 0 0
[7,] 0 0 0 ## (000,000,010)
[8,] 0 0 0
[9,] 0 1 0
[10,] 0 0 0 ## (000,000,001)
[11,] 0 0 0
[12,] 0 0 1
[13,] 0 0 0 ## (000,100,000)
[14,] 1 0 0
[15,] 0 0 0
[16,] 0 0 0 ## (000,100,100)
[17,] 1 0 0
[18,] 1 0 0
[19,] 0 0 0 ## (000,100,010)
[20,] 1 0 0
[21,] 0 1 0
[22,] 0 0 0 ## (000,100,001)
[23,] 1 0 0
[24,] 0 0 1
[25,] 0 0 0 ## (000,010,000)
[26,] 0 1 0
[27,] 0 0 0
And here are the last 9 groups:
a <- bitPairwise2(3, 3)[166:192, ]
row.names(a) <- 166:192
a
[,1] [,2] [,3]
166 0 0 1 ## (001,100,001)
167 1 0 0
168 0 0 1
169 0 0 1 ## (001,010,000)
170 0 1 0
171 0 0 0
172 0 0 1 ## (001,010,100)
173 0 1 0
174 1 0 0
175 0 0 1 ## (001,010,010)
176 0 1 0
177 0 1 0
178 0 0 1 ## (001,010,001)
179 0 1 0
180 0 0 1
181 0 0 1 ## (001,001,000)
182 0 0 1
183 0 0 0
184 0 0 1 ## (001,001,100)
185 0 0 1
186 1 0 0
187 0 0 1 ## (001,001,010)
188 0 0 1
189 0 1 0
190 0 0 1 ## (001,001,001)
191 0 0 1
192 0 0 1
If you need the output in a list, try this:
test <- bitPairwise2(4, 3)
numGroups <- nrow(test)/3
makeGroupList <- function(mat, nG, groupSize) {
lapply(1:nG, function(x) {
s <- groupSize*(x-1) + 1
e <- s + (groupSize - 1)
mat[s:e, ]
})
}
makeGroupList(test, numGroups, 3)
[[1]]
[,1] [,2] [,3] [,4]
[1,] 0 0 0 0
[2,] 0 0 0 0
[3,] 0 0 0 0
[[2]]
[,1] [,2] [,3] [,4]
[1,] 0 0 0 0
[2,] 0 0 0 0
[3,] 1 0 0 0
[[3]]
[,1] [,2] [,3] [,4]
[1,] 0 0 0 0
[2,] 0 0 0 0
[3,] 0 1 0 0
. . . . .
. . . . .
. . . . .
Drawing conditional combinations of a binary vector one by one
What the OP is after is an iterator. If we were to do this properly, we would write a class in C++ with a get_next method, and expose this to R. As it stands, with base R, since everything is passed by value, we must call a function on our object-to-be-updated and reassign the object-to-be-updated every time.
Here is a very crude implementation:
get_next <- function(comb, v, m) {
s <- seq(1L, length(comb), length(v))
e <- seq(length(v), length(comb), length(v))
last_comb <- rev(v)
can_be_incr <- sapply(seq_len(m), function(x) {
!identical(comb[s[x]:e[x]], last_comb)
})
if (all(!can_be_incr)) {
return(FALSE)
} else {
idx <- which(can_be_incr)[1L]
span <- s[idx]:e[idx]
j <- which(comb[span] == 1L)
comb[span[j]] <- 0L
comb[span[j + 1L]] <- 1L
if (idx > 1L) {
## Reset previous maxed out sections
for (i in 1:(idx - 1L)) {
comb[s[i]:e[i]] <- v
}
}
}
return(comb)
}
And here is a simple usage:
m <- 3L
v <- as.integer(c(1,0,0))
comb <- rep(v, m)
count <- 1L
while (!is.logical(comb)) {
cat(count, ": ", comb, "\n")
comb <- get_next(comb, v, m)
count <- count + 1L
}
1 : 1 0 0 1 0 0 1 0 0
2 : 0 1 0 1 0 0 1 0 0
3 : 0 0 1 1 0 0 1 0 0
4 : 1 0 0 0 1 0 1 0 0
5 : 0 1 0 0 1 0 1 0 0
6 : 0 0 1 0 1 0 1 0 0
7 : 1 0 0 0 0 1 1 0 0
8 : 0 1 0 0 0 1 1 0 0
9 : 0 0 1 0 0 1 1 0 0
10 : 1 0 0 1 0 0 0 1 0
11 : 0 1 0 1 0 0 0 1 0
12 : 0 0 1 1 0 0 0 1 0
13 : 1 0 0 0 1 0 0 1 0
14 : 0 1 0 0 1 0 0 1 0
15 : 0 0 1 0 1 0 0 1 0
16 : 1 0 0 0 0 1 0 1 0
17 : 0 1 0 0 0 1 0 1 0
18 : 0 0 1 0 0 1 0 1 0
19 : 1 0 0 1 0 0 0 0 1
20 : 0 1 0 1 0 0 0 0 1
21 : 0 0 1 1 0 0 0 0 1
22 : 1 0 0 0 1 0 0 0 1
23 : 0 1 0 0 1 0 0 0 1
24 : 0 0 1 0 1 0 0 0 1
25 : 1 0 0 0 0 1 0 0 1
26 : 0 1 0 0 0 1 0 0 1
27 : 0 0 1 0 0 1 0 0 1
Note, this implementation will be memory efficient, however it will be very slow.
Generate all possible binary vectors of length n in R
n = 3
expand.grid(replicate(n, 0:1, simplify = FALSE))
# Var1 Var2 Var3
#1 0 0 0
#2 1 0 0
#3 0 1 0
#4 1 1 0
#5 0 0 1
#6 1 0 1
#7 0 1 1
#8 1 1 1
Create all possible combiations of 0,1, or 2 1s of a binary vector of length n
This algorithm might be be more effective than that based on expand.grid:
n <- 3
z <- rep(0,n)
answer <- t(apply(combn(0:n,2),2,function(k) {z[k]=1;z}))
# [,1] [,2] [,3]
# [1,] 1 0 0
# [2,] 0 1 0
# [3,] 0 0 1
# [4,] 1 1 0
# [5,] 1 0 1
# [6,] 0 1 1
[EDIT] I noticed that my original solution misses a trivial case of all zeros,
which can be easily fixed:
rbind(unname(z),answer)
# [,1] [,2] [,3] [,4]
# [1,] 0 0 0 0
# [2,] 1 0 0 0
# [3,] 0 1 0 0
# [4,] 0 0 1 0
# [5,] 0 0 0 1
# [6,] 1 1 0 0
# [7,] 1 0 1 0
# [8,] 1 0 0 1
# [9,] 0 1 1 0
# [10,] 0 1 0 1
# [11,] 0 0 1 1
All combinations of a binary number where only certain bits can change
So, there is alsready an answer. But just dumped code, without any explanation. Not good. Anyway...
I would like to add an answer with a different approach, and explain the steps.
Basically, if you want to have all combinations of a binary number, then you could simply "count" or "increment by one". Example for a 3 bit value. This would be decimal 0, 1, 2, 3, 4, 5, 6, 7 and binary 000, 001, 010, 011, 100, 101, 110, 111. You see that it is simple counting.
If we think far back to school days, where we learned boolean algebra and a little bit of automata theory, then we rember how this counting operation is done on low level. We always flip the least significant bit, and, if there is a transition from 1 to 0, then we basically had an overflow and must also flip the next bit. That's the principle of a binary adder. We want to add always 1 in our example. So, add 1 to 0, result is 1, then no overflow. But add 1 to 1, result is 0, then we we have an overlow and must add 1 to the next bit. This will effectively flip the next bit, and so on and so on.
The advantage of this method is, that we do not always need to operate on all bits. So, the complexity is not O(n), but rather O(log n).
Additional advantage: It fits very good to your request for using a std::bitset.
3rd advantage, and maybe not that obvious: You can decouple the task of calculating the next combination from the rest of your program. No need to integrate your real-task-code in such a function. That is also the reason, why std::next_permutation is implemented like this.
And, the algorithms desribed above works for all values, no sorting or something necessary.
That part was for the algorithm you have asked for.
Next part is for your request that only certain bits can change. Of course, we need to specify these bits. And because your are working with std::bitset masking is no solution here. The better approach is to use indices. Meaning, give the bit positions of the bits that are allowed to be changed.
And then we can use the above described algorithm, with just one additional indirection. So, we do not use bits[pos], but bits[index[pos]].
The indices can easily be stored in a std::vector using an initializer list. We can also derive the indices-vector from a string or whatever. I used a std::string as example.
All the above will result in some short / compact code, with just a few lines and is easy to understand. I also added some driver code that makes use of this function.
Please see:
#include <iostream>
#include <vector>
#include <string>
#include <bitset>
#include <algorithm>
#include <cassert>
constexpr size_t BitSetSize = 32U;
void nextCombination(std::bitset<BitSetSize>& bits, const std::vector<size_t>& indices) {
for (size_t i{}; i < indices.size(); ++i) {
// Get the current index, and check, if it is valid
if (const size_t pos = indices[i]; pos < BitSetSize) {
// Flip bit at lowest positions
bits[pos].flip();
// If there is no transition of the just flipped bit, then stop
// If there is a transition from high to low, then we need to flip the next bit
if (bits.test(pos))
break;
}
}
}
// Some driver code
int main() {
// Use any kind of mechanism to indicate which index should be changed or not
std::string mask{ "x00x0000x000000x00x00x000x000x" };
// Here, we will store the indices
std::vector<size_t> index{};
// Populated the indices vector from the string
std::for_each(mask.crbegin(), mask.crend(), [&, i = 0U](const char c) mutable {if ('x' == c) index.push_back(i); ++i; });
// The bitset, for which we want to calculate the combinations
std::bitset<BitSetSize> bits(0);
// Play around
for (size_t combination{}; combination < (1 << (index.size())); ++combination) {
// This is the do something
std::cout << bits.to_string() << '\n';
// calculate the next permutation
nextCombination(bits, index);
}
return 0;
}
This software has been compiled wth MSVC 19 Community Edition using C++17
If you should have additional questions or need more clarifications, then I am happy to answer
How to get all combination of n binary value?
Use itertools.product
import itertools
lst = list(itertools.product([0, 1], repeat=3))
This will yield a list of tuples (see here)
You can easily change this to use a variable repeat:
n = 3
lst = list(itertools.product([0, 1], repeat=n))
If you need a list of lists, then you can use the map function (thanks @Aesthete).
lst = map(list, itertools.product([0, 1], repeat=n))
Or in Python 3:
lst = list(map(list, itertools.product([0, 1], repeat=n)))
# OR
lst = [list(i) for i in itertools.product([0, 1], repeat=n)]
Note that using map or a list comprehension means you don't need to convert the product into a list, as it will iterate through the itertools.product object and produce a list.
R: Get all combinations of p binary variables
OK, found it:
p <- 3
l <- rep(list(0:1), p)
expand.grid(l)
From here:
Generate list of all possible combinations of elements of vector
Related Topics
Rbindlist Data.Tables with Different Number of Columns
Cast String Directly to Idatetime
Counting Occurrence of Particular Letter in Vector of Words in R
How to 'Compress' an Lm() Object for Later Prediction
How to Create a Bar and Line Plot with R Dygraphs
Rhtml: Warning: Conversion Failure on '<Var>' in 'Mbcstosbcs': Dot Substituted for <Var>
R Xts: .001 Millisecond in Index
Using Variable Value as Column Name in Data.Frame or Cbind
How to Increase Smoothness of Spheres3D in Rgl
Match Two Columns with Two Other Columns
R - Svd() Function - Infinite or Missing Values in 'X'
How to Underline Text in a Plot Title or Label? (Ggplot2)
How to Place Legends at Different Sides of Plot (Bottom and Right Side) with Ggplot2
Ggplot2: Problem with X Axis When Adding Regression Line Equation on Each Facet