MathGroup Archive 1999

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

Search the Archive

Re: Numbers problem

  • To: mathgroup at smc.vnet.net
  • Subject: [mg19524] Re: [mg19520] Numbers problem
  • From: "Andrzej Kozlowski" <andrzej at tuins.ac.jp>
  • Date: Sun, 29 Aug 1999 17:21:23 -0400
  • Sender: owner-wri-mathgroup at wolfram.com

Problems like this one consist of two parts, a hard one and a (realtively)
easy one. The hard one is finding a workable algorithm. The easy one is
writing a mathematica program to implement it. In your case I do not know
any workable algorithm (but then I have given this matter no time at all). I
know of course the obvious one: find all possible distinct permutations of a
list of your type and select from it elements satisfying your condition.
Clearly no implementation of this algorithm will be workable for anything
but small values of n. But anyway, here is a quick implementation of this
essentially useless method:

First we load the combinatorica package in order to use its
DistinctPermutations function:

In[1]:=
<< DiscreteMath`Combinatorica`


Next we define our test function.

In[2]:=
test[l_List, i_] := (Last[#] - First[#]) &@Flatten[Position[l, i]] - 1 == i;
test[l_List] := Apply[And, Map[test[l, #] &, Union[l]]]

Now we can find the solution of your example:

In[3]:=
Select[DistinctPermutations[{1, 1, 2, 2, 3, 3}], test]
Out[3]=
{{2, 3, 1, 2, 1, 3}, {3, 1, 2, 1, 3, 2}}

We can also get the next case:

In[4]:=
Select[DistinctPermutations[{1, 1, 2, 2, 3, 3, 4, 4}], test]
Out[4]=
{{2, 3, 4, 2, 1, 3, 1, 4}, {4, 1, 3, 1, 2, 4, 3, 2}}

Beyond that things will get very slow. I have not considered the efficiency
of my implementation at all because I am pretty sure that unless you or
someone else can propose a better algorithm not even a Mathematica speed
demon like Carl Woll can make any significant difference here.
--
Andrzej Kozlowski
Toyama International University
JAPAN
http://sigma.tuins.ac.jp
http://eri2.tuins.ac.jp


----------
>From: Mecit Yaman <mecit at iname.com>
To: mathgroup at smc.vnet.net
>To: mathgroup at smc.vnet.net
>Subject: [mg19524] [mg19520] Numbers problem
>Date: Sun, Aug 29, 1999, 8:00 AM
>

>
> 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. But i am
> learning Mathematica and
> wanna see how professionals solve a real problem with
> Mathematica.
>
> Thank you very much for giving me a chance to ask my
> question.
> Best wishes to everyone.
>
>
>
>
>
> 


  • Prev by Date: Word and Mathematica
  • Next by Date: Re: How to use sign[] for symbolic operations?
  • Previous by thread: Numbers problem
  • Next by thread: Re: Numbers problem