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