select subsets of elements of a list under a certain condition

Question

I am new in Mathematica and am stuck on a simple problem. Please advise:

I have the following list:

list = {
{"1", 1000},
{"2", 800},
{"3", 800}
};

I want to select subsets of the first elements Subsets[list[[All,1]]] when the Total of coresponding second elements is for example $>= 1000$.

So in this example the expected result is:

 {{"1"}, {"1", "2"}, {"1", "3"}, {"2", "3"}, {"1", "2", "3"}}

I solved it using @Kuba's answer below, and added DeleteDuplicates to make it work better (produce less output) on large datasets:

lst = DeleteDuplicates[
If[
Total[#[[;; , 2]]] >= 1000, 
    #[[;; , 1]]] & /@ (Rest@ Subsets[list]) /. Null -> Sequence[]
] 
// TableForm

Did you mean >=1000? If I understand correctly your expected result should be {{1}, {1,2}, {1,3}, {2,3}, {1,2,3}}. — Kuba, Aug 6 '13 at 11:58
Since I know what you want, I have edited your question so it should be clear now. Feel free to undo if you wish. — Kuba, Aug 6 '13 at 12:34
@Kuba the guy said the output should be {"2","3"}. Surely he knows what he wants? — Mike Honeychurch, Aug 6 '13 at 13:17
@MikeHoneychurch You are right, but at least now the question is self consistent. We will see how he respond to that edit. — Kuba, Aug 6 '13 at 13:25
I wonder - how long is your initial list? Subsets has limits, so to speak... (especially on "unbounded" length of subsets). Say, you use list = Table[{i, RandomInteger[{500, 1100}]}, {i, 20}] (i.e. 20 elements in the initial list), on my machine, @Kuba's code takes 8sec (and on 25 elements, I didn't wait for it to finish. You could do With[{subsets = Subsets[list, {1, \[Infinity]}]}, Pick[subsets[[All, All, 1]], UnitStep[Total /@ subsets[[All, All, 2]] - 1000], 1]] which has the same problem, but better speed. So if the list is considerably longer, you'd need another approach... — Pinguin Dirk, Aug 7 '13 at 17:23

Kuba · Accepted Answer · 2013-08-06 12:03:33Z

1

If I understand correctly, this is what you asked for:

If[
   Total[#[[ ;; , 2]]] >= 1000,
   #[[ ;; , 1]]
  ] & /@ (Rest@Subsets[list]) /. Null -> Sequence[]

{{"1"}, {"1", "2"}, {"1", "3"}, {"2", "3"}, {"1", "2", "3"}}

answered Aug 6 '13 at 12:03

Kuba♦

132k12 gold badges262 silver badges679 bronze badges

$\begingroup$ Actually I am looking for a way to select subsets between certain values. I like your answer a lot, you made me understand how to do it!! For example, a slight tweak gives me exactly what I want: $\endgroup$
– sanderws
Aug 6 '13 at 12:23
$\begingroup$ If[1000 > Total[#[[;; , 2]]] > 100, #[[;; , 1]]] & /@ (Rest@ Subsets[list]) /. Null -> Sequence[] $\endgroup$
– sanderws
Aug 6 '13 at 12:24
1

$\begingroup$ @sanderws I'm glad you find it useful :) Please do not accept so fast, there are going to be more great answers if you edit your question to be more clear. :) $\endgroup$
– Kuba ♦
Aug 6 '13 at 12:27
$\begingroup$ I would like to ask a follow up question. However I find it hard to formulate it so I would like to show you how I used your answer and what I would like to do next. I just figured out that you cant use the same markup in comments as in questions but It seems much to start a new question. What is a smart way to follow up? @kuba $\endgroup$
– sanderws
Aug 6 '13 at 14:35

Add a comment |

m_goldberg · Accepted Answer · 2013-08-08 12:37:41Z

0

u = Rest @ Subsets[list];
#[[;; ,1]]& /@ Pick[u, (Total[#[[;;, 2]]] >= 1000)& /@ u]

yields

{{"1"}, {"1", "2"}, {"1", "3"}, {"2", "3"}, {"1", "2", "3"}}

m_goldberg

106k16 gold badges90 silver badges237 bronze badges

answered Aug 8 '13 at 11:53

ubpdqn

54.2k2 gold badges51 silver badges128 bronze badges

Add a comment |

2 Answers 2