/* Average avoiding in Picat. From Stack Overflow "Arrange an array such that the average of 2 numbers does not lie between them" http://stackoverflow.com/questions/19345090/arrange-an-array-such-that-the-average-of-2-numbers-does-not-lie-between-them """ As the question says, find an algorithm to arrange the array. This was a Facebook interview question. The average needs to be exact. We do not round of, take floor or ceil of the average. Edit : To quote an example, if the numbers are 1,2,5,9, then the arrangement {1,9,2,5} is valid but {1,5,9,2} is not since average of 1 and 9 is 5 and lies between them. Why is everybody downvoting this? """ Note: This question don't say anything about the sequence, ie. - if it contains all the integers from min..max - if the integers are distinct or not, i.e. if duplicates are allowed This Picat model is a general approach for solving both the free version and and the restricted 0..N-1 variant. [Later: It seems that the 0..N-1 (or 1..N) problem is quite known: See - http://cs.stackexchange.com/questions/13857/order-a-list-of-whole-numbers-so-that-no-two-numbers-have-the-average-of-them-si """ Here's a simple recursive construction for the more restrictive version of the problem. .... """ - http://math.stackexchange.com/questions/3060/arrangement-of-numbers """ Assume the inductive hypothesis that it is true for lists smaller than n. To reorder 1...n this way as well, split it into evens and odds, and apply the function floor((x+1)/2) to these sets to create two half-problems of the same type which by the hypothesis can be solved. Now unapply the transformation to each half-solution using the function 2x to recover the evens and the function 2x-1 to recover the odds. These functions are linear so the condition is still satisfied. Now concatenate these two lists together to form the solution. This concatenation always works because the average of an even and an odd is not an integer. """ - http://math.stackexchange.com/questions/108439/total-ordering-of-the-reals-with-a-certain-property """ I was communicated the following 1994 Miklos Schweitzer problem: Is there an ordering of the real numbers such that whenever x time2(go). go => foreach(N in 10..10..100) time2(average_avoiding2(N, _X)) end, nl. % a more general approach go1 => % A = [1,2,5,9], % original example % From the comments. % A = [1,2,3,4,5,6,7,8,9], % A = [I : I in 1..30], % A = [2,3,4], % This is UNSAT according to this model. % A = [2,2,2,4,5,6,2,2,2,2], _ = random2(), A = [random() mod 10 : _I in 1..10], % N = A.length, time2(average_avoiding(A,_X)), % All = findall(X, average_avoiding2(A,_X)), % writeln(all=All), % writeln(len=All.length), nl. go2 => time2(average_avoiding2(100, _X)), nl. go3 => % A valid solution for N=100. See comments above. L = [0,64,32,96,16,80,48,8,72,40,24,88,56,4,68,36,20,84,52,12,76,44,28,92,60,2,66,34,98,18,82,50,10,74,42,26,90,58,6,70,38,22,86,54,14,78,46,30,94,62, 1,65,33,97,17,81,49,9,73,41,25,89,57,5,69,37,21,85,53,13,77,45,29,93,61,3,67,35,99,19,83,51,11,75,43,27,91,59,7,71,39,23,87,55,15,79,47,31,95,63], N = L.length, println(l=L), println(diffs=L.diff()), foreach(I in 1..N) % printf("%3d (%2X) %3d %w %w %3X (mod 16: %2d) (div 16: %2d) (mod 8: %d) (mod 64: %2d)\n", I, I, L[I],pad(L[I].to_binary_string(),(2**nearest_two_pow(N)).to_binary_string().length,0), pad(L[I].to_oct_string(),(2**nearest_oct_pow(N)).to_binary_string().length,0),L[I], L[I] mod 16, L[I] div 16, L[I] mod 8, L[I] mod 64, AllMod) printf("%3d: %3d ", I, L[I]), foreach(J in 2..16) printf("%2d ", L[I] mod J) end, nl end, nl. go4 => foreach(N in 10..10..100) println(n=N), A = 0..N-1, time2(average_avoiding(A, _X)) end, nl. % % a general approach: A is any array of numbers % average_avoiding(A, X) => println(a=A), N = length(A), X = new_list(N), X :: A, foreach(I in 1..N, J in I+1..N) foreach(K in I+1..J-1) 2*X[K] #!= X[I] + X[J] end end, % ensure cardinality of each value foreach(E in A.remove_dups()) C = [ 1 : I in 1..N,A[I] == E].sum(), count(E,X,#=,C) end, % symmetry breaking X[1] #= min(X), solve([ffd, split], X), writeln(x=X), writeln(diff=X.diff()), writeln(mod2=[E mod 2 : E in X]), nl. % % Average avoiding for 0..N-1. % average_avoiding2(N, X) => println(n=N), A = [I : I in 0..N-1], X = new_list(N), X :: A, foreach(I in 1..N, J in I+1..N) foreach(K in I+1..J-1) % 2*X[K] #!= X[I] + X[J] X[K]+X[K] #!= X[I] + X[J] end end, all_distinct(X), % much faster % all_different(X), % testing: Works for even N N2 = N div 2, if N mod 2 == 0 then foreach(I in 1..N div 2) X[I+N2] #= X[I]+1 end, foreach(I in 1..N) if I < N div 2 then X[I] mod 2 #= 0 end, if I > N div 2 then X[I] mod 2 #= 1 end end end, % Symmetry breaking X[1] #= 0, % X[N] #= 1, solve([ffc,split], X), % solve([constr,split], X), writeln(x=X), writeln(diff=X.diff()), foreach(I in 1..N) printf("%3d %3d %w %2X\n", I, X[I],pad(X[I].to_binary_string(),(2**nearest_two_pow(N)).to_binary_string().length,0), X[I]) end, nl. diff(L) = [ D : I in 2..L.length, D #= L[I] - L[I-1]]. % diff(L) = [ L[I+1] - L[I] : I in 1..L.length-1]. pad(List, N, Value) = Res => Res = List, Len = List.length, if N > Len then Res := [Value : _I in 1..N-Len] ++ List end. nearest_two_pow(N) = Pow => Pow := 0, foreach(I in 0..N, Pow = 0) if 2**I > N then Pow := I end end. nearest_oct_pow(N) = Pow => Pow := 0, foreach(I in 0..N, Pow = 0) if 8**I > N then Pow := I end end.