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