MathGroup Archive 2010

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

Search the Archive

Re: Combinations Dispositions Permutations TREE

  • To: mathgroup at smc.vnet.net
  • Subject: [mg108724] Re: Combinations Dispositions Permutations TREE
  • From: DrMajorBob <btreat1 at austin.rr.com>
  • Date: Mon, 29 Mar 2010 05:22:32 -0500 (EST)

An easy improvement is to eliminate most of the functions and use  
built-ins:

"perm" is Factorial.

"elDisp" is Permutations (there's no problem adding List to the second  
argument in calls).

"dispRip" is Power.

"elDispRip" is Tuples.

"comb" is Binomial

"combRip[n,k]" is Binomial[n + k - 1, k]

and

elCombRip[list,k] is Union[Sort /@ Tuples[Union@list, k]]

(The second Union is to eliminate duplicates in "list", if any, for  
efficiency. That could be a huge improvement, for lists with a lot of  
duplicates.)

You may like the names you've chosen, but it's probably better to use the  
names Mathematica already provides.

In addition, here are some improvements to "elCombRip", one step at a time:

First idea:

Clear@elCombRip1
elCombRip1[list_List, 1] := List /@ Union@list
elCombRip1[list_List, k_] := Flatten[Module[{rest = Union@list, first},
    First@Last@Reap[
       While[
        Length@rest > 1,
        first = First@rest;
        Sow@Union[Sort@Prepend[#, first] & /@ Tuples[rest, k - 1]];
        rest = Rest@rest;
        ];
       Sow@Tuples[rest, k]
       ]
    ], 1]

That uses Tuples on smaller lists... but we can do better:

Clear@elCombRip2
elCombRip2[list_List, 1] := List /@ Union@list
elCombRip2[list_List, k_] := Flatten[Module[{rest = Union@list, first},
    First@Last@Reap[
       While[
        Length@rest > 1,
        first = First@rest;
        Sow@
         Union[Prepend[#, first] & /@
           Union[Sort /@ Tuples[rest, k - 1]]];
        rest = Rest@rest;
        ];
       Sow@Tuples[rest, k]
       ]
    ], 1]

That uses the original idea Union[Sort /@ Tuples[list, k]]] with smaller  
lists and smaller k, but we can still do better:

Clear@elCombRip
elCombRip[list_List, 1] := List /@ Union@list
elCombRip[list_List, k_] :=
  Flatten[Module[{rest = Union@list, first},
    First@Last@Reap[
       While[
        Length@rest > 1,
        first = First@rest;
        Sow@Union[Prepend[#, first] & /@ elCombRip3[rest, k - 1]];
        rest = Rest@rest;
        ];
       Sow@Tuples[rest, k]
       ]
    ], 1]

Timing[one = Union[Sort /@ Tuples[Range@25, 5]];]

{12.0882, Null}

Timing[two = elCombRip1[Range@25, 5];]

{3.10245, Null}

Timing[three = elCombRip2[Range@25, 5];]

{1.96643, Null}

Timing[four = elCombRip[Range@25, 5];]

{1.00799, Null}

one == two == three == four

True

Length@one

118755

Here's the same test for a longer, unsorted list with duplicates:

list = RandomChoice[Range@20, 30];

Timing[one = Union[Sort /@ Tuples[list, 5]];]

{34.8852, Null}

Timing[two = elCombRip1[list, 5];]

{0.25278, Null}

Timing[three = elCombRip2[list, 5];]

{0.153685, Null}

Timing[four = elCombRip[list, 5];]

{0.122611, Null}

one == two == three == four

True

Length@one

11628

Length@Union@list

15

Bobby

On Sun, 28 Mar 2010 04:06:53 -0500, Lele <emanuele.tormene at gmail.com>  
wrote:

> Given a list l of n objects,
> I want to choose k elements,
> with or without repetitions
>
> I wrote some functions to find the number and the elements of
>
> dispositions
> Disp[n_, k_] := n!/(n - k)!;
> ElDisp[l_, k_] := Permutations[l, {k}];
> DispRip[n_, k_] := n^k;
> ElDispRip[l_, k_] := Tuples[l, k];
>
> permutations
> Perm[n_] := Disp[n, n];
> ElPerm[l_] := Permutations[l, {Part[Dimensions[l], 1]}];
>
> combinations
> Comb[n_, k_] := Disp[n, k]/Perm[k];
> ElComb[l_, k_] := Subsets[l, {k}];
> CombRip[n_, k_] := (n + k - 1)!/((k! (n - 1)!));
> ElCombRip[l_, k_] := (m = ElDispRip[l, k]; d = Length[m];   For[i = 1,
> i < d, m[[i]] = Sort[m[[i]]], i++]; Union[m]);
>
> 1) I am sure it is possible to write my functions really better
> 2) I would like to write a function able to draw a tree representing
> the path going through every k-th step of "fishing" into the list (for
> every function).
> For example, given the l={a,b,c} , k=2, I would like to draw a
> DispositionTree[l,k]
>
>    a -- b
>  /    \ c
> /
> --b -- a
> \    \  c
>  \
>    c -- a
>      \ b
>
> Thanks, Lele (I am sorry for my english, my code and my ignorance)
>


-- 
DrMajorBob at yahoo.com


  • Prev by Date: Re: Transformation of 3D Objects to 2D Parallel-projection
  • Next by Date: Re: Substitute expressions with FullSimplify
  • Previous by thread: Combinations Dispositions Permutations TREE
  • Next by thread: Transformation of 3D Objects to 2D Parallel-projection