The shortest way to find the sequence of all 1s to all 0s
6 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?
3 Comments
Bruno Luong
on 24 Jul 2020
Walter, look at his first question d is what he calls "number of flips", so yes the number of bits that change values.
Accepted Answer
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
on 26 Jul 2020
Edited: 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.
More Answers (1)
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
Bruno Luong
on 25 Jul 2020
If you decide to compute the whole graph, which is awfully costly IMO, then you can find shorttest path simply by calling
P = shortestpath(G, s, t)
where s is your initial node having all 1s and t any node where you reach the target array having all 0s.
See Also
Categories
Find more on Creating and Concatenating Matrices in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!