MathGroup Archive 1999

[Date Index] [Thread Index] [Author Index]

Search the Archive

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

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

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

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

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

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

  • Prev by Date: Help: Outer of a list of lists
  • Next by Date: Re: LaTeX Output
  • Previous by thread: Re: Help: Outer of a list of lists
  • Next by thread: Element extraction