Prev: Printing large PDF files generated from Mathematica
Next: Running Mathematica code using DOS
From: Lele on 28 Mar 2010 05:06
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)

From: DrMajorBob on 29 Mar 2010 06:21
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(a)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(a)elCombRip1
elCombRip1[list_List, 1] := List /@ Union(a)list
elCombRip1[list_List, k_] := Flatten[Module[{rest = Union(a)list, first},
First(a)Last@Reap[
While[
Length(a)rest > 1,
first = First(a)rest;
Sow(a)Union[Sort(a)Prepend[#, first] & /@ Tuples[rest, k - 1]];
rest = Rest(a)rest;
];
Sow(a)Tuples[rest, k]
]
], 1]

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

Clear(a)elCombRip2
elCombRip2[list_List, 1] := List /@ Union(a)list
elCombRip2[list_List, k_] := Flatten[Module[{rest = Union(a)list, first},
First(a)Last@Reap[
While[
Length(a)rest > 1,
first = First(a)rest;
Sow@
Union[Prepend[#, first] & /@
Union[Sort /@ Tuples[rest, k - 1]]];
rest = Rest(a)rest;
];
Sow(a)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(a)elCombRip
elCombRip[list_List, 1] := List /@ Union(a)list
elCombRip[list_List, k_] :=
Flatten[Module[{rest = Union(a)list, first},
First(a)Last@Reap[
While[
Length(a)rest > 1,
first = First(a)rest;
Sow(a)Union[Prepend[#, first] & /@ elCombRip3[rest, k - 1]];
rest = Rest(a)rest;
];
Sow(a)Tuples[rest, k]
]
], 1]

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

{12.0882, Null}

Timing[two = elCombRip1[Range(a)25, 5];]

{3.10245, Null}

Timing[three = elCombRip2[Range(a)25, 5];]

{1.96643, Null}

Timing[four = elCombRip[Range(a)25, 5];]

{1.00799, Null}

one == two == three == four

True

Length(a)one

118755

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

list = RandomChoice[Range(a)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(a)one

11628

Length(a)Union@list

15

Bobby

On Sun, 28 Mar 2010 04:06:53 -0500, Lele <emanuele.tormene(a)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(a)yahoo.com

From: Lele on 4 Apr 2010 07:44
Thanks!!! Could you help me with the second question?

> > 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)

From: Bob Hanlon on 5 Apr 2010 08:00

ClearAll[graph]

graph[elem_?VectorQ, n_Integer?Positive, opts___] :=

Module[{str = ToString /@ elem, tup, nodes, gr},
tup = Select[Tuples[str, n],
Length[Union[#]] == n &];
nodes = FoldList[StringJoin, First[#],
Rest[#]] & /@ tup;
gr = Union[Flatten[{Thread["O" -> str],
Rule @@@ Partition[#, 2, 1] & /@ nodes}]];
GraphPlot[gr, FilterRules[{opts}, Options[GraphPlot]]]]

graph[{a, b, c, d}, 3, ImageSize -> 500, VertexLabeling -> True]


Bob Hanlon

---- Lele <emanuele.tormene(a)gmail.com> wrote:

=============
Thanks!!! Could you help me with the second question?

> > 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)


 | 
Pages: 1
Prev: Printing large PDF files generated from Mathematica
Next: Running Mathematica code using DOS