Re: Select from Tuplet using logical expression
- To: mathgroup at smc.vnet.net
- Subject: [mg117015] Re: Select from Tuplet using logical expression
- From: Ray Koopman <koopman at sfu.ca>
- Date: Mon, 7 Mar 2011 05:50:29 -0500 (EST)
- References: <ikvomg$f8l$1@smc.vnet.net>
On Mar 6, 2:46 am, Heike Gramberg <heike.gramb... at gmail.com> wrote:
> On 5 Mar 2011, at 11:08, Peter Pein wrote:
>> Am 04.03.2011 09:40, schrieb Ray Koopman:
>>> On Mar 1, 2:27 am, Lengyel Tamas<lt... at hszk.bme.hu> wrote:
>>>> Hello.
>>>>
>>>> Skip if needed:
>>>> ///I am working on a part combinatorical problem with sets of 3
>>>> differently indexed values (e.g. F_i, F_j, F_k, F denoting
>>>> frequency channels) which are subsets of many values (e.g 16
>>>> different frequency channels, denoted F_0, F_1 ... F_15).
>>>>
>>>> Now, I need to select triplets from these channels, I used Tuplets.
>>>> So far so good. From these I need those combinations where indexes
>>>> i!=k and/or j!=k, and i=j is allowed (e.g {i,j,k} = {12, 12, 4} is
>>>> a valid channel combination, but {3, 12, 3} is not).///
>>>>
>>>> So basically I need to generate triplets from a range of integer
>>>> numbers, where the first and second elements of these triplets do
>>>> not match the third. I thought Select would help, but I don't know
>>>> if there exists an option to control elements' values in a condition.
>>>>
>>>> From then on I must use these triplets' elements in a function.
>>>>
>>>> But first I am asking your help in generating thos triplets of
>>>> numbers.
>>>>
>>>> Thanks.
>>>>
>>>> Tam s Lengyel
>>>
>>> 1 - 6 have been posted previously. 7 is new, a modification of 6.
>>> 1 - 5 generate all the triples, then delete unwanted ones.
>>> 6 & 7 generate only the triples that are wanted.
>>>
>>> The time differences seem to be reliable.
>>>
>>> r = Range[32];
>>> AbsoluteTiming[t1 = Select[Tuples[r,3],
>>> #[[1]]!=#[[3]]&& #[[2]]!=#[[3]]&]; "1"]
>>> AbsoluteTiming[t2 = Select[Tuples[r,3],
>>> FreeQ[Most@#,Last@#]&]; "2"]
>>> AbsoluteTiming[t3 = Cases[Tuples[r,3],
>>> _?(FreeQ[Most@#,Last@#]&)]; "3"]
>>> AbsoluteTiming[t4 = DeleteCases[Tuples[r,3],
>>> _?(MemberQ[Most@#,Last@#]&)]; "4"]
>>> AbsoluteTiming[t5 = DeleteCases[Tuples[r,3],
>>> {k_,_,k_}|{_,k_,k_}]; "5"]
>>> AbsoluteTiming[t6 = Flatten[Function[ij,Append[ij,#]& /@
>>> Complement[r,ij]] /@ Tuples[r,2], 1]; "6"]
>>> AbsoluteTiming[t7 = Flatten[Outer[Append,{#},
>>> Complement[r,#],1]& /@ Tuples[r,2], 2]; "7"]
>>> SameQ[t1,t2,t3,t4,t5,t6,t7]
>>>
>>> {0.378355 Second, 1}
>>> {0.390735 Second, 2}
>>> {0.409103 Second, 3}
>>> {0.420442 Second, 4}
>>> {0.140180 Second, 5}
>>> {0.128378 Second, 6}
>>> {0.085107 Second, 7}
>>> True
>>
>> Ray,
>>
>> you might want to add
>>
>> AbsoluteTiming[t8=Flatten/@Flatten[(Distribute[
>> {{#1},Complement[r,#1]},List]&)/@Tuples[r,{2}],1];"8"]
>>
>> which needs ~95% of the time needed to calculate t7.
>>
>> Peter
>
> You could also do
>
> AbsoluteTiming[
> t9 = Flatten[
> Map[(Tuples[{Complement[r, {#}], Complement[r, {#}], {#}}]) &, r],
> 1]; "9"]
>
> That seems to be about twice as fast as t8, although t9 is in a
> different order from t1-t8 (SameQ[t1, t2, t3, t4, t5, t6, t7, t8,
> Sort[t9]] is still True though).
>
> Heike.
7, 8, & 9 below are as in my previous post. 10 below is your 9.
Whatever it's called, it's definitely the fastest so far.
m[7] := Flatten[ Outer[
Append,{#},Complement[r,#],1]& /@ Tuples[r,2], 2]
m[8] := Flatten /@ Flatten[ Distribute[
{{#},Complement[r,#]},List]& /@ Tuples[r,2], 1]
m[9] := Flatten[ Distribute[
Append[#,Complement[r,#]],List]& /@ Tuples[r,2], 1]
m[10]:= Flatten[ Tuples[
{Complement[r,{#}],Complement[r,{#}],{#}}]& /@ r, 1]
Transpose@Table[r = Range[n = 2^k];
Table[AbsoluteTiming@Do[Null,{1*^7}];
AbsoluteTiming[m[j];{j,n}],{j,7,10}],{k,4,6}]//ColumnForm
v5.2
{{0.013456, { 7,16}}, {0.091608, { 7,32}}, {0.685204, { 7,64}}}
{{0.013743, { 8,16}}, {0.105262, { 8,32}}, {0.822973, { 8,64}}}
{{0.006476, { 9,16}}, {0.041605, { 9,32}}, {0.257631, { 9,64}}}
{{0.002176, {10,16}}, {0.019507, {10,32}}, {0.167546, {10,64}}}
v6.0
{{0.019666, { 7,16}}, {0.129066, { 7,32}}, {0.947086, { 7,64}}}
{{0.018183, { 8,16}}, {0.131886, { 8,32}}, {0.986983, { 8,64}}}
{{0.007146, { 9,16}}, {0.042182, { 9,32}}, {0.251833, { 9,64}}}
{{0.002474, {10,16}}, {0.017437, {10,32}}, {0.145921, {10,64}}}
A tiny speedup in 10 may be had by changing Complement[r,{#}]
to DeleteCases[r,#]. (Another may be had by using Delete[r,#],
but that works only when r = Range[n]. In the OP's example,
r was Range[0,n-1], in which case we would Delete[r,#+1].
However, I dislike making routines data-dependent that way.
The extra speed is simply not worth the potential cost that
could be incurred if someone changed the channel codes.)