Group Abstract

Message Boards

WOLFRAM COMMUNITY

6.3K Views

2 Replies

2 Total Likes

View groups...

Follow this post

Share this post:

GROUPS:

Wolfram Language

Is there a fast way to find all multiple pairs in a list?

Paul Cleary

Posted 5 years ago

On small lists of numbers using subsets and cases works reasonably well, but is slow when the list contains a few million entries. list = {616, 720, 1352, 1504, 2288, 3136, 3744, 4600, 4752, 5720, 7000, 7280, 8568, 8800, 10296, 12312, 13832, 16456, 20224, 23400, 27056, 27720, 32032, 37904, 39208, 46376, 61272, 70720, 83600, 102200, 117936, 139392, 184016, 306720, 353912, 418264, 511216, 920200, 1533672, 4601024}; Cases[Subsets[list, {2}], {a_, b_} /; Mod[b, a] == 0] {{616, 27720}, {616, 32032}, {616, 418264}, {720, 306720}, {1352, 39208}, {2288, 32032}, {8568, 1533672}}

On small lists of numbers using subsets and cases works reasonably well, but is slow when the list contains a few million entries.

list = {616, 720, 1352, 1504, 2288, 3136, 3744, 4600, 4752, 5720, 
   7000, 7280, 8568, 8800, 10296, 12312, 13832, 16456, 20224, 23400, 
   27056, 27720, 32032, 37904, 39208, 46376, 61272, 70720, 83600, 
   102200, 117936, 139392, 184016, 306720, 353912, 418264, 511216, 
   920200, 1533672, 4601024};

Cases[Subsets[list, {2}], {a_, b_} /; Mod[b, a] == 0]

{{616, 27720}, {616, 32032}, {616, 418264}, {720, 306720}, {1352, 
  39208}, {2288, 32032}, {8568, 1533672}}

POSTED BY: Paul Cleary

2 Replies

Sort By:

Trevor Cappallo

Posted 5 years ago

I'm pretty sure it's the `Subsets` that really slows that down, I think that would try (and presumably fail) to create a list in memory of $10^{12}$ pairs, if you're using a set with a million numbers. Anyway, depends how fast you're looking for. My first stab is s = Sort[RandomInteger[{2, 100000000}, 100000]]; Timing[r = Flatten[Table[{s[[i]], #} & /@ Pick[s[[;; i - 1]], Mod[s[[i]], s[[;; i - 1]]], 0], {i, 2, Length@s}], 1]; r[[{1, 2, 3, -3, -2, -1}]]] which takes about 30 seconds on my machine for 100k numbers: `{30.1719, {{194616, 194616}, {348102, 498}, {355572, 498}, {99883982, 4540181}, {99889338, 498}, {99950842, 49975421}}}`

POSTED BY: Trevor Cappallo

Paul Cleary

Posted 5 years ago

POSTED BY: Paul Cleary

Reply to this discussion

Reply Preview

Attachments

Remove Add a file to this post

Follow this discussion

or Discard

Feedback