MATLAB Answers

The shortest way to find the sequence of all 1s to all 0s

4 views (last 30 days)
Yang Metin
Yang Metin on 24 Jul 2020
Edited: Bruno Luong on 26 Jul 2020
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?
  3 Comments

Sign in to comment.

Accepted Answer

Bruno Luong
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
  6 Comments
Bruno Luong
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.

Sign in to comment.

More Answers (1)

Bruno Luong
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.
  3 Comments
Yang Metin
Yang Metin on 25 Jul 2020
My code generates a tree. The shortest path can be seen directly without using a function. The important thing is that the tree (graph) is constructed incorrectly. Maybe you are not running the code.

Sign in to comment.

Tags

Community Treasure Hunt

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

Start Hunting!