Group Abstract Group Abstract

Message Boards Message Boards

1
|
11.7K 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:

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

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

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

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

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

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
POSTED BY: l van Veen

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
Bill Simpson
Bill Simpson
Posted 9 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
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