Re: Combination/Permutation questions

*To*: mathgroup at smc.vnet.net*Subject*: [mg37442] Re: [mg37436] Combination/Permutation questions*From*: Andrzej Kozlowski <andrzej at tuins.ac.jp>*Date*: Wed, 30 Oct 2002 00:50:39 -0500 (EST)*Sender*: owner-wri-mathgroup at wolfram.com

On Tuesday, October 29, 2002, at 02:09 PM, Michael Chang wrote: > First, suppose that I have 4 objects, a, b, c, and d, respectively. > How can I generate the permutation set when chosing, say, only *2* > elements. > > In[1]:= Permutations[{a,b,c,d}] > > gives me the permutation set when choosing *all* 4 objects ... :( In[1]:= <<DiscreteMath`Combinatorica` In[2]:= Perms[l_List,k_]:=Flatten[Permutations/@KSubsets[l,k],1] In[3]:= Perms[{a,b,c,d},2] Out[3]= {{a,b},{b,a},{a,c},{c,a},{a,d},{d,a},{a,e},{e,a},{b,c},{c,b},{b,d},{d,b} ,{ b,e},{e,b},{c,d},{d,c},{c,e},{e,c},{d,e},{e,d}} > > Second, for the same four objects (a,b,c,d), to generate the > *combination* set (with 2 elements), I use: > > In[2]:= Needs["DiscreteMath`Combinatorica`"]; > In[3]:= cset=KSubsets[{a,b,c,d},2] > > and this generates the expected 6 combinatorial pairs > ({{a,b},{a,c},{a,d},{b,c},{b,d},{c,d}}). > > What I'd like to do next is add each combinatorial set, and I am able > to do this correctly via: > > In[4]:= Plus@@Transpose[cset] > > to obtain {a+b,a+c,a+d,b+c,b+d,c+d}. Alternatively: In[4]:= cset=KSubsets[{a,b,c,d},2] Out[4]= {{a,b},{a,c},{a,d},{b,c},{b,d},{c,d}} In[5]:= Plus@@@cset Out[5]= {a+b,a+c,a+d,b+c,b+d,c+d} > > My problem lies in the fact that now, I'd like to be able to allow > *each* (a,b,c,d) element to be either plus, or minus (in reality, I'm > trying to generate combinatorial adds/minuses for *functions* > (a,b,c,d)), and to still generate the 'sum' of the cominatorial set. > So for instance, in my current example, for the *first* {a,b} > combinatorial pair, I'd like to be able to generate > > In[5]:= > Plus@@Transpose[Partition[Flatten[Outer[List,{a,-a},{b,-b}]],2]] > > (which generates {a+b,a-b,-a+b,-a-b}) ... only I'd like this to be > somehow done automatically for *each* combinatorial pair (and, for the > more general case when I generate combinatorial sets involving only > 'k' elements). I've struggled with this for a while, and am only able > to generate such a list *manually* for each of my six original > combinatorial pairs ... a tedious, and somewhat tiresome procedure! :( > Is there a way of 'easily' doing this?!? For example: In[6]:= f[l_List,k_]:=Rest[Union[Plus@@@Perms[Join[l,-l],k]]] In[7]:= f[{a,b,c,d},2] Out[7]= {-a-b,a-b,-a+b,a+b,-a-c,a-c,-b-c,b-c,-a+c,a+c,-b+c,b+c,-a-d,a-d,-b-d,b- d,- c-d,c-d,-a+d,a+d,-b+d,b+d,-c+d,c+d} > > With my newly generated list (having 4*6 'elements'), how can I also > go about finding which expressions involve/use only, say, 1 Minus? Is > there an 'easy' way of doing this too? (For instance, I'd like to > then 'filter' for (a-b) and (b-a) ...) (Perhaps the count of 1 Minus > is a little contrived for this example here, but for the more general > case I'll probably be considering, I might need to filter for, say, > (longer) expressions involving 2 Minuses (say).) In cases like the above the following will work: In[8]:= Count[#,-1,2]&/@% Out[8]= {2,1,1,0,2,1,2,1,1,0,1,0,2,1,2,1,2,1,1,0,1,0,1,0} Andrzej Kozlowski Yokohama, Japan http://www.mimuw.edu.pl/~akoz/ http://platon.c.u-tokyo.ac.jp/andrzej/