How to reorder a vector one cell at a time?

I am looking to create a matrix by iteratively swapping one row with another in a vector. For example, I want to start with [1 1 3 4 1]' and end with

1 1 1 1 3 3

1 1 3 3 1 4

3 3 1 4 4 1

4 4 4 1 1 1

1 1 1 1 1 1

where each column is a different iteration and I am only moving a single 1 at a time. I was able to figure out a case with a single 1.

order = [1 3 4 1]'

for i = 1:3
    if order(i) == 1
        order([i i+1]) = order([i+1 i]);
        ord(:,i+1) = order;
    end
end  

[Walter Roberson]

There is no obvious rule for producing column 5, [3;1;4;1;1]. In the previous columns, the progress was always down towards the bottom, locating the first available 1 after the current row and doing the swap and then moving to the next row. But for column 5, you have gone back up to the top with no apparent rule that would clearly prevent you from endlessly swapping a pair of adjacent 1's.

[William Harris]

What I am trying to figure out is how to get past column 4. If I apply my for loop to the problem I only get to column 4. I am not sure how to loop back, look for the next 1 and begin the process of moving it down.

[James Tursa]

Isn't this just a variation of a bubble sort where you are only moving the 1's?

Answer 1

[David Hill]

order = [1 3 1 5 1 1 7 1 8 1 1 9 4 1]';
a=order([find(order~=1);find(order==1)]);
c=1;
while ~isequal(order(:,c),a)
  c=c+1;
  order(:,c)=order(:,c-1);
  for i = 1:size(order,1)-1
    if order(i,c) == 1&&order(i+1,c)~=1
        order(i:i+1,c) = order(i+1:-1:i,c);
        break;
    end
  end 
end

Answer 2

[Walter Roberson]

Okay, so the problem is that the rules are not exactly as you describe.

The algorithm

1. Start at the top of the column, and remember the fact that you started from the top
2. look down the column for the first 1
3. check to see if everything from that 1 to the bottom is 1
4. if so and you have marked that you started from the top, then you are done moving everything so exit the algorithm
5. if everything was 1 and you have not marked that you started from the top, then go back to step 1 (starting from the top again)
6. to get here, not everything from the 1 downward is a 1. unmark that you started from the top. Now bubble that 1 "downward" one row at a time, stopping when everything from the position of moved 1 to the end is all 1's
7. go back to the start of the column (you only reach this step if you were bubbling a 1 downward)

When you reach the end, all 1's will be at the bottom of the column.

Note: When you are bubbling a 1 downward, exchanging it with a different 1 is a valid step. That is why your second column looks the same as the first column: the 1 at the top got logically exchanged with the 1 below it, and column 3 is moving the 1 even further down.