11129 - An antiarithmetic permutation

[liulike]

Cool..

let n=13,
first consider 2 0.
now, you've 2 insert 4 and (4,2,0) forms an arithmetic progression. so, insert 4 in the middle of (2,0) so the sequence will be : 2 4 0.
then, it's 6. two arithmetic progression with 6 are (2,4,6) && (0,3,6).
since i put all odd numbers right of 0 and there cant be any (even,even,odd) or (even,odd,odd) progression so, the odd differenced triples can be ignored. so, 6 should be inserted between (2,4) & the sequence will be: 2 6 4 0.
now, u've 2 insert 8. among the two progressions (4,6,8 ) & (0,4,8 ) the (0,4,8 ) is the most differenced one. put 8 between (4,0). as 6 & 8 will be in two different sides of 4, there cant be (4,6,8 ). the sequence will be:2 6 4 8 0
thus, for 10 : 2 10 6 4 8 0 (between 2 and 6 )
thus, for 12: 2 10 6 4 12 8 0 (between 6 and 0 )

the odd numbers can be put on a same way : 2 10 6 4 12 8 0 1 9 5 3 11 7

[ziliang]

still dont quite understand..

but will try to figure it out

[ziliang]

wow~ got it. really a cool way.

but how do you prove it correct?

I mean how do you prove that correct when you insert 8 between 0 and 4 that 4 6 8 will not form a progression?

let n=13,
first consider 2 0.
now, you've 2 insert 4 and (4,2,0) forms an arithmetic progression. so, insert 4 in the middle of (2,0) so the sequence will be : 2 4 0.
then, it's 6. two arithmetic progression with 6 are (2,4,6) && (0,3,6).
since i put all odd numbers right of 0 and there cant be any (even,even,odd) or (even,odd,odd) progression so, the odd differenced triples can be ignored. so, 6 should be inserted between (2,4) & the sequence will be: 2 6 4 0.
now, u've 2 insert 8. among the two progressions (4,6,8 ) & (0,4,8 ) the (0,4,8 ) is the most differenced one. put 8 between (4,0). as 6 & 8 will be in two different sides of 4, there cant be (4,6,8 ). the sequence will be:2 6 4 8 0
thus, for 10 : 2 10 6 4 8 0 (between 2 and 6 )
thus, for 12: 2 10 6 4 12 8 0 (between 6 and 0 )

the odd numbers can be put on a same way : 2 10 6 4 12 8 0 1 9 5 3 11 7

[sclo]

wow~ got it. really a cool way.

but how do you prove it correct?

I mean how do you prove that correct when you insert 8 between 0 and 4 that 4 6 8 will not form a progression?

let n=13,
first consider 2 0.
now, you've 2 insert 4 and (4,2,0) forms an arithmetic progression. so, insert 4 in the middle of (2,0) so the sequence will be : 2 4 0.
then, it's 6. two arithmetic progression with 6 are (2,4,6) && (0,3,6).
since i put all odd numbers right of 0 and there cant be any (even,even,odd) or (even,odd,odd) progression so, the odd differenced triples can be ignored. so, 6 should be inserted between (2,4) & the sequence will be: 2 6 4 0.
now, u've 2 insert 8. among the two progressions (4,6,8 ) & (0,4,8 ) the (0,4,8 ) is the most differenced one. put 8 between (4,0). as 6 & 8 will be in two different sides of 4, there cant be (4,6,8 ). the sequence will be:2 6 4 8 0
thus, for 10 : 2 10 6 4 8 0 (between 2 and 6 )
thus, for 12: 2 10 6 4 12 8 0 (between 6 and 0 )

the odd numbers can be put on a same way : 2 10 6 4 12 8 0 1 9 5 3 11 7

There's a slight modification that is easy to prove why it works.
Recall that (even,even,odd) or (even,odd,odd) can't be an arithmetic sequence. First, initialize the list with 0 to n-1, then we consider moving all even numbers to the left of the list, and all odd numbers to the right of the list.
Now, recursively, compute the left half of the list (even) and right half of the list (odd). To compute the left half, we first divide each number by 2, then we would get a similar subproblem. To compute the right half, we subtract 1 and then divide each number by 2, then we would also get a similar subproblem. In order to print the correct output, we must remember the original numbers. The algorithm has runtime O(n log n). The reason why it works is because if a sequence is antiarithmetic, then multiplication and/or addition each term by a constant would make the sequence stay antiarithmetic (in other words, solution to subproblems are valid). And also (even,even,odd) and (even,odd,odd) can't be arithmetic, so the 2 recursively computed sequences could be concatenated to form a single sequence (in other words, the 2 subproblems are independent). I'm sure it is less than 30 lines of code.

I can't quite prove that sunny's algorithm is correct, but I'm quite sure that mine is correct from the above.

[sunny]

i admit that sclo's algorithm is smarter than mine.
but i can prove the correctness of my algo.
when inserting 8 between (4,0) there cant be any progression like (8,6,4) cuz 8 is on right of 4.
look between the numbers 6,8,10,12... are inserted. it's like: (2,4),(4,0),(2,6),(6,0).....(2,k),(k,0),(2,k+2),(k+2,0).......
as 8 is inserted between (4,0), 6 should be between (2,4). so, 6 is on left of 4. so, there cant be any progression like (4,6,8 ).

[boshkash1986]

thanks to sclo explanation of the problem I got AC and here is my explanation of sclo code with example if it could help

n = 10
first recursive call with seperation of even and odd to left and right
2 4 6 8 0 1 3 5 7 9
divide each even by 2 and each odd by ((odd-1)/2)
1 2 3 4 0 0 1 2 3 4
second recursive call for the left part(i will ignore the right part for simplicty (you will do exactly the same))
seperating even and odd
1 2 3 4 --- we get-----> 2 4 1 3
divide the each even and odd as described above
1 2 0 1
third recursive call on the even side
seperate the sides
1 2 ---we get ---> 2 1
and we end here for this branch of recursive call
so if we trace back the origin of the last two numbers (which are 2 and 1) we will find that they are 4 and 8 and so we get the antiarithemtic permutation

of course anyone can trace back the numbers to their origin
i hope i am clear and thanks again for sclo algo

[wallace]

I am difficulties to write the function !
can someone help me?
look:

pseudocode

void myfuction(int start, int end, int vecto){

if(end - start == 1)return;

separates_ side_even_ and_ odd();
myfuction(start,index_vector_even,even)
m = (length_even+length_odd)/2;
myfuction(m+1,index_vector_odd,odd)
join(even,odd);

}
thank you!