Re: Select from Tuplet using logical expression

• To: mathgroup at smc.vnet.net
• Subject: [mg117038] Re: Select from Tuplet using logical expression
• From: DrMajorBob <btreat1 at austin.rr.com>
• Date: Tue, 8 Mar 2011 05:36:17 -0500 (EST)

```At my machine, #9 scales better than either #10 or the #11 that I added.
#11 seems to scale better than #10, but not as well as #9.

With a more general input, all the solvers could need Union (somewhere) to
avoid a lot of duplicates.

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]
m[11] := Flatten[
Table[Tuples[{c = Drop[r, {i}], c, {r[[i]]}}], {i, Length@r}], 1]

Transpose@Table[r = Range[n = 2^k];
Table[AbsoluteTiming[t = Length@m[j]; {j, n, t}], {j, 7, 11}], {k,
4, 6}] // ColumnForm

ColumnForm[{{{0.00591`4.2231324743772305, {7, 16, 3600}}, {
0.041152`5.065935940404083, {7, 32, 30752}}, {
0.339338`5.982177489351639, {7, 64, 254016}}}, {{
0.005333`4.178516577178848, {8, 16, 3600}}, {
0.0358`5.005428020139846, {8, 32, 30752}}, {
0.303657`5.933928290567705, {8, 64, 254016}}}, {{
0.002998`3.928376622008233, {9, 16, 3600}}, {
0.016185`4.660657697234564, {9, 32, 30752}}, {
0.121207`5.535072695616553, {9, 64, 254016}}}, {{
0.002009`3.754524930244218, {10, 16, 3600}}, {
0.016869`4.678634331725041, {10, 32, 30752}}, {
0.168136`5.677205704719193, {10, 64, 254016}}}, {{
0.001774`3.700498608991677, {11, 16, 3600}}, {
0.017524`4.695178238002113, {11, 32, 30752}}, {
0.16683`5.673819143292538, {11, 64, 254016}}}}]

Transpose@Table[r = Range[n = 2^k];
Table[AbsoluteTiming[t = Length@m[j]; {j, n, t}], {j, 9, 11}], {k,
7, 8}] // ColumnForm

ColumnForm[{{{0.967439`6.437168584449372, {9, 128, 2064512}}, {
7.581579`7.331304658174462, {9, 256, 16646400}}}, {{
1.608454`6.657953638571179, {10, 128, 2064512}}, {
88.318995`8.39759911198302, {10, 256, 16646400}}}, {{
1.618712`6.660714579780597, {11, 128, 2064512}}, {
83.386051`8.372638400483885, {11, 256, 16646400}}}}]

Bobby

On Mon, 07 Mar 2011 04:50:29 -0600, Ray Koopman <koopman at sfu.ca> wrote:

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

--
DrMajorBob at yahoo.com

```

• Prev by Date: Re: Delete elements from list..
• Next by Date: Re: Any recommendations for new hardware (quadcore/GPUs)?
• Previous by thread: Re: Select from Tuplet using logical expression
• Next by thread: Local Variables in Do[]