Message Boards Message Boards

1
|
10896 Views
|
9 Replies
|
5 Total Likes
View groups...
Share
Share this post:

Pick out pairs of numbers in a list that add up to any number in 2nd list?

Hello, I have a question about selecting items in a list that match any item in another list.

Here is the problem. I'm having 2 lists named, list and sum respectively.

list = {3, 2, 1, 6, 5, 4, 9, 7}
sums = {5, 6, 9, 10}

How to I find pairs of numbers in list that's matching any of the numbers in sums?

To start off, i generated possible number of pairs from list, using IntegerPartition command that will use only numbers from list to generate pairs.

(# -> IntegerPartitions[#, {2}, list]) & /@ sums // Column

5->{{4,1},{2,3}}
6->{{4,2},{5,1},{3,3}}
9->{{7,2},{4,5},{6,3}}
10->{{7,3},{9,1},{4,6},{5,5}}

In the above output, sums list of {5,6,9,10} can be written in pairs using the numbers in the list {3, 2, 1, 6, 5, 4, 9, 7}.

Transforming my list into possible pairs:

Partition[#, {2}] & /@ Permutations[list]

enter image description here

So, there are 40,320 combinations, out of these, how can I select a list that has pairs which sum up to any of the numbers in the sums list?
POSTED BY: Manjunath Babu
9 Replies
Sort By:
Bill Simpson
Bill Simpson
Posted 8 years ago

This should be enough of a hint to get you started.

Since it seems that you want to look at every possible pair of numbers from your list, you might look at the help page for the Outer function.

Outer[f, list, list]

is going to give every possible pair of numbers from your list to a function named f that you write. f is probably going to start with

f[ x_, y_ ] :=

and you need to think how you would complete that function, what you would return for a match and what would return for a non-match.
POSTED BY: Bill Simpson

I'm surprised to not see this simple (and faster) method:

GroupBy[Select[Subsets[list, {2}], MemberQ[sums, Total[#]] &], Total]

One can also use GatherBy instead of GroupBy (whatever one prefers), output is slightly in a different form.
POSTED BY: Sander Huisman

But how do I group the list into correct pairs such that each pair sum belongs to one of the items in sums?

For the input

list = {3, 2, 1, 6, 5, 4, 9, 7}
sums = {5, 6, 9, 10}

the output should be:

{{3, 6}, {2, 7}, {5, 4}, {1, 9}}
POSTED BY: Manjunath Babu

Its a well written function. I saw the output. ListSumPairSelect[] function is displaying 8 pairs per item.

The requirement is to display the output with original list itself that's grouped in pairs such that each pair sum is present in the sums list.

Current Output:

ListSumPairSelect[list, sums][[1]]
{{1, 5}, {2, 4}, {3, 2}, {1, 4}, {1, 5}, {3, 6}, {2, 7}, {1, 9}}

ListSumPairSelect[list, sums][[100]]
{{1, 5}, {2, 7}, {3, 2}, {1, 4}, {1, 5}, {6, 4}, {3, 7}, {1, 9}}

ListSumPairSelect[list, sums][[864]]
{{1, 9}, {3, 2}, {3, 7}, {6, 4}, {5, 4}, {6, 4}, {3, 7}, {1, 9}}

Expected Output: (should contain ONLY original list elements in pairs)

{{9, 1}, {7, 2}, {6, 3}, {5, 4}}
POSTED BY: Manjunath Babu

Well, i came up with this solution that needs optimization. However, it crashes for any list of length greater than 30

list = {3, 2, 1, 6, 5, 4, 9, 7};
sums = {5, 6, 9, 10};
Flatten[Select[
  DeleteDuplicates[
   Subsets[Flatten[IntegerPartitions[#, {2}, list] & /@ sums, 
     1], {Length[list]/2}]], 
  Length[Union[Flatten[#]]] == Length[Union[list]] &], 1]

Output:

{{7, 2}, {4, 5}, {6, 3}, {9, 1}}

I'd like to know what kind of an algorithms should be applied to problems of this type?

POSTED BY: Manjunath Babu

Hi I'm not really sure what you would like to achieve. It seems to me you have a list of numbers (sums) that can be constructed by summing up integers. The integerpartitions is exact what you need. When you go through that list for each item you generate the integerpartitions and next step is to see if any of these integer sets (or all?) is present in the list (use complement[]). I don't have mathematica at hand now but this should be easy when I see your code. But if your list contains eg (1,2,2,6) and sum is 5 you won't find a match if you only use pairs right? (1,2,2) would be a match but is missed in this approach. I hope this helps and this combined with Bill's suggestion you should be able to use much more then lists with 30 or more items. How many items do you have?
POSTED BY: l van Veen

Is it something like this?

Grid[Table[Select[Subsets[list, {2}], Total[#] == k &], {k, sums}]]

{3,2} {1,4}

{2,4} {1,5}

{3,6} {2,7} {5,4}

{3,7} {1,9} {6,4}

Rows corresponds to sums = {5, 6, 9, 10}.
POSTED BY: Vitaliy Kaurov

That was not clear at all from your question, but can easily be achieved: 

ClearAll[RecurseSelectHelper,RecurseSelect]
RecurseSelectHelper[uniqsleft_List,remainingpairs_List,selectedpairs_List]:=Module[{sel,opts},
    If[Length[uniqsleft]>0,
        sel=First[uniqsleft];
        opts=Select[remainingpairs,MemberQ[#,sel]&];
        If[Length[opts]>0,
            Do[RecurseSelectHelper[Rest[uniqsleft],Complement[remainingpairs,o],Append[selectedpairs,o]],{o,opts}]
        ]
    ,
        Sow[selectedpairs]
    ]
]
RecurseSelect[pairs_List]:=Reap[RecurseSelectHelper[Union@@pairs,pairs,{}]][[2,1]]
ListSumPairSelect[list_List,sums_List]:=RecurseSelect[Select[Subsets[list,{2}],MemberQ[sums,Total[#]]&]]

Now calling the function:

list = {3, 2, 1, 6, 5, 4, 9, 7};
sums = {5, 6, 9, 10};
AbsoluteTiming[options = ListSumPairSelect[list, sums];]

Gives 864 options, in 47 milliseconds. Not that swapping each pair (a,b) and (b,a) have not been taken in to account (Replace Subset[...,{2}] by Tuples[...,2] to get all of them.
POSTED BY: Sander Huisman

Hi Manjunath,

I think I finally understand what you want:

ClearAll[RecurseSelectHelper,RecurseSelect]
RecurseSelectHelper[uniqsleft_List,remainingpairs_List,selectedpairs_List]:=Module[{sel,opts},
    If[Length[uniqsleft]>0,
        sel=First[uniqsleft];
        opts=Select[remainingpairs,MemberQ[#,sel]&];
        Do[
            RecurseSelectHelper[Complement[uniqsleft,o],Select[remainingpairs,ContainsNone[#,o]&],Append[selectedpairs,o]]
           ,
            {o,opts}
        ]
    ,
        Sow[selectedpairs]
    ]
]
RecurseSelect[pairs_List]:=First[Reap[RecurseSelectHelper[Union@@pairs,pairs,{}]][[2]],{}]
ListSumPairSelect[list_List,sums_List]:=RecurseSelect[Select[Subsets[list,{2}],MemberQ[sums,Total[#]]&]]

calling it:

list = {3, 2, 1, 6, 5, 4, 9, 7}
sums = {5, 6, 9, 10};
AbsoluteTiming[options = ListSumPairSelect[list, sums]]

Gives:

{{{1, 9}, {2, 7}, {3, 6}, {5, 4}}}

One solution only. It can now only deal with unique values in 'list'. But that can be changed; I think you can deduce how the algorithm works and fine-tune it to your needs...
POSTED BY: Sander Huisman
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Tag limit exceeded
Note: Only the first five people you tag will receive an email notification; the other tagged names will appear as links to their profiles.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract