3
$\begingroup$

Possible Duplicate:
find subsequences of constant increase

Given an arbitrarily long list of integers (let's say they are sorted), how would one determine if any 3 (or more) of those integers make up an arithmetic sequence? (an arithmetic sequence is where the difference between consecutive terms is the same) Also how would one determine all such sequences in a given list?

For instance, I'd like this function to return

In[] = FindArithmSeq[{2,5,6,8,10,12}]
Out[]= {{2,5,8}, {2,6,10}, {6,8,10}, {8,10,12}, {6,8,10,12}}

Thanks in advance!

$\endgroup$
16
  • $\begingroup$ why should it not return eg {2,5,8}? $\endgroup$
    – acl
    Dec 5, 2012 at 1:00
  • $\begingroup$ yep :) forgot that one $\endgroup$
    – cartonn
    Dec 5, 2012 at 1:02
  • $\begingroup$ @JohnD and cartonn if it's consecutive then it's much easier! $\endgroup$
    – acl
    Dec 5, 2012 at 1:03
  • $\begingroup$ actually, it should probably be all elements anyways, I'm changing my result to the answer you suggested below $\endgroup$
    – cartonn
    Dec 5, 2012 at 1:04
  • 1
    $\begingroup$ Too often, a monster answer gets posted here and everything else gets ignored. Well, I hadn't noticed JM's solution, but when I did need to do this, I saw Leonid's answer and came up with my solution faster than I could understand Leonid's. Since in my use case I cannot go over lists of 10-15, this answer is perfectly fine. So overall what I mean is, it's nice that there's a general answer, but let's not go overboard with fully general code that ends up being unreadable. This is doing people who look for answers a disservice. $\endgroup$
    – acl
    Dec 6, 2012 at 12:42

1 Answer 1

2
$\begingroup$

I think this works for short lists:

f[lst_List, len_] := Module[
  {tpls = Subsets[lst, {len}]},
  Pick[
   tpls,
   1 == Length@DeleteDuplicates[Differences[#]] & /@ tpls
   ]
  ]

So for instance:

list = {2, 5, 6, 8, 10, 12};
Sequence @@ # & /@ (f[list, #] & /@ Range[3, Length@list])

(*{{2, 5, 8}, {2, 6, 10}, {6, 8, 10}, {8, 10, 12}, {6, 8, 10, 12}}*)

This finds all list of length 3 that make up an arithmetic sequence, then of length 4, up to the Length@list; then the Sequence@@#& bit is to get rid of empty sets.

Or am I missing something?

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.