Identifying Arithmetic progressions in a list of numbers
Question: M arithmetic progressions each having N terms (with the terms differing by
d1,d2,...dm) are passed as input with the terms shuffled. The program must
print the terms in M arithmetic progressions in sequential order with the
smallest starting term first.

Example Input/Output 1:

    
    
    Input: 2
           1 4 8 12 7 16 
    Output: 1 4 7 8 12 16
    Explanation: There are two progressions. Hence 6/2 = 3 terms in each progression. So the first A.M has 1 4 7 and the second has 8 12 16 As 1 < 8, 1 4 7 is printed followed by 8 12 16
    

Example Input/Output 2:

    
    
    Input: 3
           2 6 8 10 15 22 12 11 4
    Output: 2 4 6 8 15 22 10 11 12 
    

Explanation: There are three progressions. Hence 9/3 = 3 terms in each
progression. So the first A.M has 2 4 6 and the second has 8 15 22. The third
has 10 11 12. Note: We cannot have 8 10 12 as the second progression as the
remaining numbers 11 15 22 do not for an arithmetic progression.`

I thought of an approach to initially sort the numbers and then generate a
list of lists containing the difference of each number with every other
number.

    
    
    inp=raw_input()
    inputList=[int(c) for c in inp]
    inputList.sort()
    for i in range(0,len(inputList)):
       for j in range(0,len(inputList)):
          if(i!=j): #To avoid zeros
             newlist.append(abs(inputList[j]-inputList[i]))
    

Then, map each of the numbers in the same place with that in the other list.
Thus, a sequence can be identified. But it didn't work out. Is there a better
way to solve this problem (preferably in Python)?


Answer: You can get the combinations of the list after sorting in descending order
filtering by checking if the elements are arithmetic progressions then use a
Counter dict to keep track of what elements have been used to handle what
should be added:

    
    
    def arith_seq(l, m):
        l.sort(reverse=True)
        terms = len(l) // m
        combs = filter(lambda x: all((x[i + 1] - x[i] == x[1] - x[0]
                                           for i in range(len(x) - 1))), combinations(l, terms))
        out = []
        from collections import Counter
        cn = Counter(l)
        for ele in combs:
            if all(cn[c] > 0 for c in ele):
                out.append(ele[::-1])
                for c in ele:
                    cn[c] -= 1
        out.sort()
        return out
    

Using your input:

    
    
    In [6]: inp = 3
    
    In [7]: l = map(int,"2 6 8 10 15 22 12 11 4".split())
    
    In [8]: arith_seq(l,inp)
    Out[8]: [(2, 4, 6), (8, 15, 22), (10, 11, 12)]
    

