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