4 views (last 30 days)

Show older comments

The sequence P has a total of N bits, given the initial state (0 or 1). The given number d is the number of changes each time. Find the least number of changes method process (including the process) from A to all 0 sequence.

For example: P=[1 1 1 1], d=2, then the shortest change sequence is [0 0 1 1]->[0 0 0 0].

Of course, there are also sequences that can never be changed successfully.

The code I wrote, it can only give all the results that can be changed, but not necessarily the least number of times. For example, A=[1 1 1 1 1 1 1 1 1 1 1 1], D=9. The correct result should be [0 0 0 0 0 0 0 0 0 1 1 1]->[1 1 1 1 1 1 0 0 0 0 0 0]->[0 0 0 1 1 1 1 1 1 1 1 1 1] ->[0 0 0 0 0 0 0 0 0 0 0 0].

This is the code I wrote:

clear

global LEN G H d

P=[1 1 1 1 1 1 1 1 1 1 1 1];

d=6;

LEN=length(P);

H=length(find(P==0));

G=graph();

G=G.addnode(num2str(P));

dd(P);

p=plot(G);

function dd(P)

global LEN G H d

C=nchoosek(1:LEN,d);

for i=1:length(C)

D=P;

D(C(i,:))=~D(C(i,:));

L=length(find(D==0));

if ~any(H==L)

H=[H L];

G=G.addnode(num2str(D));

G=G.addedge(num2str(P),num2str(D));

dd(D);

end

end

end

How can I change the code to make it the shortest or is there any new way to solve this problem?

Bruno Luong
on 25 Jul 2020

Edited: Bruno Luong
on 26 Jul 2020

Build full Graph and select the shortest path

N = 12; % number of bits

D = 9; % number of flips for each step, <= N

E0 = (0:N)+(-N:0)';

D0 = (0:N)-(0:N)';

A = mod(D0,2)==mod(D,2) & abs(D0)<=D & abs(E0)<=N-D;

P = shortestpath(graph(A),1,N+1);

if length(P) <= 1

fprintf('No solution\n');

return

end

% Build the binary arrays

% between two sucessive rows are D-bit flips

B = zeros(length(P),N);

B(1,:) = 1;

i = 1;

b = B(1,:);

for q=2:length(P)

j = P(q);

d0 = (D+i-j)/2;

i0 = find(b==0);

i1 = find(b==1);

b(i0(1:d0)) = 1;

b(i1(1:(D-d0))) = 0;

B(q,:) = b;

i = j;

end

% Print the result

char(B+'0')

Binary arrays transformation, between two sucessive arrays are 9 bits flips

111111111111

000000000111

111111000000

000111111111

000000000000

Bruno Luong
on 26 Jul 2020

As I already gave you a hint in another post:

"'Everytime you flip d elements, you change the number of 0s by d, d-2, d-4, ..., 0/1 (depending on d is odd or even), and might be a subset of the above."

Short answer the A matrix translates just this sentense in math expression. The "d, d-2, d-4 ..." is ensured by "mod(D0,2)==mod(D,2)" and "subset" by the rest of expression of A.

Long answer

A matrix is the "transition" matrix to pass from one sequence of binary array to another by flipping D-bits.

It's possible to determine if the flipping is possible only from the number of 0s and 1s in two sequences.

I assume the starting array contains on the 0s are in the head and all the 1s are in the tails, for simplification of the explanation.

The number N0, N1, D0, D1 are defined as following:

array_s = 00 .... 00000001111 .... 1111

<------N0------><------N1------->

Flip D <------------>

<--D0--><-D1->

array_t = 00....001111111100000011...1111

P0, P1 are defined as the number of 0s of the array_t.

From that we have the following relationships (exercice for you)

P0 = N0 - D0 + D1

P1 = N1 + D1 - D0

N0 + N1 = N

D0 + D1 = D

0 <= D1 <= N1 <= N

0 <= D0 <= N0 <= N

They are not independents. For example the any of the equality from the four equations can be obtained from the other three.

From that I derive actually the equivalent conditions on N0/P0 so that this six relationship have solutions, and comes up with what you see in A, where N0/P0 are along column and row index of A. I don't go into calculation details, but to give you a flavor, D0 can by computed from N0/P0 by

D0 = (D - P0 + N0) / 2.

In the MATLAB code, this expression is somewhere on the for-loop.

Since D0 is integer, that means (D - P0 - N0) must be even, thus the modulo(...,2) condition, (which is what I already said that the number of 0s or 1s change is "d, d-2, d-4 ...".)

The above can rewrite as

2*D0 = D - P0 + N0.

and since D0 <= N0

We get

D - P0 + N0 <= 2*N0

Meaning

D <= P0 + N0 := S0

You find this condition in the construction of A.

I let you figure out all the rest.

Bruno Luong
on 24 Jul 2020

Edited: Bruno Luong
on 24 Jul 2020

For the shortest, you would probably want to take a look of dynamic programming.

A standard problem quite similar to yours is the Coin Change problem: how to pay a given an amount from a set of coins. Here is nice tutorial of Coin Change

In your case the number of 0s is 0 at the start, and you want it to reach N - the length of the array - in mimum number of steps.

Everytime you flip d elements, you change the number of 0s by d, d-2, d-4, ..., 0/1 (depending on d is odd or even), and might be a subset of the above.

It looks pretty much to me you might be able to use the coin change technique with few modifications.

Before you ask, no I won't give you the code. Let you rather study the dynamic programming technique.

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!