RE: Re: Re: Re: Re: circumference of an ellipse

*To*: mathgroup at smc.vnet.net*Subject*: [mg19592] RE: [mg19541] Re: [mg19501] Re: [mg19447] Re: [mg19390] Re: circumference of an ellipse*From*: "Simons, F.H." <F.H.Simons at tue.nl>*Date*: Sat, 4 Sep 1999 01:34:28 -0400*Sender*: owner-wri-mathgroup at wolfram.com

Some days ago the following problem was posted in this group: Mecit Yaman schrieb: > > Hi there, > > I am trying to solve a problem with Mathematica. You have numbers from 1 to n all > numbers twice , namely. > > 1 1 2 2 3 3 4 4 5 5 for example for n=5 > > I am trying to sort the numbers o that between two 'n's there must be exactly n > numbers. > > For example if n=3 the solution is > 2 3 1 2 1 3 . You see there is 1 number between 1 and 1. and 2 numbers between 2 > and 2, and 3 between 3's. > > I know this forum is not for asking problems. Hartmut Wolf replied: > Right! So if you do, you should not camouflage you posting behind an > answer to an obviously unrelated question! With respect to this, I disagree with Hartmut. Mathematica is a very powerful tool for solving problems and most of us can profit from studying the various solutions of a posed problem. Being a reader of this group for many years, I regret that indeed the tendency of the questions has changed to only technical problems with Mathematica. Some years ago indeed mathematical questions like this one were regularly brought up and I like this particular problem very much. Here is a solution rather different from Hartmut's. The technique I use is backtracking. For a given integer n we have to fill a list of length 2 n with the numbers 1, 1, 2, 2, ..., n, n in such a way that the above condition holds. Suppose that we have an intermediate result. If all numbers have been used, we have a solution of the problem. Otherwise, we compute the next number to be placed in the list of length 2 n, find all positions where this number can be put (maybe none) so that we arrive some further intermediate results on which we can repeat the construction. Here is a function that performs this operation. f[res_] := Block[{m = Complement[Range[n], res], pos, aux}, If[m === {}, AppendTo[result, res], m = m[[1]]; pos = 1; While[ pos < 2 n - m, aux = res; If[ aux[[pos]] == aux[[pos + m + 1]] == 0, aux[[pos]] = aux[[pos + m + 1]] = m; f[aux] ]; pos = pos + 1] ] ] For any solution, the reverse is also a solution. Hence we may restrict ourselves to solutions for which the first number 1 is at position 1, 2 , ... (n-1). So we find all solutions for n = 5 in the following way: result = {}; n = 5; (f /@ NestList[ RotateRight, Join[ {1, 0, 1}, Table[0, {2 n - 3}]], n - 2];) // Timing result In a few seconds we are sure that there are no solutions. On my relatively slow computer (Windows 95, 120Mhz) it took 18 seconds to find that for n=7 we have 26 solutions, 97 seconds to find that for n=8 we have 150 solutions, 705 sec to find that for n=9 we have no solutions and 5458 seconds (so within lunch and desert) that also for n=10 we have no solutions. Amazing that we have so many solutions for n=7 and n=8, and none for n= 5, 6, 9, 10, and likely also 11, 12; I did not have a complete run for these last values of n. Fred Simons Eindhoven University of Technology

**Help: Outer of a list of lists**

**Re: LaTeX Output**

**Re: Help: Outer of a list of lists**

**Element extraction**