MathGroup Archive 2006

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

Search the Archive

Re: need to make a special function

Nabeel Butt wrote:

>         I need help on making a special type of function which has the
> following properties.
>    f[1]={{0},{1}}
>    f[2]={{0,0},{0,1},{1,0},{1,1}}
>    f[3]={{0,0,0},{0,0,1},{0,1,0},{0,1,1},{1,0,0},{1,0,1},{1,1,0},{1,1,1}}
> on you can see the pattern emerging.
>  I need a very efficient code to perform the above evaluation in some

just one way, not necessarily very efficient but maybe good enough for a
starting point for values of n<20:

f[n_] := Flatten[Map[Permutations,
Table[If[i <= j, 0, 1], {i, 1, n + 1}, {j, 1, n}]
], 1]

if you need the permutations in a specific order, you will need some more
work to be done. If this code is too slow, you might want to check the
Combinatorica-Package, maybe there are functions which can be used to do
this in a more efficient way. Anyway, since the list size grows like 2^n my
guess is that the generation of the lists will be even less an efficiency
problem than handling the huge results, some experiments indicate that
memory allocation dominates calculation time on my machine for n>20. 

Maybe for calls for large n you want to generate the permutations on the fly
instead of storing the huge lists in memory, on the other hand if you have
many calls for low values of n you might be better off to store the values
you have calculated instead of recalculating them every time f is called.
So further optimization of f depends a lot on what your optimization
problem is actually doing with these lists and how f is called...



  • Prev by Date: Re: Using implicit information about row indices
  • Next by Date: Re: Using implicit information about row indices
  • Previous by thread: Re: need to make a special function
  • Next by thread: Can we prove that it is never a square?