Re: need to make a special function
- To: mathgroup at smc.vnet.net
- Subject: [mg68301] Re: need to make a special function
- From: albert <awnl at arcor.de>
- Date: Tue, 1 Aug 2006 06:59:13 -0400 (EDT)
- References: <eakec7$qvd$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
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}}
> .............so 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...
hth,
albert