Shifting the bit in the array

General Usage
1

Hello everyone, I am looking forward to the advice about this problem. In the initial state, I have:

G = 1
Z = [0, 0, 0, 0]

Then, with the increasing value of G, Z will also be updated as follows:

G = 2                    G = 6                    G = 10                    G = 14
Z = [0, 0, 0, 1]         Z = [0, 0, 1, 1]         Z = [1, 0, 1, 0]          Z = [1, 1, 0, 1]

G = 3                    G = 7                    G = 11                    G = 15
Z = [0, 0, 1, 0]         Z = [0, 1, 0, 1]         Z = [1, 1, 0, 0]          Z = [1, 1, 1, 0]

G = 4                    G = 8                    G = 12                    G = 16
Z = [0, 1, 0, 0]         Z = [0, 1, 1, 0]         Z = [0, 1, 1, 1]          Z = [1, 1, 1, 1]

G = 5                    G = 9                    G = 13
Z = [1, 0, 0, 0]         Z = [1, 0, 0, 1]         Z = [1, 0, 1, 1]

The code that I have written so far is:

n = 4
a = [1, 0, 1, 0]
b = [1, 2]
g = 1
while g <= 2^n
    z = [0, 0, 0, 0]
    c = zeros(n)
    g += 1
    for i in 1 : n
        c[i] = xor(a[i], z[i]
    end
    sum_c = sum(Base.Fix1(getindex, a), b) #(credit to @Dan in my previous question)
    if sum_c == 0
        res = c
    else
        # I think this is the position for updating the value of z
    end
end

I am looking forward to any advice.

2

What are you looking to do with all these binary vectors? The simplest thing to me would be something like

for i in 1:2^n
   v = int_to_bitvector(i)
   # do stuff
end

but it allocates more (and I’m not sure how to implement int_to_bitvector but I’m willing to bet it’s easy enough)

1 Like
3

One thing to consider is if you even need the bitvector in the first place. A UInt is already a pretty good bit vector and won’t have any allocations.

4 Likes
4

I’m still trying to understand the pattern. At first, I thought you might be trying to do something like this.

julia> Gs = 1:13
1:13

julia> Z_G(G) = reverse(digits(G-1, base=2, pad=4))
Z_G (generic function with 1 method)

julia> zip(Gs, Z_G.(Gs)) |> collect
13-element Vector{Tuple{Int64, Vector{Int64}}}:
 (1, [0, 0, 0, 0])
 (2, [0, 0, 0, 1])
 (3, [0, 0, 1, 0])
 (4, [0, 0, 1, 1])
 (5, [0, 1, 0, 0])
 (6, [0, 1, 0, 1])
 (7, [0, 1, 1, 0])
 (8, [0, 1, 1, 1])
 (9, [1, 0, 0, 0])
 (10, [1, 0, 0, 1])
 (11, [1, 0, 1, 0])
 (12, [1, 0, 1, 1])
 (13, [1, 1, 0, 0])

Maybe this is useful to you as a hint.

1 Like
5

Thank you very much for your reply, @gdalle. I am looking for an array c that has sum_c = 0 (from line 12). This array is obtained by XOR between arrays a and z, and if sum_c is not 0, the operation is continued with g = 2 and z = [0, 0, 0, 1].

7

Thank you very much for the suggestion, @Oscar_Smith. I will search for information about UInt.

Also for the reply from @mkitti, the pattern is first we start with 0 of 1s in the array z

(1, [0, 0, 0, 0])

Then only 1 of 1s in the array

(2, [0, 0, 0, 1])
(3, [0, 0, 1, 0])
(4, [0, 1, 0, 0])
(5, [1, 0, 0, 0])

After that 2 of 1s in the array

(6, [0, 0, 1, 1])
(7, [0, 1, 0, 1])
(8, [0, 1, 1, 0])
(9, [1, 0, 0, 1])
(10, [1, 0, 1, 0])
(11, [1, 1, 0, 0])

Next is 3 of 1s in the array

(12, [0, 1, 1, 1])
(13, [1, 0, 1, 1])
(14, [1, 1, 0, 1])
(15, [1, 1, 1, 0])

And last is all 1s

(16, [1, 1, 1, 1])

If there are any suggestions, feel free to inform me.

8

Does it have to be in this order? Cause if you shuffle it you get exactly what it means to count in binary. And Oscar’s suggestion is simply due to the fact that (unsigned) integers are represented in binary on any machine

1 Like
9

Yes, it does, because the array z will be assumed to be useless when it has so many bit 1s. I am sorry for being so demanding, but it is in the article that I read. :cry:

10

Interestingly this sequence (when interpreted as binary) never occurs at the start of any sequence in OEIS.
Which suggests no simple formula will yield it.

11

Maybe using existing Combinatorics package can help:

julia> using Combinatorics

julia> sparsevecs(n,k) = 
  [ntuple(i-> i∈b, n) for t in 1:k for b in combinations(1:n, t)]
sparsevecs (generic function with 1 method)

julia> sparsevecs(4,4)
15-element Vector{NTuple{4, Bool}}:
 (1, 0, 0, 0)
 (0, 1, 0, 0)
 (0, 0, 1, 0)
 (0, 0, 0, 1)
 (1, 1, 0, 0)
 (1, 0, 1, 0)
 (1, 0, 0, 1)
 (0, 1, 1, 0)
 (0, 1, 0, 1)
 (0, 0, 1, 1)
 (1, 1, 1, 0)
 (1, 1, 0, 1)
 (1, 0, 1, 1)
 (0, 1, 1, 1)
 (1, 1, 1, 1)

julia> sparsevecs(4,1)
4-element Vector{NTuple{4, Bool}}:
 (1, 0, 0, 0)
 (0, 1, 0, 0)
 (0, 0, 1, 0)
 (0, 0, 0, 1)

If generating the whole output is too much memory, then the same method can be used to generate the tuples one by one for iteration.

1 Like
12

I also don’t see any pattern in it. If you only need it for G ∈ {1, ..., 16} , you might hard-code it:

const table = [0, 1, 2, 4, 8, 3, 5, 6, 9, 10, 12, 7, 11, 13, 14, 15]
get_Z(G) = reverse!(digits(table[G], base=2, pad=4))

julia> for i in 1:16
           println(i, " => ", get_Z(i))
       end
1 => [0, 0, 0, 0]
2 => [0, 0, 0, 1]
3 => [0, 0, 1, 0]
4 => [0, 1, 0, 0]
5 => [1, 0, 0, 0]
6 => [0, 0, 1, 1]
7 => [0, 1, 0, 1]
8 => [0, 1, 1, 0]
9 => [1, 0, 0, 1]
10 => [1, 0, 1, 0]
11 => [1, 1, 0, 0]
12 => [0, 1, 1, 1]
13 => [1, 0, 1, 1]
14 => [1, 1, 0, 1]
15 => [1, 1, 1, 0]
16 => [1, 1, 1, 1]
3 Likes
13

I think the pattern is increasing number of 1s (inside blocks of similar weight, the order might be less crucial for the application).

14

Well, if you hardcode it (which is IMHo the right option), you might even hardcode the translation:

const Z_table = get_Z.(1:16)

and then call it via Z_table[G].

2 Likes
15

Thank you very much for the comment, @oxinabox. I just want to arrange the array based on the number of 1s in it.

Also, thank you very much for the advice, @Dan. I have tried to implement your advice, but I am confused about generating the tuples one by one. I think I need more practice for it. :grin:

And, thank you very much for the advice, @barucden. Your advice can be used to solve an array with length 4. My task is to create a simulation for the array with length 1024, and when I generate array Z, it will return nothing (which I assume Julia did not generate due to the “Out of Memory error” that I got when I tried to generate an array with length 2^32).

Just like @Dan said, the pattern is not important. As long as the arrays have the same number of 1s, then they are considered to have the same “probability” (in my previous statement, I called it “useful”)…

Thank you very much for the advice, @lrnv. But it won’t work when I change the length of the array.

P.S.: I am sorry for the late reply, I really wanted to reply 2 hours ago, but due to the restriction for newly created accounts, I have reached the limit for replying posts and need to wait to post another reply.

16

I see. Then the solution by @Dan is correct. However, the number of such vectors is huuuge for N=1024:

julia> sum(k -> binomial(big(1024), k), 0:1024)
179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137216

Not really enumerable.

EDIT: Ugh, yeah, the easier formula for the number of such vectors is obviously 2^N :slight_smile:

1 Like
17

That’s easy then, just sort it:

julia> function bitarraysort(n)
           nums = collect(0:n-1)
           sort!(nums, by=x -> (count_ones(x), x))
           map(1:n) do i
               pad = Base.ndigits0z(n-1, 2)
               return i => reverse!(digits(nums[i]; base=2, pad))
           end
       end
bitarraysort (generic function with 1 method)

julia> bitarraysort(16)
16-element Vector{Pair{Int64, Vector{Int64}}}:
  1 => [0, 0, 0, 0]
  2 => [0, 0, 0, 1]
  3 => [0, 0, 1, 0]
  4 => [0, 1, 0, 0]
  5 => [1, 0, 0, 0]
  6 => [0, 0, 1, 1]
  7 => [0, 1, 0, 1]
  8 => [0, 1, 1, 0]
  9 => [1, 0, 0, 1]
 10 => [1, 0, 1, 0]
 11 => [1, 1, 0, 0]
 12 => [0, 1, 1, 1]
 13 => [1, 0, 1, 1]
 14 => [1, 1, 0, 1]
 15 => [1, 1, 1, 0]
 16 => [1, 1, 1, 1]

Whether a closed-form solution for this sequence exists, I don’t know :slight_smile: I suspect it doesn’t, because the bit-representation for 17 introduces another bit, which would need to find its place after 5. If you take a look at the numbers the bits represent:

julia> function bitarraysort(n)
           nums = collect(0:n-1)
           sort!(nums, by=x -> (count_ones(x), x))
           map(1:n) do i
               pad = Base.ndigits0z(n-1, 2)
               return nums[i]+1 => reverse!(digits(nums[i]; base=2, pad))
           end
       end
bitarraysort (generic function with 1 method)

julia> bitarraysort(17)
17-element Vector{Pair{Int64, Vector{Int64}}}:
  1 => [0, 0, 0, 0, 0]
  2 => [0, 0, 0, 0, 1]
  3 => [0, 0, 0, 1, 0]
  5 => [0, 0, 1, 0, 0]
  9 => [0, 1, 0, 0, 0]
 17 => [1, 0, 0, 0, 0]
  4 => [0, 0, 0, 1, 1]
...

You can see that the whole sequence changes depending on the maximum value you’re looking for.

1 Like
18

If all the vectors with the same nb of 1s are equivalent to you, can’t you exploit that to avoid generating them all?

1 Like
19

As you said, @barucden. The vector is huge and I am still trying to implement the advice from @Dan

Thank you very much for your advice, @Sukera. I have tried it and your advice is working for n = 1024. Right now, I am trying to figure out how to generate them one by one for each step.

Unfortunately, I can’t ignore even one of the array z, @gdalle. Because there is a possibility that within the array I get the correct result. For example:

a = [0, 1, 0, 1]
b = [1, 2] # I need a[1] + a[2] = 0


z = [0 0 0 1; 0 0 1 0; 0 1 0 0; 1 0 0 0]
for I in 1 : 4
    c = xor(a[i], z[i]
end
# if I want c = [0 0 0 1], then I need z = [1 0 0 0] to make it happen

But I also can’t generate c = [0 0 0 1] directly because there is an operation after xor-ing a and z, and the result of that operation will be checked to see whether position b of it is equal to 0.

N = 4
a = [1, 0, 0, 1]
b = [1, 2]
z = [0 0 0 0; 0 0 0 1; 0 0 1 0; 0 1 0 0; 1 0 0 0; ...; 1 1 1 0; 1 1 1 1]
c = zeros(N)
g = 1
res = []
while g <= 1 : 2^N
    for j in 1 : N
        c[j] = xor(a[j], z[i, j]
    end
    d = another_operation(res)
    sum_d = sum(Base.Fix1(getindex, d), b)
    if sum_d == 0
        res = sum_d
        g = 2^N
    else
        g += 1
    end
end

I am sorry because I can’t explain it very well.

20

To generate the tuples one by one:

using Combinatorics

sparsevecs_itr(n,k) = 
  Iterators.map(b -> ntuple(i -> i ∈ b, n), (b for t in 0:k for b in combinations(1:n, t)))

# sparsevecs_itr returns an iterator for all n-tuples up to weight k

For example:

julia> for t in sparsevecs_itr(4,2)
           println("sum of ", 1 .* t, " = ", sum(t))
           # do something interesting with t here
       end
sum of (0, 0, 0, 0) = 0
sum of (1, 0, 0, 0) = 1
sum of (0, 1, 0, 0) = 1
sum of (0, 0, 1, 0) = 1
sum of (0, 0, 0, 1) = 1
sum of (1, 1, 0, 0) = 2
sum of (1, 0, 1, 0) = 2
sum of (1, 0, 0, 1) = 2
sum of (0, 1, 1, 0) = 2
sum of (0, 1, 0, 1) = 2
sum of (0, 0, 1, 1) = 2
1 Like
21

Thank you very much for the explanation, @Dan. I have tried to create like this:

n = 2
N = 2 ^ n
function spars_noise(n, k)
    [ntuple(i -> i∈b, n) for t in 1:k for b in combinations(1:n, t)]
end
for i in 1:N
    z = spars_noise(N, i)
    println("i = ", i)
    println("z = ", z)
end

The output is

i = 1
z = NTuple{4, Bool}[(1, 0, 
0, 0), (0, 1, 0, 0), (0, 0, 1, 0), (0, 0, 0, 1)]
i = 2
z = NTuple{4, Bool}[(1, 0, 0, 0), (0, 1, 0, 0), (0, 0, 1, 0), (0, 0, 0, 1), (1, 1, 0, 0), (1, 0, 1, 0), (1, 0, 0, 1), (0, 1, 1, 0), (0, 1, 0, 1), (0, 0, 1, 1)]
i = 3
z = NTuple{4, Bool}[(1, 0, 0, 0), (0, 1, 0, 0), (0, 0, 1, 0), (0, 0, 0, 1), (1, 1, 0, 0), (1, 0, 1, 0), (1, 0, 0, 1), (0, 1, 1, 0), (0, 1, 0, 1), (0, 0, 1, 1), (1, 1, 1, 0), (1, 1, 0, 
1), (1, 0, 1, 1), (0, 1, 1, 1)]
i = 4
z = NTuple{4, Bool}[(1, 0, 0, 0), (0, 1, 0, 0), (0, 0, 1, 0), (0, 0, 0, 1), (1, 1, 0, 0), (1, 0, 1, 0), (1, 0, 0, 1), (0, 1, 1, 0), (0, 1, 0, 1), (0, 0, 1, 1), (1, 1, 1, 0), (1, 1, 0, 1), (1, 0, 1, 1), (0, 1, 1, 1), (1, 1, 1, 1)]

Is there any way to configure that number of 1s in array z = i?

The advice from @Sukera also returns OutOfMemoryError() when I tried n = 2^32. Sorry for the previous comment where I claimed that I can do simulation with large n. Maybe previously I do simulation with n = 1024 instead of n = 2^(1024).