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

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?

[Walter Roberson]

What is a valid change? You say that d is the number of changes each time: does d give the number of bits that are flipped ?

[Bruno Luong]

Walter, look at his first question d is what he calls "number of flips", so yes the number of bits that change values.

[Yang Metin]

Does anyone have ideas?

Answer 1

[Bruno Luong]

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

[Yang Metin]

I sincerely hope you can explain the meaning of each variable.Especially how A is constructed.

In addition, the input vector is not necessarily all 1.

[Image Analyst]

But Yang, your subject line says "The shortest way to find the sequence of all 1s to all 0s". What does "all 1s" mean to you? To most of us, it means what Bruno said.

[Yang Metin]

Oh, you are right, I forgot the title I wrote. This is only an abstract model of mathematical modeling, there is no specific limit, I have been trying to find a more general method.

[Bruno Luong]

If you have an input of starting binary array different, (not entirely contain 1s), here is the modification to achieve that:

function B = FlipSequenceToZero(b, D)
% B = FlipSequenceToZero(bstart, D)
%
% Find a sequence of binary arrays, started from bstart to 0s array
% where the next array are obtained from current array by XOR of D-bytes
%
% INPUTS:
%   bstarts: 1 x N binary array (containing 0/1)
%   D: scalar, number of flip, D <= N
% OUTPUT:
%   b: M x N binary arrays
%   b(k,:) is an binary vector of the sequence as specified. 
%   b(1,:) is bstart and b(end,:) contains 0s.
%   NOTES: If no solution exists, b = [] is returned.
%          M is minimal is solution exists.
%
% Example:
%   bstart = [1 0 1 0 1 1 1 1 0 0 1 1 1];
%   B = FlipSequenceToZero(bstart, 7);
%   disp(char(B+'0'))
%
%   1010111100111
%   0101011111111
%   1010000011111
%   0000000000000
%
% Author: <brunoluong_at_yahoo_dot_findmycountry>

N = length(b);

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

G = graph(A);
i = sum(b==0)+1;
P = shortestpath(G,i,N+1);
M = length(P);
if M <= 1
    B = [];
    fprintf('No solution\n');
    return
end

% Build the binary arrays
% between two sucessive rows are D-bit flips
B = zeros(M,N);
D0 = (D - diff(P)) / 2;
for q = 1:M-1
    B(q,:) = b;
    d0 = D0(q);
    isb0 = b==0;
    b(myfind( isb0, d0)) = 1;
    d1 = D-d0;
    b(myfind(~isb0, d1)) = 0;
end
% B(M,:) = b; % no need to carry out, since the last b contains 0s

end % FlipSequenceToZero

%% Like FIND but overcome error for N == 0
function i = myfind(b, N)
if N > 0
    i = find(b, N);
else
    i = [];
end
end

Test

bstart = [1 0 1 0 1 1 1 1 0 0 1 1 1];
B = FlipSequenceToZero(bstart, 7);
disp(char(B+'0'))

Result

1010111100111
0101011111111
1010000011111
0000000000000

[Yang Metin]

I sincerely hope you can explain how matrix A is constructed.

[Bruno Luong]

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.

Answer 2

[Bruno Luong]

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.

[Yang Metin]

I don't know how to make a little change. Or to be more precise, I don't know how to change it.

There seems to be an algorithm "pruning", but I don't know how to write it.

[Bruno Luong]

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.

[Yang Metin]

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.